#LyX 2.4 created this file. For more info see https://www.lyx.org/
\lyxformat 620
\begin_document
\begin_header
\save_transient_properties true
\origin unavailable
\textclass article
\use_default_options true
\begin_modules
theorems-ams
theorems-ams-extended
\end_modules
\maintain_unincluded_children no
\language slovene
\language_package default
\inputencoding utf8
\fontencoding auto
\font_roman "default" "default"
\font_sans "default" "default"
\font_typewriter "default" "default"
\font_math "auto" "auto"
\font_default_family default
\use_non_tex_fonts false
\font_sc false
\font_roman_osf false
\font_sans_osf false
\font_typewriter_osf false
\font_sf_scale 100 100
\font_tt_scale 100 100
\use_microtype false
\use_dash_ligatures true
\graphics default
\default_output_format default
\output_sync 0
\bibtex_command default
\index_command default
\float_placement class
\float_alignment class
\paperfontsize default
\spacing single
\use_hyperref false
\papersize default
\use_geometry false
\use_package amsmath 1
\use_package amssymb 1
\use_package cancel 1
\use_package esint 1
\use_package mathdots 1
\use_package mathtools 1
\use_package mhchem 1
\use_package stackrel 1
\use_package stmaryrd 1
\use_package undertilde 1
\cite_engine basic
\cite_engine_type default
\biblio_style plain
\use_bibtopic false
\use_indices false
\paperorientation portrait
\suppress_date false
\justification true
\use_refstyle 1
\use_formatted_ref 0
\use_minted 0
\use_lineno 0
\index Index
\shortcut idx
\color #008080
\end_index
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\paragraph_indentation default
\is_math_indent 0
\math_numbering_side default
\quotes_style english
\dynamic_quotes 0
\papercolumns 1
\papersides 1
\paperpagestyle default
\tablestyle default
\tracking_changes false
\output_changes false
\change_bars false
\postpone_fragile_content true
\html_math_output 0
\html_css_as_file 0
\html_be_strict false
\docbook_table_output 0
\docbook_mathml_prefix 1
\end_header

\begin_body

\begin_layout Section*
IRZV FRI 2024-12-11 (desete vaje)
\end_layout

\begin_layout Section
Odločitveni problem
\end_layout

\begin_layout Itemize
Vhod:
 števila 
\begin_inset Formula $a_{1},\dots,a_{n}\in\mathbb{Z}^{+}$
\end_inset

,
 število 
\begin_inset Formula $k\in\mathbb{Z}^{+}$
\end_inset


\end_layout

\begin_layout Itemize
Izhod:
 DA 
\begin_inset Formula $\Leftrightarrow\exists I\subseteq\left\{ 1,\dots n\right\} \ni:\sum_{i\in I}a_{i}=k$
\end_inset

 (sicer NE)
\end_layout

\begin_layout Subsection
Naloge
\end_layout

\begin_layout Enumerate
Naloga.
 Vhod:
 
\begin_inset Formula $a_{1}=3$
\end_inset

,
 
\begin_inset Formula $a_{2}=8$
\end_inset

,
 
\begin_inset Formula $a_{3}=7$
\end_inset

,
 
\begin_inset Formula $a_{4}=4$
\end_inset

,
 
\begin_inset Formula $k=14$
\end_inset

.
 Izhod je DA.
 Serializiramo kot 
\begin_inset Formula $1^{3}01^{8}01^{7}01^{4}001^{14}$
\end_inset

.
 
\begin_inset Formula $0$
\end_inset

 je delimiter in 
\begin_inset Formula $00$
\end_inset

 je 
\begin_inset Quotes eld
\end_inset

konec
\begin_inset Quotes erd
\end_inset

 števil 
\begin_inset Formula $a_{i}$
\end_inset

.
\end_layout

\begin_layout Enumerate
Naloga:
 Vhod:
 
\begin_inset Formula $a_{1}=3$
\end_inset

,
 
\begin_inset Formula $a_{2}=8$
\end_inset

,
 
\begin_inset Formula $a_{3}=7$
\end_inset

,
 
\begin_inset Formula $a_{4}=4$
\end_inset

,
 
\begin_inset Formula $k=16$
\end_inset

.
 Izhod je NE.
 Serializiramo kot 
