Mercurial > 13ss.theoinf

comparison notes/tex/computation.tex @ 53:a2d28c18251a

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
ue12 notes
author Markus Kaiser <markus.kaiser@in.tum.de>
date Mon, 15 Jul 2013 23:51:55 +0200
parents adcb0ab03ade
children b815b94ae158
comparison
equal deleted inserted replaced
52:d5aa58bee83b 53:a2d28c18251a
726 \uncover<2>{\node at (10cm, 0) {$L = \left\{ (12^*3)^+ \right\}$};} 726 \uncover<2>{\node at (10cm, 0) {$L = \left\{ (12^*3)^+ \right\}$};}
727 \end{tikzpicture} 727 \end{tikzpicture}
728 \end{center} 728 \end{center}
729 \end{frame} 729 \end{frame}
730 } 730 }
731
732 \defineUnit{time}{%
733 \begin{frame}[t]
734 \frametitle{$TIME$}
735 \setbeamercovered{dynamic}
736
737 \begin{definition}[$TIME$]
738 Wir bezeichnen die minimale Anzahl der Schritte, bis eine \structure{DTM} $M$ mit Eingabe $w$ hält als $\alert{time_M(w)} \in \N \cup \left\{ \infty \right\}$.\\
739 \vspace{1em}
740 Sei $f : \N \to \N$ total. Dann ist
741 \begin{align*}
742 \alert{TIME(f(n))} := \{ A \subseteq \Sigma^* \mid \exists &\structure{DTM}\ M. A = L(M) \wedge \\
743 &\forall w \in \Sigma^*. \structure{time_M(w) \leq f(|w|)} \}
744 \end{align*}
745 die Klasse der \structure{in Zeit $f(n)$} von einer \structure{DTM} entscheidbaren Sprachen.
746 \end{definition}
747
748 \vfill
749
750 \begin{itemize}
751 \item $TIME(\Oh(n))$ enthält alle "\structure{linearen Probleme}".
752 \item Also alle Probleme, für die ein Linearzeitalgorithmus existiert.
753 \end{itemize}
754 \end{frame}
755 }
756
757 \defineUnit{ntime}{%
758 \begin{frame}[t]
759 \frametitle{$NTIME$}
760 \setbeamercovered{dynamic}
761
762 \begin{definition}[$NTIME$]
763 Wir bezeichnen die minimale Anzahl der Schritte, bis eine \structure{NTM} $M$ mit Eingabe $w$ hält als $\alert{ntime_M(w)} \in \N$.
764 \[ \alert{ntime_M(w)} := \begin{cases} \text{minimale Schrittanzahl} & \text{falls } w \in L(M) \\ 0 & \text{falls } w \not \in L(M)\end{cases} \]
765 Dann ist
766 \begin{align*}
767 \alert{NTIME(f(n))} := \{ A \subseteq \Sigma^* \mid \exists &\structure{NTM}\ M. A = L(M) \wedge \\
768 &\forall w \in \Sigma^*. \structure{ntime_M(w) \leq f(|w|)} \}
769 \end{align*}
770 die Klasse der \structure{in Zeit $f(n)$} von einer \structure{NTM} entscheidbaren Sprachen.
771 \end{definition}
772 \end{frame}
773 }
774
775 \defineUnit{pundnp}{%
776 \begin{frame}
777 \frametitle{P und NP}
778 \setbeamercovered{dynamic}
779
780 \begin{definition}
781 \alert{P} ist die Menge aller von einer \structure{DTM} in polynomieller Zeit entscheidbaren Sprachen.
782 \[\alert{P}:= \bigcup_{p\text{ Polynom}} TIME(p(n)) = \bigcup_{k \in \N} TIME(\alert{\Oh(n^k)}) \]
783 \end{definition}
784
785 \begin{definition}
786 \alert{NP} ist die Menge aller von einer \structure{NTM} in polynomieller Zeit entscheidbaren Sprachen.
787 \[\alert{NP}:= \bigcup_{p\text{ Polynom}} NTIME(p(n)) = \bigcup_{k \in \N} NTIME(\alert{\Oh(n^k)}) \]
788 \end{definition}
789 \end{frame}
790 }
791
792 \defineUnit{verifikator}{%
793 \begin{frame}
794 \frametitle{Verifikator}
795 \setbeamercovered{dynamic}
796
797 \begin{definition}[Verifikator]
798 Sei $M$ eine \structure{DTM} mit $L(M) \subseteq \left\{ w\# c \mid w \in \Sigma^*, c \in \Delta^* \right\}$.
799 \begin{itemize}
800 \item Falls $w\#c \in L(M)$, dann heißt $c$ \alert{Zertifikat} für $w$.
801 \item $M$ ist ein \alert{polynomiell beschränkter Verifikator} für
802 \[\left\{ \structure{w \in \Sigma^*} \mid \exists c \in \Delta^* . w\#c \in L(M) \right\}\]
803 falls $time_M(w\#c) \leq p(|w|)$ für ein Polynom $p$.
804 \end{itemize}
805 \end{definition}
806
807 \begin{itemize}
808 \item \structure{NTM} rät Lösung (Zertifikat), \structure{DTM} probiert sie aus.
809 \item Verifizieren (wahrscheinlich) einfacher als Lösung finden.
810 \end{itemize}
811
812 \vfill
813
814 \begin{theorem}
815 \alert{$A \in NP$} gdw es einen pol. beschränkten Verifikator für A gibt.
816 \end{theorem}
817 \end{frame}
818 }
819
820 \defineUnit{preduktion}{%
821 \begin{frame}
822 \frametitle{Polynomielle Reduzierbarkeit}
823 \setbeamercovered{dynamic}
824
825 \begin{definition}[Polynomielle Reduzierbarkeit]
826 Eine Menge $A \subseteq \Sigma^*$ ist \alert{polynomiell reduzierbar} auf eine Menge $B \subseteq \Gamma^*$ gdw es eine totale und \structure{von einer DTM in polynomieller Zeit} berechenbare Funktion $f:\Sigma^* \to \Gamma^*$ gibt mit
827 \[\forall w \in \Sigma^*. w \in A \Longleftrightarrow f(w) \in B\]
828 Wir schreiben dann \alert{$A \leq_P B$}.
829 \end{definition}
830
831 \vfill
832
833 \begin{itemize}
834 \item Die Relation $\leq_P$ ist \structure{transitiv}.
835 \item P und NP sind \structure{nach unten abgeschlossen}:
836 \[A \leq_P B \in P/NP \Longrightarrow A \in P/NP\]
837 \end{itemize}
838 \end{frame}
839 }
840
841 \defineUnit{npvollstaendigkeit}{%
842 \begin{frame}
843 \frametitle{NP-Vollständigkeit}
844 \setbeamercovered{dynamic}
845
846 \begin{definition}[NP-Schwere]
847 Eine Sprache $L$ heißt \alert{NP-schwer} (NP-hart) wenn sich \structure{alle Sprachen} in NP auf $L$ reduzieren lassen.
848 \[\forall A \in NP. A \leq_P L\]
849 \end{definition}
850
851 \begin{definition}[NP-Vollständigkeit]
852 Eine Sprache $L$ heißt \alert{NP-vollständig} wenn $L$ \structure{NP-schwer} ist und \structure{$L \in NP$}.
853 \end{definition}
854
855 \vfill
856
857 \structure{Fragen}:
858 \begin{itemize}
859 \item Gibt es überhaupt NP-vollständige Sprachen?
860 \item Gibt es eine NP-vollständige Sprache in $P$?
861 \end{itemize}
862 \end{frame}
863 }
864
865 \defineUnit{sat}{%
866 \begin{frame}
867 \frametitle{SAT}
868 \setbeamercovered{dynamic}
869
870 \begin{definition}[Aussagenlogik]
871 Syntax der \alert{Aussagenlogik}.\\
872 \begin{description}
873 \item[Formeln] $F \rightarrow \neg F \mid (F \wedge F) \mid (F \vee F) \mid X$
874 \item[Variablen] $X \rightarrow x \mid y \mid z \mid \ldots$
875 \end{description}
876 \end{definition}
877
878 \vfill
879
880 \begin{definition}[SAT]
881 Gegeben eine \structure{aussagenlogische Formel} $F$.\\
882 Ist $F$ \alert{erfüllbar}, also gibt es eine Belegung der Variablen in $F$, sodass $F$ gilt?
883 \end{definition}
884
885 \begin{theorem}[Cook 1971]
886 $\mathbf{SAT}$ ist \alert{NP-vollständig}.
887 \end{theorem}
888 \end{frame}
889 }
890
891 \defineUnit{3col}{%
892 \begin{frame}
893 \frametitle{3COL}
894 \setbeamercovered{dynamic}
895
896 \begin{definition}[3COL]
897 Gegeben ein \structure{Graph} $G = (V, E)$.\\
898 Gibt es eine \alert{Färbung der Knoten} $V$ mit $3$ Farben, so dass keine zwei benachbarten Knoten die gleiche Farbe haben?
899 \end{definition}
900
901 \vfill
902
903 \begin{center}
904 \begin{tikzpicture}
905 \tikzstyle{red} = [fill=tumred!50]
906 \tikzstyle{green} = [fill=tumgreen!50]
907 \tikzstyle{blue} = [fill=tumblue!50]
908 \tikzstyle{vertex} = [draw, circle, thin, blue]
909 \tikzstyle{edge} = [draw, thick]
910
911 \foreach \name/\angle/\dist/\col in {
912 ia/18/0.8cm/blue, ib/90/0.8cm/red, ic/162/0.8cm/red, id/234/0.8cm/green, ie/306/0.8cm/green,
913 oa/18/1.6cm/red, ob/90/1.6cm/blue, oc/162/1.6cm/green, od/234/1.6cm/red, oe/306/1.6cm/blue} {
914 \node<1>[vertex] (\name) at (\angle:\dist) {};
915 \node<2>[vertex, \col] (\name) at (\angle:\dist) {};
916 }
917
918 \foreach \a/\b in {
919 ia/oa, ib/ob, ic/oc, id/od, ie/oe,
920 oa/ob, ob/oc, oc/od, od/oe, oe/oa,
921 ia/ic, ic/ie, ie/ib, ib/id, id/ia} {
922 \draw[edge] (\a) -- (\b);
923 }
924 \end{tikzpicture}
925 \end{center}
926
927 \begin{theorem}
928 Es ist \alert{$\mathbf{3COL} \leq_P \mathbf{SAT}$} und $\alert{\mathbf{SAT}} \leq_P \mathbf{3SAT} \alert{\leq_P \mathbf{3COL}}$.
929 \end{theorem}
930 \end{frame}
931 }