Benutzer:Wdvorak/in arbeit

Listen zu meiner eigenen Verwendung.

Artikeln mit Mängeln/Lücken

• Polynomialzeithierarchie
• Chernoff-Ungleichung

Turingmaschinen

• Turingmaschine
• Linear beschränkte Turingmaschine
• Nichtdeterministische Turingmaschine
• Alternierende Turingmaschine
• Probabilistische Turingmaschine
• Turingmaschine mit Zusatzeingabe
• Mehrband-Turingmaschine en:Multitape Turing machine
• Mehrspuren-Turingmaschine en:Multi-track_Turing_machine

• Orakel-Turingmaschine
• Zenomaschine
• Turingmaschine Typ 2
• Vergessliche Turingmaschine
• Quanten-Turingmaschine
• Persistente Turingmaschine

• Fleißiger Biber

• Hilbertsches Entscheidungsproblem en:Entscheidungsproblem

Literatur

• John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie. 3., aktualisierte Auflage. Pearson Studium, München 2011, ISBN 978-3-86894-082-4 (englisch: Introduction to Automata Theory, Languages, and Computation. 2007. Übersetzt von Sigrid Richter und Ingrid Tokar). 
• Ingo Wegener: Theoretische Informatik. Eine algorithmenorientierte Einführung. B.G. Teubner, Stuttgart, ISBN 3-519-02123-4. 
• Uwe Schöning: Theoretische Informatik – kurz gefasst. 5. Auflage. Spektrum Akademischer Verlag, Heidelberg 2008, ISBN 978-3-8274-1824-1. 
• Juraj Hromkovič: Theoretische Informatik. Formale Sprachen, Berechenbarkeit, Komplexitätstheorie, Algorithmik, Kommunikation und Kryptographie. 3. Auflage. B.G. Teubner Verlag, Heidelberg 2007, ISBN 978-3-8351-0043-5. 
• Thomas A. Sudkamp: Languages and Machines. An Introduction to the Theory of Computer Science. Second edition Auflage. Addison-Wesley, 1998, ISBN 0-201-82136-2. 
• Sanjeev Arora, Boaz Barak: Computational Complexity: A Modern Approach. Cambridge University Press, Cambridge; New York 2009, ISBN 978-0-521-42426-4 (Draft [PDF; abgerufen am 30. Juli 2016]). 
• Christos H.Papadimitriou: Computational Complexity. Addison-Wesley, Reading/Mass, 1995, ISBN 978-0-201-53082-7. 
• Marek Cygan, Fedir V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh: Parameterized Algorithms. Springer International Publishing, 2016, ISBN 978-3-319-21274-6, doi:10.1007/978-3-319-21275-3. 
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms. Third Edition Auflage. MIT Press, Cambridge, Massachusetts; London, England 2009, ISBN 978-0-262-03384-8, 43.3 NP-completeness and reducibility - Circuit satisfiability, S. 1070–1078 (englisch). 

Temp

• $d_{G}(v)$ Grad des Koten $v$
• $n$ Knotenzahl
• $m$ Kantenzahl
• Datenstruktur#Speicher- und Rechenaufwand von Datenstrukturen

Datenstruktur	Speicher	Kante einfügen	Nachbarschaft (u,v) testen / löschen	Über alle Nachbarn von v iterieren	Einfügen Knoten	Löschen Knoten
Liste von Kanten	$\Theta (m)$	$\Theta (1)$	$\Theta (m)$	$\Theta (m)$	$\Theta (1)$	$\Theta (m)$
Adjazenzmatrix (dyn. Array)	$\Theta (n^{2})$	$\Theta (1)$	$\Theta (1)$	$\Theta (n)$	$\Theta (n)$	$\Theta (n)$
Inzidenzmatrix (dyn. Array)	$\Theta (n\cdot m)$	$\Theta (n)$	$\Theta (1)$	$\Theta (m)$	$\Theta (n+m)$	$\Theta (n+m)$
Adjazenzlisten (Knoten als verkette Liste)	$\Theta (n+m)$	$\Theta (n)$	$\Theta (n+d_{G}(v))$	$\Theta (n+d_{G}(v))$	$\Theta (1)$	$\Theta (n+m)$
Adjazenzlisten (Knoten als dyn. Array)	$\Theta (n+m)$	$\Theta (1)$	$\Theta (d_{G}(v))$	$\Theta (d_{G}(v))$	$\Theta (1)$	$\Theta (m)$