Lectures

Lectures

Lectures Held on a Regular Basis

Please click here to find the lectures that are held on a regular basis. This information can be used to create a study plan. However, this information is tentative, i.e. always check the lectures of the current and next semester to keep the study plan up to date.

Lectures of the Current Semester

Module details on 'Algorithms and Complexity - Algorithms and Complexity'

CategoryTheoretical Foundations
TypeLecture
SiteHannover
LecturerProf. Dr. rer. nat. Vollmer, Heribert (Hannover)
Module Exam ID1020
ECTS-Credits5
Weekly Composition2L+1E
Required Hours of Work (presence / self-study)125 (42 / 83)
SemesterWinter (biyearly)
Teaching Methodsblackboard lecture, video recording
Module DescriptionWe will cover different complexity classes obtained using polynomial-time Turing machines operating under different acceptance criteria. The obtained classes are of current focal interest in the areas of algorithms and complexity, and are the most used for the complexity classifications of algorithmic tasks from areas such as network optimization, knowledge represenation, operations research, etc.
Module OutcomesCompetence in applications of phenomena of complexity. Ability of detailed analysis and complexity classification of algorithmic problems in terms of (completeness in) polynomial classes (deterministic, parallel, randomized) such as P, NP, PSPACE, PP, etc. Students are able to distinguish between several important complexity class degrees within the polynomial time hierarchy.
Recommended LiteratureLane Hemaspaandra und Mitsunori Ogihara, The complexity theory companion, Springer. Christos M. Papadimitriou. Computational Complexity. Addison-Wesley, 1994. Michael R. Garey und David S. Johnson. Computers and Intractability. Freeman, 1979. Michael Sipser, Introduction to the Theory of Computing. Itps Thomson Learning, 1997. John E. Hopcroft, Rajeev Motwani, und Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley Longman, 2006.
PrerequisitesFoundations on computational complexity, algorithms.
ExamOral exam, graded (25 min)
CommentsSee http://www.thi.uni-hannover.de/217.html?&L=1

Available Course Modes

In the following document you can get an overview about the available course modes that are offered in the ITIS Master's program: Course Modes