\begin_inset Formula $1^{3}01^{8}01^{7}01^{4}001^{16}$
\end_inset

.
\end_layout

\begin_layout Standard
Pretvorimo te serializirane nize v jezik.
 Niz je v jeziku,
 če predstavlja nalogo odločitvenega problema z izhodom DA.
 
\begin_inset Formula $1^{3}01^{8}01^{7}01^{4}001^{14}\in L$
\end_inset

,
 
\begin_inset Formula $1^{3}01^{8}01^{7}01^{4}001^{16}\not\in L$
\end_inset

.
 
\begin_inset Formula $L$
\end_inset

 je torej jezik odločitvenih nalog.
\end_layout

\begin_layout Standard
Za ta jezik konstruirajmo Turingov stroj.
 Pri izdelavi stroja predpostavimo,
 da je vhodni jezik smiseln.
\end_layout

\begin_layout Subparagraph
Turingov stroj
\end_layout

\begin_layout Standard
Bo nedeterminističen.
 Poskusimo vse možne odločitve (podmnožice števil 
\begin_inset Formula $a_{i}$
\end_inset

) in preverimo,
 ali so naloge z izhodom DA.
\end_layout

\begin_layout Itemize
\begin_inset Formula $T1=11101111111101111111011110011111111111111=1^{3}01^{8}01^{7}01^{4}001^{14}$
\end_inset

 (vhod oz.
 začetno stanje traku)
\end_layout

\begin_layout Itemize
Na 
\begin_inset Formula $T2$
\end_inset

 prepišemo nekaj odločitev (nedeterministično in tokrat brez delimiterjev) in primerjamo ta trak z enicami po 
\begin_inset Formula $00$
\end_inset

 v 
\begin_inset Formula $T1$
\end_inset

.
 Na primer 
\begin_inset Formula $T2=11111111111111$
\end_inset

 (vzamemo 
\begin_inset Formula $a_{1}$
\end_inset

,
 
\begin_inset Formula $a_{3}$
\end_inset

 in 
\begin_inset Formula $a_{4}$
\end_inset

).
\end_layout

\begin_layout Standard
Predpis stroja:
\end_layout

\begin_layout Itemize
\begin_inset Formula $q_{1}$
\end_inset

 predstavlja stanje,
 ko bomo skopirali 
\begin_inset Formula $a_{i}$
\end_inset

 na drugi trak,
 
\begin_inset Formula $q_{2}$
\end_inset

 pa stanje,
 ko preskakujemo ta 
\begin_inset Formula $a_{i}$
\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\delta\left(q_{0},1,B\right)=\left\{ \left(q_{1},\left(1,R\right),\left(1,R\right)\right),\left(q_{2},\left(1,R\right),\left(B,S\right)\right)\right\} 
\]

\end_inset


\begin_inset Formula 
\[
\delta\left(q_{1},1,B\right)=\left\{ \left(q_{1},\left(1,R\right),\left(1,R\right)\right)\right\} 
\]

\end_inset


\begin_inset Formula 
\[
\delta\left(q_{2},1,B\right)=\left\{ \left(q_{2},\left(1,R\right),\left(B,S\right)\right)\right\} 
\]

\end_inset


\begin_inset Formula 
\[
\delta\left(q_{1},0,B\right)=\left\{ \left(q_{0},\left(0,R\right),\left(B,S\right)\right)\right\} 
\]

\end_inset


\begin_inset Formula 
\[
\delta\left(q_{2},0,B\right)=\left\{ \left(q_{0},\left(0,R\right),\left(B,S\right)\right)\right\} 
\]

\end_inset


\begin_inset Formula 
\[
\delta\left(q_{0},0,B\right)=\left\{ \left(q_{3},\left(0,R\right),\left(B,L\right)\right)\right\} 
\]

\end_inset


\begin_inset Formula 
\[
\delta\left(q_{3},1,1\right)=\left\{ \left(q_{3},\left(1,R\right),\left(1,L\right)\right)\right\} 
\]

\end_inset


\begin_inset Formula 
\[
\delta\left(q_{3},B,B\right)=\left\{ \left(q_{F},\left(B,S\right),\left(B,S\right)\right)\right\} 
\]

\end_inset


\end_layout

\begin_layout Section
Optimizacijski problem
\end_layout

