Attribut:Reading suggestions
Aus International Center for Computational Logic
Reading suggestions for courses (in no particular language). This is a text.
A
Several general guides to writing and to scientific writing in computer science in particular exist.
The lecture most strongly uses:
* Justin Zobel: '''Writing for Computer Science''' 3rd edition, Springer, 2014.
Some relevant content is also found in:
* Christian W. Dawson: '''Projects in Computing and Information Systems: A Student’s Guide''' 2nd edition, Addison Wesley, 2009 +
Several general guides to writing and to scientific writing in computer science in particular exist.
The lecture most strongly uses:
* Justin Zobel: '''Writing for Computer Science''' 3rd edition, Springer, 2014.
Some relevant content is also found in:
* Christian W. Dawson: '''Projects in Computing and Information Systems: A Student’s Guide''' 2nd edition, Addison Wesley, 2009 +
*Stuart J. Russell and Peter Norvig. "Artificial Intelligence A Modern Approach" (3. edition ). Pearson Education, 2010.
*Zbigniew Michalewicz and David B. Fogel. "How to Solve It: Modern Heuristics", volume 2. Springer, 2004.
*Martin Gebser, Benjamin Kaufmann Roland Kaminski, and Torsten Schaub. "Answer Set Solving in Practice". Synthesis Lectures on Artificial Intelligence and Machine Learning. Morgan and Claypool Publishers, 2012.
*Michael Gelfond and Vladimir Lifschitz. "Classical negation in logic programs and disjunctive databases". New Generation Comput., 9(3–4):365–386, 1991.
*A.E. Eiben and J.E. Smith. "Introduction to Evolutionary Computing", Springer, 2003.
*Thomas Hammerl, Nysret Musliu and Werner Schafhauser. "Metaheuristic Algorithms and Tree Decomposition", Handbook of Computational Intelligence, pp 1255–1270, Springer, 2015.
*Hans L. Bodlaender, Arie M.C.A. Koster. "Treewidth computations I. Upper bounds", Comput. 208(2): 259–275, 2010.
*Georg Gottlob, Nicola Leone, and Francesco Scarcello. "Hypertree decompositions and tractable queries", Journal of Computer and System Sciences, 64(3):579–627, 2002. ISSN 0022-0000.
*Artan Dermaku, Tobias Ganzow, Georg Gottlob, Ben McMahan, Nysret Musliu, and Marko Samer. "Heuristic methods for hypertree decomposition", In Alexander Gelbukh and Eduardo F. Morales, editors, MICAI 2008: Advances in Artificial Intelligence, volume 5317 of LNCS, pages 1–11. Springer Berlin Heidelberg, 2008. ISBN 978-3-540-88635-8.
+
*Stuart J. Russell and Peter Norvig. "Artificial Intelligence A Modern Approach" (3. edition ). Pearson Education, 2010.
*Zbigniew Michalewicz and David B. Fogel. "How to Solve It: Modern Heuristics", volume 2. Springer, 2004.
*Martin Gebser, Benjamin Kaufmann Roland Kaminski, and Torsten Schaub. "Answer Set Solving in Practice". Synthesis Lectures on Artificial Intelligence and Machine Learning. Morgan and Claypool Publishers, 2012.
*Michael Gelfond and Vladimir Lifschitz. "Classical negation in logic programs and disjunctive databases". New Generation Comput., 9(3–4):365–386, 1991.
*A.E. Eiben and J.E. Smith. "Introduction to Evolutionary Computing", Springer, 2003.
*Thomas Hammerl, Nysret Musliu and Werner Schafhauser. "Metaheuristic Algorithms and Tree Decomposition", Handbook of Computational Intelligence, pp 1255–1270, Springer, 2015.
*Hans L. Bodlaender, Arie M.C.A. Koster. "Treewidth computations I. Upper bounds", Comput. 208(2): 259–275, 2010.
*Georg Gottlob, Nicola Leone, and Francesco Scarcello. "Hypertree decompositions and tractable queries", Journal of Computer and System Sciences, 64(3):579–627, 2002. ISSN 0022-0000.
*Artan Dermaku, Tobias Ganzow, Georg Gottlob, Ben McMahan, Nysret Musliu, and Marko Samer. "Heuristic methods for hypertree decomposition", In Alexander Gelbukh and Eduardo F. Morales, editors, MICAI 2008: Advances in Artificial Intelligence, volume 5317 of LNCS, pages 1–11. Springer Berlin Heidelberg, 2008. ISBN 978-3-540-88635-8.
+
*Stuart J. Russell and Peter Norvig. "Artificial Intelligence A Modern Approach" (3. edition ). Pearson Education, 2010.
*Zbigniew Michalewicz and David B. Fogel. "How to Solve It: Modern Heuristics", volume 2. Springer, 2004.
*Martin Gebser, Benjamin Kaufmann Roland Kaminski, and Torsten Schaub. "Answer Set Solving in Practice". Synthesis Lectures on Artificial Intelligence and Machine Learning. Morgan and Claypool Publishers, 2012.
*Michael Gelfond and Vladimir Lifschitz. "Classical negation in logic programs and disjunctive databases". New Generation Comput., 9(3–4):365–386, 1991.
*A.E. Eiben and J.E. Smith. "Introduction to Evolutionary Computing", Springer, 2003.
*Thomas Hammerl, Nysret Musliu and Werner Schafhauser. "Metaheuristic Algorithms and Tree Decomposition", Handbook of Computational Intelligence, pp 1255–1270, Springer, 2015.
*Hans L. Bodlaender, Arie M.C.A. Koster. "Treewidth computations I. Upper bounds", Comput. 208(2): 259–275, 2010.
*Georg Gottlob, Nicola Leone, and Francesco Scarcello. "Hypertree decompositions and tractable queries", Journal of Computer and System Sciences, 64(3):579–627, 2002. ISSN 0022-0000.
*Artan Dermaku, Tobias Ganzow, Georg Gottlob, Ben McMahan, Nysret Musliu, and Marko Samer. "Heuristic methods for hypertree decomposition", In Alexander Gelbukh and Eduardo F. Morales, editors, MICAI 2008: Advances in Artificial Intelligence, volume 5317 of LNCS, pages 1–11. Springer Berlin Heidelberg, 2008. ISBN 978-3-540-88635-8.
+
*Stuart J. Russell and Peter Norvig. "Artificial Intelligence A Modern Approach" (3. edition ). Pearson Education, 2010.
*Zbigniew Michalewicz and David B. Fogel. "How to Solve It: Modern Heuristics", volume 2. Springer, 2004.
*Martin Gebser, Benjamin Kaufmann Roland Kaminski, and Torsten Schaub. "Answer Set Solving in Practice". Synthesis Lectures on Artificial Intelligence and Machine Learning. Morgan and Claypool Publishers, 2012.
*Michael Gelfond and Vladimir Lifschitz. "Classical negation in logic programs and disjunctive databases". New Generation Comput., 9(3–4):365–386, 1991.
*A.E. Eiben and J.E. Smith. "Introduction to Evolutionary Computing", Springer, 2003.
*Thomas Hammerl, Nysret Musliu and Werner Schafhauser. "Metaheuristic Algorithms and Tree Decomposition", Handbook of Computational Intelligence, pp 1255–1270, Springer, 2015.
*Hans L. Bodlaender, Arie M.C.A. Koster. "Treewidth computations I. Upper bounds", Comput. 208(2): 259–275, 2010.
*Georg Gottlob, Nicola Leone, and Francesco Scarcello. "Hypertree decompositions and tractable queries", Journal of Computer and System Sciences, 64(3):579–627, 2002. ISSN 0022-0000.
*Artan Dermaku, Tobias Ganzow, Georg Gottlob, Ben McMahan, Nysret Musliu, and Marko Samer. "Heuristic methods for hypertree decomposition", In Alexander Gelbukh and Eduardo F. Morales, editors, MICAI 2008: Advances in Artificial Intelligence, volume 5317 of LNCS, pages 1–11. Springer Berlin Heidelberg, 2008. ISBN 978-3-540-88635-8.
+
*Stuart J. Russell and Peter Norvig. "Artificial Intelligence A Modern Approach" (3. edition ). Pearson Education, 2010.
*Zbigniew Michalewicz and David B. Fogel. "How to Solve It: Modern Heuristics", volume 2. Springer, 2004.
*Martin Gebser, Benjamin Kaufmann Roland Kaminski, and Torsten Schaub. "Answer Set Solving in Practice". Synthesis Lectures on Artificial Intelligence and Machine Learning. Morgan and Claypool Publishers, 2012.
*Michael Gelfond and Vladimir Lifschitz. "Classical negation in logic programs and disjunctive databases". New Generation Comput., 9(3–4):365–386, 1991.
*A.E. Eiben and J.E. Smith. "Introduction to Evolutionary Computing", Springer, 2003.
*Thomas Hammerl, Nysret Musliu and Werner Schafhauser. "Metaheuristic Algorithms and Tree Decomposition", Handbook of Computational Intelligence, pp 1255–1270, Springer, 2015.
*Hans L. Bodlaender, Arie M.C.A. Koster. "Treewidth computations I. Upper bounds", Comput. 208(2): 259–275, 2010.
*Georg Gottlob, Nicola Leone, and Francesco Scarcello. "Hypertree decompositions and tractable queries", Journal of Computer and System Sciences, 64(3):579–627, 2002. ISSN 0022-0000.
*Artan Dermaku, Tobias Ganzow, Georg Gottlob, Ben McMahan, Nysret Musliu, and Marko Samer. "Heuristic methods for hypertree decomposition", In Alexander Gelbukh and Eduardo F. Morales, editors, MICAI 2008: Advances in Artificial Intelligence, volume 5317 of LNCS, pages 1–11. Springer Berlin Heidelberg, 2008. ISBN 978-3-540-88635-8.
+
*Stuart J. Russell and Peter Norvig. "Artificial Intelligence A Modern Approach" (3. edition ). Pearson Education, 2010.
*Zbigniew Michalewicz and David B. Fogel. "How to Solve It: Modern Heuristics", volume 2. Springer, 2004.
*Martin Gebser, Benjamin Kaufmann Roland Kaminski, and Torsten Schaub. "Answer Set Solving in Practice". Synthesis Lectures on Artificial Intelligence and Machine Learning. Morgan and Claypool Publishers, 2012.
*Michael Gelfond and Vladimir Lifschitz. "Classical negation in logic programs and disjunctive databases". New Generation Comput., 9(3–4):365–386, 1991.
*A.E. Eiben and J.E. Smith. "Introduction to Evolutionary Computing", Springer, 2003.
*Thomas Hammerl, Nysret Musliu and Werner Schafhauser. "Metaheuristic Algorithms and Tree Decomposition", Handbook of Computational Intelligence, pp 1255–1270, Springer, 2015.
*Hans L. Bodlaender, Arie M.C.A. Koster. "Treewidth computations I. Upper bounds", Comput. 208(2): 259–275, 2010.
*Georg Gottlob, Nicola Leone, and Francesco Scarcello. "Hypertree decompositions and tractable queries", Journal of Computer and System Sciences, 64(3):579–627, 2002. ISSN 0022-0000.
*Artan Dermaku, Tobias Ganzow, Georg Gottlob, Ben McMahan, Nysret Musliu, and Marko Samer. "Heuristic methods for hypertree decomposition", In Alexander Gelbukh and Eduardo F. Morales, editors, MICAI 2008: Advances in Artificial Intelligence, volume 5317 of LNCS, pages 1–11. Springer Berlin Heidelberg, 2008. ISBN 978-3-540-88635-8.
+
*Stuart J. Russell and Peter Norvig. "Artificial Intelligence A Modern Approach" (3. edition ). Pearson Education, 2010.
*Zbigniew Michalewicz and David B. Fogel. "How to Solve It: Modern Heuristics", volume 2. Springer, 2004.
*Martin Gebser, Benjamin Kaufmann Roland Kaminski, and Torsten Schaub. "Answer Set Solving in Practice". Synthesis Lectures on Artificial Intelligence and Machine Learning. Morgan and Claypool Publishers, 2012.
*Michael Gelfond and Vladimir Lifschitz. "Classical negation in logic programs and disjunctive databases". New Generation Comput., 9(3–4):365–386, 1991.
*A.E. Eiben and J.E. Smith. "Introduction to Evolutionary Computing", Springer, 2003.
*Thomas Hammerl, Nysret Musliu and Werner Schafhauser. "Metaheuristic Algorithms and Tree Decomposition", Handbook of Computational Intelligence, pp 1255–1270, Springer, 2015.
*Hans L. Bodlaender, Arie M.C.A. Koster. "Treewidth computations I. Upper bounds", Comput. 208(2): 259–275, 2010.
*Georg Gottlob, Nicola Leone, and Francesco Scarcello. "Hypertree decompositions and tractable queries", Journal of Computer and System Sciences, 64(3):579–627, 2002. ISSN 0022-0000.
*Artan Dermaku, Tobias Ganzow, Georg Gottlob, Ben McMahan, Nysret Musliu, and Marko Samer. "Heuristic methods for hypertree decomposition", In Alexander Gelbukh and Eduardo F. Morales, editors, MICAI 2008: Advances in Artificial Intelligence, volume 5317 of LNCS, pages 1–11. Springer Berlin Heidelberg, 2008. ISBN 978-3-540-88635-8.
+
== Books ==
* Michael Sipser: Introduction to the Theory of Computation, 3rd edition, Cengage Learning, 2013
* Christos H. Papadimitriou: Computational Complexity, 1st edition, Addison-Wesley, 1994
* Sanjeev Arora and Boaz Barak: Computational Complexity A Modern Approach, Cambridge University Press, 2009
==Lecture Notes and Exercise Sheets==
* [[Medium:ATiCT2016-lecture-notes.pdf|Lecture Notes]]
* [[Medium:ATiCT2016-exercise-01.pdf|1. Sheet]]
* [[Medium:ATiCT2016-exercise-02.pdf|2. Sheet]]
* [[Medium:ATiCT2016-exercise-03.pdf|3. Sheet]]
* [[Medium:ATiCT2016-exercise-04.pdf|4. Sheet]]
* [[Medium:ATiCT2016-exercise-05.pdf|5. Sheet]]
* [[Medium:ATiCT2016-exercise-06.pdf|6. Sheet]]
* [[Medium:ATiCT2016-exercise-07.pdf|7. Sheet]]
* [[Medium:ATiCT2016-exercise-08.pdf|8. Sheet]]
* [[Medium:ATiCT2016-exercise-09.pdf|9. Sheet]]
* [[Medium:ATiCT2016-exercise-10.pdf|10. Sheet]] +
* Jörg Rothe (Ed.): Economics and Computation. An Introduction to Algorithmic Game Theory, Computational Social Choice, and Fair Division. Springer-Verlag Berlin Heidelberg (2016) (Part I: Playing Successfully)
** Lectures 1, 2, 6, 7, and 10
* Richard Alan Gillman, David Housman: Game Theory. A Modeling Approach. CRC Press (2019)
** Lectures 1, 2, 3, and 8
* Stuart J. Russell, Peter Norvig: Artificial Intelligence. A Modern Approach (Global Edition). Pearson (2021) (Chapter 6: Adversarial Search and Games)
** Lectures 4 and 5
* Noam Nisan, Tim Roughgarden, Éva Tardos, Vijay Vazirani (eds.): Algorithmic Game Theory. Cambridge University Press (2007)
** Lecture 8
* Michael R. Genesereth, Michael Thielscher: General Game Playing (Synthesis Lectures on Artificial Intelligence and Machine Learning) Morgan & Claypool Publishers (2014)
** Lectures 4, 5, and 9
* Bernhard von Stengel: Game Theory Basics. Cambridge University Press (2021)
+
* Jörg Rothe (Ed.): Economics and Computation. An Introduction to Algorithmic Game Theory, Computational Social Choice, and Fair Division. Springer-Verlag Berlin Heidelberg (2016) (Part I: Playing Successfully)
** Lectures 1, 2, 6, 7, 11, and 12
* Richard Alan Gillman, David Housman: Game Theory. A Modeling Approach. CRC Press (2019)
** Lectures 1, 2, 3, and 9
* Stuart J. Russell, Peter Norvig: Artificial Intelligence. A Modern Approach (Global Edition). Pearson (2021) (Chapter 6: Adversarial Search and Games)
** Lectures 4 and 5
* Todd W. Neller, Marc Lanctot: An Introduction to Counterfactual Regret Minimization. Self-published. (2013)
** Lecture 8
* Noam Nisan, Tim Roughgarden, Éva Tardos, Vijay Vazirani (eds.): Algorithmic Game Theory. Cambridge University Press (2007)
** Lecture 9
* Michael R. Genesereth, Michael Thielscher: General Game Playing (Synthesis Lectures on Artificial Intelligence and Machine Learning) Morgan & Claypool Publishers (2014)
** Lectures 4, 5, and 10
* Bernhard von Stengel: Game Theory Basics. Cambridge University Press (2021)
+
C
* '''Michael Sipser: ''Introduction to the Theory of Computation, International Edition''; 3rd Edition; Cengage Learning 2013'''
:: Introductory text that covers all basic topics in this lecture.
* Erich Grädel: ''Complexity Theory''; Lecture Notes, Winter Term 2009/10. Available online at https://logic.rwth-aachen.de/Teaching/KTQC-WS09/index.html.en
:: Free lecture notes with general overview of main results; more detailed than Sipser on oracles and alternation; main reference for randomized computation
* John E. Hopcroft and Jeffrey D. Ullman: ''Introduction to Automata Theory, Languages, and Computation''; Addison Wesley Publishing Company 1979
:: The ''Cinderella Book''; contains a lot of information not contained in most other books; the hierarchy of undecidable problems as well as Rice' characterization of recognizable properties of recognizable languages are from here.
* Christos H. Papadimitriou: ''Computational Complexity''; 1995 Addison-Wesley Publishing Company, Inc
:: Standard reference text for many advanced aspects on complexity theory; the proofs of the Linear Speedup Theorem, the Gap Theorem, and Ladner's Theorem as given in the lecture are from here
* Sanjeev Arora and Boaz Barak: ''Computational Complexity: A Modern Approach''; Cambridge University Press 2009
:: Extensive book covering the state of the art of Complexity Theory
* Michael R. Garey and David S. Johnson: ''Computers and Intractability''; Bell Telephone Laboratories, Inc. 1979
:: The classical book on Complexity Theory; contains a long list of problems with their complexities
+
* '''Michael Sipser: ''Introduction to the Theory of Computation, International Edition''; 3rd Edition; Cengage Learning 2013'''
:: Introductory text that covers all basic topics in this lecture.
* Erich Grädel: ''Complexity Theory''; Lecture Notes, Winter Term 2009/10. Available online at https://logic.rwth-aachen.de/Teaching/KTQC-WS09/index.html.en
:: Free lecture notes with general overview of main results; more detailed than Sipser on oracles and alternation; main reference for randomized computation
* John E. Hopcroft and Jeffrey D. Ullman: ''Introduction to Automata Theory, Languages, and Computation''; Addison Wesley Publishing Company 1979
:: The ''Cinderella Book''; contains a lot of information not contained in most other books; the hierarchy of undecidable problems as well as Rice' characterization of recognizable properties of recognizable languages are from here.
* Christos H. Papadimitriou: ''Computational Complexity''; 1995 Addison-Wesley Publishing Company, Inc
:: Standard reference text for many advanced aspects on complexity theory; the proofs of the Linear Speedup Theorem, the Gap Theorem, and Ladner's Theorem as given in the lecture are from here
* Sanjeev Arora and Boaz Barak: ''Computational Complexity: A Modern Approach''; Cambridge University Press 2009
:: Extensive book covering the state of the art of Complexity Theory
* Michael R. Garey and David S. Johnson: ''Computers and Intractability''; Bell Telephone Laboratories, Inc. 1979
:: The classical book on Complexity Theory; contains a long list of problems with their complexities
+
* '''Michael Sipser: ''Introduction to the Theory of Computation, International Edition''; 3rd Edition; Cengage Learning 2013'''
:: Introductory text that covers all basic topics in this lecture.
* Erich Grädel: ''Complexity Theory''; Lecture Notes, Winter Term 2009/10. Available online at https://logic.rwth-aachen.de/Teaching/KTQC-WS09/index.html.en
:: Free lecture notes with general overview of main results; more detailed than Sipser on oracles and alternation; main reference for randomized computation
* John E. Hopcroft and Jeffrey D. Ullman: ''Introduction to Automata Theory, Languages, and Computation''; Addison Wesley Publishing Company 1979
:: The ''Cinderella Book''; contains a lot of information not contained in most other books; the hierarchy of undecidable problems as well as Rice' characterization of recognizable properties of recognizable languages are from here.
* Christos H. Papadimitriou: ''Computational Complexity''; 1995 Addison-Wesley Publishing Company, Inc
:: Standard reference text for many advanced aspects on complexity theory; the proofs of the Linear Speedup Theorem, the Gap Theorem, and Ladner's Theorem as given in the lecture are from here
* Sanjeev Arora and Boaz Barak: ''Computational Complexity: A Modern Approach''; Cambridge University Press 2009
:: Extensive book covering the state of the art of Complexity Theory
* Michael R. Garey and David S. Johnson: ''Computers and Intractability''; Bell Telephone Laboratories, Inc. 1979
:: The classical book on Complexity Theory; contains a long list of problems with their complexities
+
* '''Michael Sipser: ''Introduction to the Theory of Computation, International Edition''; 3rd Edition; Cengage Learning 2013'''
:: Introductory text that covers all basic topics in this lecture.
* Erich Grädel: ''Complexity Theory''; Lecture Notes, Winter Term 2009/10. Available online at https://logic.rwth-aachen.de/Teaching/KTQC-WS09/index.html.en
:: Free lecture notes with general overview of main results; more detailed than Sipser on oracles and alternation; main reference for randomized computation
* John E. Hopcroft and Jeffrey D. Ullman: ''Introduction to Automata Theory, Languages, and Computation''; Addison Wesley Publishing Company 1979
:: The ''Cinderella Book''; contains a lot of information not contained in most other books; the hierarchy of undecidable problems as well as Rice' characterization of recognizable properties of recognizable languages are from here.
* Christos H. Papadimitriou: ''Computational Complexity''; 1995 Addison-Wesley Publishing Company, Inc
:: Standard reference text for many advanced aspects on complexity theory; the proofs of the Linear Speedup Theorem, the Gap Theorem, and Ladner's Theorem as given in the lecture are from here
* Sanjeev Arora and Boaz Barak: ''Computational Complexity: A Modern Approach''; Cambridge University Press 2009
:: Extensive book covering the state of the art of Complexity Theory
* Michael R. Garey and David S. Johnson: ''Computers and Intractability''; Bell Telephone Laboratories, Inc. 1979
:: The classical book on Complexity Theory; contains a long list of problems with their complexities
+
* '''Michael Sipser: ''Introduction to the Theory of Computation, International Edition''; 3rd Edition; Cengage Learning 2013'''
:: Introductory text that covers all basic topics in this lecture.
* Erich Grädel: ''Complexity Theory''; Lecture Notes, Winter Term 2009/10. Available online at https://logic.rwth-aachen.de/Teaching/KTQC-WS09/index.html.en
:: Free lecture notes with a general overview of main results; more detailed than Sipser on oracles and alternation; main reference for randomized computation
* John E. Hopcroft and Jeffrey D. Ullman: ''Introduction to Automata Theory, Languages, and Computation''; Addison Wesley Publishing Company 1979
:: The ''Cinderella Book''; contains a lot of information not contained in most other books; the hierarchy of undecidable problems as well as Rice' characterization of recognizable properties of recognizable languages are from here.
* Christos H. Papadimitriou: ''Computational Complexity''; 1995 Addison-Wesley Publishing Company, Inc
:: Standard reference text for many advanced aspects on complexity theory; the proofs of the Linear Speedup Theorem, the Gap Theorem, and Ladner's Theorem as given in the lecture are from here
* Sanjeev Arora and Boaz Barak: ''Computational Complexity: A Modern Approach''; Cambridge University Press 2009
:: Extensive book covering the state of the art of Complexity Theory
* Michael R. Garey and David S. Johnson: ''Computers and Intractability''; Bell Telephone Laboratories, Inc. 1979
:: The classical book on Complexity Theory; contains a long list of problems with their complexities
+
* '''Michael Sipser: ''Introduction to the Theory of Computation, International Edition''; 3rd Edition; Cengage Learning 2013'''
:: Introductory text that covers all basic topics in this lecture.
* Erich Grädel: ''Complexity Theory''; Lecture Notes, Winter Term 2009/10. Available online at https://logic.rwth-aachen.de/Teaching/KTQC-WS09/index.html.en
:: Free lecture notes with a general overview of main results; more detailed than Sipser on oracles and alternation; main reference for randomized computation
* John E. Hopcroft and Jeffrey D. Ullman: ''Introduction to Automata Theory, Languages, and Computation''; Addison Wesley Publishing Company 1979
:: The ''Cinderella Book''; contains a lot of information not contained in most other books; the hierarchy of undecidable problems as well as Rice' characterization of recognizable properties of recognizable languages are from here.
* Christos H. Papadimitriou: ''Computational Complexity''; 1995 Addison-Wesley Publishing Company, Inc
:: Standard reference text for many advanced aspects on complexity theory; the proofs of the Linear Speedup Theorem, the Gap Theorem, and Ladner's Theorem as given in the lecture are from here
* Sanjeev Arora and Boaz Barak: ''Computational Complexity: A Modern Approach''; Cambridge University Press 2009
:: Extensive book covering the state of the art of Complexity Theory
* Michael R. Garey and David S. Johnson: ''Computers and Intractability''; Bell Telephone Laboratories, Inc. 1979
:: The classical book on Complexity Theory; contains a long list of problems with their complexities
+
* '''Michael Sipser: ''Introduction to the Theory of Computation, International Edition''; 3rd Edition; Cengage Learning 2013'''
:: Introductory text that covers all basic topics in this lecture.
* Erich Grädel: ''Complexity Theory''; Lecture Notes, Winter Term 2009/10. Available online at https://logic.rwth-aachen.de/Teaching/KTQC-WS09/index.html.en
:: Free lecture notes with a general overview of main results; more detailed than Sipser on oracles and alternation; main reference for randomized computation
* John E. Hopcroft and Jeffrey D. Ullman: ''Introduction to Automata Theory, Languages, and Computation''; Addison Wesley Publishing Company 1979
:: The ''Cinderella Book''; contains a lot of information not contained in most other books; the hierarchy of undecidable problems as well as Rice' characterization of recognizable properties of recognizable languages are from here.
* Christos H. Papadimitriou: ''Computational Complexity''; 1995 Addison-Wesley Publishing Company, Inc
:: Standard reference text for many advanced aspects on complexity theory; the proofs of the Linear Speedup Theorem, the Gap Theorem, and Ladner's Theorem as given in the lecture are from here
* Sanjeev Arora and Boaz Barak: ''Computational Complexity: A Modern Approach''; Cambridge University Press 2009
:: Extensive book covering the state of the art of Complexity Theory
* Michael R. Garey and David S. Johnson: ''Computers and Intractability''; Bell Telephone Laboratories, Inc. 1979
:: The classical book on Complexity Theory; contains a long list of problems with their complexities
+
* '''Michael Sipser: ''Introduction to the Theory of Computation, International Edition''; 3rd Edition; Cengage Learning 2013'''
:: Introductory text that covers all basic topics in this lecture.
* Erich Grädel: ''Complexity Theory''; Lecture Notes, Winter Term 2009/10. Available online at https://logic.rwth-aachen.de/Teaching/KTQC-WS09/index.html.en
:: Free lecture notes with a general overview of main results; more detailed than Sipser on oracles and alternation; main reference for randomized computation
* John E. Hopcroft and Jeffrey D. Ullman: ''Introduction to Automata Theory, Languages, and Computation''; Addison Wesley Publishing Company 1979
:: The ''Cinderella Book''; contains a lot of information not contained in most other books; the hierarchy of undecidable problems as well as Rice' characterization of recognizable properties of recognizable languages are from here.
* Christos H. Papadimitriou: ''Computational Complexity''; 1995 Addison-Wesley Publishing Company, Inc
:: Standard reference text for many advanced aspects on complexity theory; the proofs of the Linear Speedup Theorem, the Gap Theorem, and Ladner's Theorem as given in the lecture are from here
* Sanjeev Arora and Boaz Barak: ''Computational Complexity: A Modern Approach''; Cambridge University Press 2009
:: Extensive book covering the state of the art of Complexity Theory
* Michael R. Garey and David S. Johnson: ''Computers and Intractability''; Bell Telephone Laboratories, Inc. 1979
:: The classical book on Complexity Theory; contains a long list of problems with their complexities
+
