====== Teorie algoritmů ======
{{ :courses:tal:prikl-slozitost.pdf| Dodatečné příklady pro 1. test (aktuální pro B252) }}
{{ :courses:tal:tal_casova_narocnost_pdf.pdf| Časová náročnost algoritmů (aktuální pro B252) }}
{{ :courses:tal:ukazka2.pdf| Ukázka 2. semestrálního testu}}
[[https://docs.google.com/document/d/1mj6l2iNKkJ4jFPcC5gjHnKnaLEOg31Nb10VRGIqsVs0|Kdo se pTAL (potřeba školní účet)]]
[[https://docs.google.com/document/d/1z_V0m3zSVl-_ckbd1mbUHATLXfBqJ7FYz_xVq3Vrd-k|Tal testy]]
==== Odkazy na přednášky ====
[[https://www.youtube.com/watch?v=15_3jkRUDHA&list=PLQL6z4JeTTQk7z9Nfjx1MpqI9c3bghnVK&index=2|22/23]]
[[https://www.youtube.com/playlist?list=PLQL6z4JeTTQncMnh4aPqU2rOWlF4hwyIq|24/25]]
^ 1. týden ^ 2. týden ^ 3. týden ^ 4. týden ^ 5. týden ^ 6. týden ^ 7. týden ^ 8. týden ^ 9. týden ^ 10. týden ^ 11. týden ^ 12. týden ^ 13. týden ^ ostatní |
| {{ :courses:tal:tals2601w.pdf| prezentace}} | {{ :courses:tal:tals2602w.pdf| prezentace}} | {{ :courses:tal:tals2603w.pdf| prezentace}} | {{ :courses:tal:tals2604w.pdf| prezentace}} | {{ :courses:tal:tals2605w.pdf| prezentace}} | {{ :courses:tal:tals2606w.pdf| prezentace}} | {{ :courses:tal:tals2607w.pdf| prezentace}} | {{ :courses:tal:tals2608w.pdf| prezentace}} | {{ :courses:tal:tals2609w.pdf| prezentace}} | {{ :courses:tal:tals2610w.pdf| prezentace}} | {{ :courses:tal:tals2611w.pdf| prezentace}} | {{ :courses:tal:tals2612w.pdf| prezentace}} | {{ :courses:tal:tals2613w.pdf| prezentace}} | {{:courses:tal:tal-doh.pdf | skripta}} |
| {{ :courses:tal:c-tal2601v.pdf| cvičení}} | {{ :courses:tal:c-tal2602v.pdf| cvičení}} | {{ :courses:tal:c-tal2603v.pdf| cvičení}} | {{ :courses:tal:c-tal2604.pdf| cvičení}} | {{ :courses:tal:c-tal2605.pdf| cvičení}} | {{ :courses:tal:c-tal2606.pdf| cvičení}} | {{ :courses:tal:c-tal2607.pdf| cvičení}} | {{ :courses:tal:c-tal2608.pdf| cvičení}} | {{ :courses:tal:c-tal2609.pdf| cvičení}} | {{ :courses:tal:c-tal2610v.pdf| cvičení}} | {{ :courses:tal:c-tal2611v.pdf| cvičení}} | {{ :courses:tal:c-tal2612.pdf| cvičení}} | {{ :courses:tal:c-tal2613.pdf| cvičení}} | {{:courses:tal:tal_definice3.0.pdf|definice}} |
===== Testy ze semestru =====
{{:courses:pasted:20250326-092807.png?direct&400}}
{{:courses:pasted:20250326-092837.png?direct&400}}
{{:courses:pasted:20250326-092854.png?direct&400}}
{{:courses:pasted:20250326-092904.png?direct&400}}
===== Zkouška 2025 =====
{{:courses:tal_zkouska_2025_1.jpg?direct&400|}}
{{:courses:tal:c6ccf5bb-a002-47df-8433-575ab53a84a5.jpg?direct&435|}}
{{:courses:tal:094aafdd-e7a7-4bcf-95ed-0d57d1469838.jpg?direct&400|}}
{{:courses:pasted:20260607-094938.png?direct&450|}}
===== Poznámky a příklady =====
Non-deterministic Turing Machine for $L = \{w00w \mid w \in \{0, 1\}^*\}$
\usetikzlibrary{automata, positioning, arrows.meta}
\begin{document}
\begin{tikzpicture}[
shorten >=1pt,
node distance=2.5cm and 2.5cm,
on grid,
>={Stealth[round]},
thick,
auto,
every loop/.style={looseness=6}
]
\node[state, initial] (q0) {$q_0$};
\node[state] (q1) [right=of q0] {$q_1$};
\node[state] (q2) [right=of q1] {$q_2$};
\node[state] (q3) [right=of q2] {$q_3$};
\node[state] (q4) [above right=1.5cm and 2.5cm of q3] {$q_4$};
\node[state] (q5) [below right=1.5cm and 2.5cm of q3] {$q_5$};
\node[state] (q6) [right=of q4] {$q_6$};
\node[state] (q7) [right=of q5] {$q_7$};
\node[state] (q8) [below right=1.5cm and 2.5cm of q6] {$q_8$};
\node[state] (q9) [below=4cm of q3] {$q_9$};
\node[state, accepting] (qf) [right=of q9] {$q_f$};
\path[->]
(q0) edge [loop above] node[align=center] {$0,0,\rightarrow$ \\ $1,1,\rightarrow$} ()
edge node {$0,Z,\rightarrow$} (q1)
(q1) edge node {$0,Z,\leftarrow$} (q2)
(q2) edge [loop above] node[align=center] {$0,0,\leftarrow$ \\ $1,1,\leftarrow$ \\ $Z,Z,\leftarrow$} ()
edge node {$B,B,\rightarrow$} (q3)
(q3) edge [loop above] node {$X,X,\rightarrow$} ()
edge [bend left=15] node[below right] {$0,X,\rightarrow$} (q4)
edge [bend right=15] node[above right] {$1,X,\rightarrow$} (q5)
edge node[left] {$Z,Z,\rightarrow$} (q9)
(q4) edge [loop above] node[align=center] {$0,0,\rightarrow$ \\ $1,1,\rightarrow$} ()
edge node {$Z,Z,\rightarrow$} (q6)
(q5) edge [loop below] node[align=center] {$0,0,\rightarrow$ \\ $1,1,\rightarrow$} ()
edge node {$Z,Z,\rightarrow$} (q7)
(q6) edge [loop above] node {$Z,Z,\rightarrow$} ()
edge [bend left=15] node {$0,Z,\leftarrow$} (q8)
(q7) edge [loop below] node {$Z,Z,\rightarrow$} ()
edge [bend right=15] node[below right] {$1,Z,\leftarrow$} (q8)
(q8) edge [loop right] node[align=center] {$0,0,\leftarrow$ \\ $1,1,\leftarrow$ \\ $X,X,\leftarrow$ \\ $Z,Z,\leftarrow$} ()
edge node[above, pos=0.5] {$B,B,\rightarrow$} (q3)
(q9) edge [loop below] node {$Z,Z,\rightarrow$} ()
edge node {$B,B,\leftarrow$} (qf);
\end{tikzpicture}
\end{document}
----
The Turing machine $M$ realizes the function $f: \{a, b\}^* \to \{a, b\}^*$ defined by:
$ f(w) = a^k b^l, \quad \text{where}\ k = |w|_a \text{ and } l = |w|_b. $
(sorts a's and b's)
\usetikzlibrary{automata, positioning, arrows.meta}
\begin{document}
\begin{tikzpicture}[
shorten >=1pt,
node distance=3cm,
>={Stealth[round]},
thick,
auto,
every loop/.style={looseness=6}
]
\node[state, initial] (q0) at (0, 0) {$q_0$};
\node[state] (q1) at (3, 0) {$q_1$};
\node[state] (q2) at (6, 0) {$q_2$};
\node[state] (q3) at (3, -3) {$q_3$};
\node[state, accepting] (qf) at (0, -3) {$q_f$};
\path[->]
(q0) edge [loop above] node {a,a,$\rightarrow$} ()
edge node {b,X,$\rightarrow$} (q1)
edge [bend right=20] node [below left] {B,B,$\rightarrow$} (qf)
(q1) edge [loop above] node {b,b,$\rightarrow$} ()
edge node {a,b,$\leftarrow$} (q2)
edge node {B,B,$\leftarrow$} (q3)
(q2) edge [loop right] node[align=center] {a,a,$\leftarrow$ \\ b,b,$\leftarrow$} ()
edge [bend right=60] node [above] {X,a,$\rightarrow$} (q0)
(q3) edge [loop right] node[align=center] {a,a,$\leftarrow$ \\ b,b,$\leftarrow$} ()
edge node {X,b,$\rightarrow$} (qf);
\end{tikzpicture}
\end{document}