\begin_layout Itemize
Vhod:
 
\begin_inset Formula $a_{1},a_{2},\dots,a_{n}\in\mathbb{Z}\setminus\left\{ 0\right\} ,\exists i\in\left[n\right]\ni:a_{i}>0$
\end_inset


\end_layout

\begin_layout Itemize
Izhod:
 
\begin_inset Formula $\max_{1\leq p\leq q\leq n}\sum_{i=p}^{q}a_{i}$
\end_inset

.
\end_layout

\begin_layout Subsection
Naloge
\end_layout

\begin_layout Enumerate
Naloga.
 Vhod:
 
\begin_inset Formula $a=\left(3,-4,5,-3,4,-1\right)$
\end_inset

,
 Izhod:
 
\begin_inset Formula $6$
\end_inset

 (
\begin_inset Formula $5+\left(-3\right)+4=5$
\end_inset

)
\end_layout

\begin_layout Standard
Kako bi optimizacijski problem pretvorili v odločitveni problem?
 Takole:
\end_layout

\begin_layout Itemize
Vhod:
 
\begin_inset Formula $a_{1},a_{2},\dots,a_{n}$
\end_inset

,
 
\begin_inset Formula $k\in\mathbb{Z}^{+}$
\end_inset

.
\end_layout

\begin_layout Itemize
Izhod:
 DA 
\begin_inset Formula $\Leftrightarrow\exists p,q,1\leq p\leq q\leq n\ni:\sum_{i=p}^{q}a_{i}>k$
\end_inset

.
\end_layout

\begin_layout Standard
Torej ali je vsota večja od 
\begin_inset Formula $k$
\end_inset

.
\end_layout

\begin_layout Paragraph*
Kako serializiramo nalogo?
\end_layout

\begin_layout Itemize
Naloga:
 
\begin_inset Formula $A=\left(3,-4,5,-3,4,-1\right),$
\end_inset


\begin_inset Formula $k=5$
\end_inset

 serializiramo kot 
\begin_inset Formula $1^{3}001^{4}01^{5}001^{3}01^{4}001^{1}0001^{5}$
\end_inset

 (končni terminator je 
\begin_inset Formula $000$
\end_inset

,
 delimiter je 
\begin_inset Formula $0$
\end_inset

,
 vsako negativno številko prefixamo z 
\begin_inset Formula $0$
\end_inset

).
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\begin{array}{ccccccc}
 & 3 & -4 & 5 & -3 & 4 & -1\\
0 & 3 & -1 & 5 & 2 & 6 & 5\\
 &  & \downarrow\\
 &  & 0
\end{array}
\]

\end_inset

Algoritem:
 Tekoče vsote.
\end_layout

\begin_layout Paragraph
Turingov stroj
\end_layout

\begin_layout Itemize
\begin_inset Formula $T1$
\end_inset

:
 
\begin_inset Formula $111001111011111001110111100100011111$
\end_inset


\end_layout

\begin_layout Itemize
\begin_inset Formula $T2$
\end_inset

:
 
\begin_inset Formula $0111$
\end_inset

,
 
\begin_inset Formula $\leftarrow\leftarrow\leftarrow S$
\end_inset

,
 
\begin_inset Formula $111$
\end_inset

,
 
\begin_inset Formula $11$
\end_inset

,
 
\begin_inset Formula $\leftarrow\leftarrow\leftarrow$
\end_inset

,
 
\begin_inset Formula $1111$
\end_inset

,
 
\begin_inset Formula $\leftarrow$
\end_inset


\end_layout

\begin_layout Standard
Opis:
 označimo si levi rob traku 
\begin_inset Formula $T2$
\end_inset

 z 
\begin_inset Formula $0$
\end_inset

,
 nato potujemo desno po 
\begin_inset Formula $T1$
\end_inset

,
 za vsako pozitivno številko dodamo toliko enic na 
\begin_inset Formula $T2$
\end_inset

,
 za vsako negativno pa se premaknemo levo na traku za toliko,
 nikoli bolj levo od označbe za levi rob traku.
 Na koncu 
\begin_inset Formula $T1$
\end_inset

 primerjamo,
 ali je na traku več enic kot za 
\begin_inset Formula $000$
\end_inset

 na 
\begin_inset Formula $T1$
\end_inset

.
\end_layout

\begin_layout Itemize
\begin_inset Formula $\delta\left(q_{0},x\in\left\{ 1,0\right\} ,B\right)=\left(q_{1},\left(x,S\right),\left(0,R\right)\right)$
\end_inset

 Označimo si levi rob.
\end_layout

\begin_layout Itemize
\begin_inset Formula $\delta\left(q_{1},1,\left\{ B,1\right\} \right)=\left(q_{3+},\left(1,B\right),\left(1,R\right)\right)$
\end_inset

 oz.
 
\begin_inset Formula $\delta\left(q_{1},1,0\right)=\left(q_{3+},\left(1,B\right),\left(0,R\right)\right)$
\end_inset


\end_layout

\begin_layout Itemize
\begin_inset Formula $\delta\left(q_{1},0,x\in\left\{ B,1,0\right\} \right)=\left(q_{2},\left(0,R\right),\left(x,S\right)\right)$
\end_inset


\end_layout

\begin_layout Itemize
\begin_inset Formula $\delta\left(q_{2},1,x\in\left\{ B,1\right\} \right)=\left(q_{3-},\left(1,B\right),\left(x,L\right)\right)$
\end_inset

 oz.
 
\begin_inset Formula $\delta\left(q_{2},1,0\right)=\left(q_{3-},\left(1,B\right),\left(0,S\right)\right)$
\end_inset

 Začetek negativnega števila.
\end_layout

\begin_layout Itemize
\begin_inset Formula $\delta\left(q_{3+},1,\left\{ B,1\right\} \right)=\left(q_{3+},\left(1,R\right),\left(1,R\right)\right)$
\end_inset

 Pišemo enice na drugi trak in se pomikamo desno.
\end_layout

\begin_layout Itemize
\begin_inset Formula $\delta\left(q_{3+},0,x\in\left\{ B,1\right\} \right)=\left(q_{1},\left(0,R\right),\left(x,S\right)\right)$
\end_inset

 Konec številke 
\begin_inset Formula $a_{i}$
\end_inset

.
\end_layout

\begin_layout Itemize
\begin_inset Formula $\delta\left(q_{3-},1,1\right)=\left(q_{3-},\left(1,R\right),\left(1,L\right)\right)$
\end_inset

,
 
\begin_inset Formula $\delta\left(q_{3-},1,0\right)=\left(q_{3-},\left(0,S\right),\left(1,L\right)\right)$
\end_inset

 Pomikamo se na levo oz.
 stallamo,
 če smo na levem robu 
\begin_inset Formula $T2$
\end_inset

.
\end_layout

\begin_layout Itemize
\begin_inset Formula $\delta\left(q_{3-},0,x\in\left\{ 1,0\right\} \right)=\left(q_{1},\left(0,R\right),\left(x,S\right)\right)$
\end_inset


\end_layout

\begin_layout Itemize
\begin_inset Formula $\delta\left(q_{2},0,x\in\left\{ B,1\right\} \right)=\left(q_{4},\left(0,R\right),\left(x,L\right)\right)$
\end_inset

 oz.
 
\begin_inset Formula $\delta\left(q_{2},0,0\right)=\left(q_{5},\left(0,R\right),\left(x,R\right)\right)$
\end_inset

 Prebrali smo terminator 000.
\end_layout

\begin_layout Itemize
\begin_inset Formula $\delta\left(q_{4},1,1\right)=\left(q_{4},\left(1,S\right),\left(1,L\right)\right)$
\end_inset

 Pomikamo se levo na 
\begin_inset Formula $T2$
\end_inset

.
\end_layout

\begin_layout Itemize
\begin_inset Formula $\delta\left(q_{5},1,1\right)=\left(q_{5},\left(1,R\right),\left(1,R\right)\right)$
\end_inset

 Primerjamo dolžini (pomikamo se desno na obeh).
\end_layout

\begin_layout Itemize
\begin_inset Formula $\delta\left(q_{5},B,1\right)=\left(q_{F},\left(B,S\right),\left(1,S\right)\right)$
\end_inset


\end_layout

\begin_layout Standard
D.
 N.:
 simuliraj ta stroj za nek primer in najdi alternativne manjše rešitve.
\end_layout

\begin_layout Section
Serializacija/jezik Turingovih strojev
\end_layout

\begin_layout Definition*
Naj bo 
\begin_inset Formula $L_{\varepsilon}=$
\end_inset


\begin_inset Formula $\left\{ \left\langle M\right\rangle ;L\left(M\right)=\emptyset\right\} $
\end_inset

 ...
 jezik Turingovih strojev,
 ki sprejmejo prazen jezik.
\end_layout

\begin_layout Standard
Kodirali bomo enotračne deterministične stroje.
 Njihova stanja:
 
\begin_inset Formula $q_{1}$
\end_inset

 začetno,
 
\begin_inset Formula $q_{2}$
\end_inset

 edino končno,
 
\begin_inset Formula $q_{i},i\geq3$
\end_inset

 ostala stanja.
 Tračna abeceda:
 
\begin_inset Formula $X_{1}=0,X_{2}=1,X_{3}=B,X_{4},\dots$
\end_inset

 Smer premika:
 
\begin_inset Formula $D_{1}=L,D_{2}=R$
\end_inset

.
 Prehod 
\begin_inset Formula $\delta\left(q_{i},X_{j}\right)=\left(q_{k},X_{l},D_{m}\right)$
\end_inset

 zakodiramo/serializiramo kot 
\begin_inset Formula $0^{i}10^{j}10^{k}10^{l}10^{m}$
\end_inset

.
 
\begin_inset Formula $c_{1},\dots,c_{n}$
\end_inset

 so serializacije prehodov 
\begin_inset Formula $c_{1}11c_{2}11\dots c_{n-1}11c_{n}$
\end_inset

.
\end_layout

\begin_layout Definition*
Univerzalni Turingov stroj je stroj,
 ki sprejme opis stroja 
\begin_inset Formula $M$
\end_inset

 z dodano besedo 
\begin_inset Formula $w$
\end_inset

 in vrne DA,
 če 
\begin_inset Formula $w\in L\left(M\right)$
\end_inset

.
 Par 
\begin_inset Formula $\left(M,w\right)$
\end_inset

 (vhod) je serializiran kot 
\begin_inset Formula $c_{M}111w$
\end_inset

.
\end_layout

\begin_layout Exercise*
Turingov stroj za 
\begin_inset Formula $1^{+}0^{+}$
\end_inset

 in napiši njegovo serializacijo/kodo.
\end_layout

\begin_layout Itemize
\begin_inset Formula $\delta\left(q_{1},1\right)=\left(q_{3},1,R\right)$
\end_inset

,
 
\begin_inset Formula $c_{1}=0100100010100$
\end_inset


\end_layout

\begin_layout Itemize
\begin_inset Formula $\delta\left(q_{3},1\right)=\left(q_{3},1,R\right)$
\end_inset

,
 
\begin_inset Formula $c_{2}=0001001000100100$
\end_inset


\end_layout

\begin_layout Itemize
\begin_inset Formula $\delta\left(q_{3},0\right)=\left(q_{4},0,R\right)$
\end_inset

,
 
\begin_inset Formula $c_{3}=000101000010100$
\end_inset


\end_layout

\begin_layout Itemize
\begin_inset Formula $\delta\left(q_{4},0\right)=\left(q_{4},0,R\right)$
\end_inset

,
 
\begin_inset Formula $c_{4}=0000101000010100$
\end_inset


\end_layout

\begin_layout Itemize
\begin_inset Formula $\delta\left(q_{4},B\right)=\left(q_{2},B,L\right)$
\end_inset

,
 
\begin_inset Formula $c_{5}=00001000100100010$
\end_inset


\end_layout

\begin_layout Standard
Koda/serializacija:
 
\begin_inset Formula $c_{1}11c_{2}11c_{3}11c_{4}11c_{5}11$
\end_inset

.
\end_layout

\begin_layout Definition*
Če niz ne predstavlja veljavnega Turingovega stroja po sedanji definiciji,
 definirajmo,
 da opiše stroj s praznim jezikom.
\end_layout

\begin_layout Standard
Potemtakem 
\begin_inset Formula $c_{1}11c_{2}11c_{3}11c_{4}11c_{5}11$
\end_inset

 od prej 
\begin_inset Formula $\not\in L_{\varepsilon}$
\end_inset


\end_layout

\end_body
\end_document