Engelsk   Dansk
Velkommen til Københavns Universitets kursuskatalog

NDAA09007U  Computability and Complexity Volume 2014/2015

Course information

LanguageEnglish
Credit7,5 ECTS
LevelFull Degree Master
Duration1 block
Placement
Block 2
Schedule
C (Mon 13-17 + Wednes 8-17)
Course capacityNo limit
Continuing and further education
Study boardStudy Board of Mathematics and Computer Science
Contracting department
  • Department of Computer Science
Course responsible
  • Christian Wulff-Nilsen (7-6e72726f72727d43676c316e7831676e)
Saved on the 04-12-2014
Content

 

In computing, there is continual tension between time usage and space usage, and what can be computed and what cannot be computed at all.  The purpose of this course is to explore these issues.

Content:

 

  • Regular languages
  • Context-free languages
  • Turing machines
  • Decidability
  • Reducibility
  • Complexity
  • Complexity classes (P, NP, PSPACE, EXPSPACE, L, and NL)
  • Intractability
Learning Outcome

At course completion, the successful student will have:

Knowledge of:

  • Computational models such as finite automata, pushdown automata, and Turing machines, the languages recognized by some of these models, and techniques for showing their limitations, such as the pumping lemmas for regular and for context-free languages.
  • The power and limits of algorithmic solvability, with focus on the computationally unsolvable Halting problem.
  • The reducibility method for proving that additional problems are computationally unsolvable.
  • How to analyze algorithms and their time and space complexity and how to classify problems according to the amount of time and space required to solve them.
  • Known computational problems that are solvable in principle but not in practice, i.e., intractable problems.


Skills in:

 

  • Reading and writing specifications of languages using computational models and grammars.
  • Classifying given languages according to type (regular, context-free, etc.) and algorithmic problems according to complexity (time and space).
  • Showing the equivalence between certain machine models.
  • Presenting the relevant constructions and proofs in writing, using precise terminology and an appropriate level of technical detail.


Competences to:

 

 

  • Reason reliably about languages and computational models and their strengths and limitations, and about the complexity of algorithms and algorithmic problems.
  • Analyze and design languages, abstract machines, and algorithms.
  • Communicate effectively about the theory of computation, both for accessing advanced topics from the research literature, and convincingly presenting the results of own work.

 

Literature

Is expected to be: Introduction to the Theory of Computation, Michael Sipser, second edition, Course Technology. See Absalon when the course is set up.

Teaching and learning methods
Lectures
Academic qualifications
The course "Logik i datalogi" or some math courses such as "Diskrete Matematiske strukturer (DIMS)" would be useful, but are not essential.
Sign up
Self Service at KUnet
Exam
Credit7,5 ECTS
Type of assessment
Written examination, 4 hours under invigilation
All books and notes may be brought to the exam.
Exam registration requirementsThe student must participate in lectures and solve exercises during the course. Assignments will be made each week and be due in the following week. 5 assignments out of the 7 must be completed by the due date and approved to qualify to take the exam.
AidWritten aids allowed
Marking scale7-point grading scale
Censorship formNo external censorship
Several internal examiners
Re-examThe re-exam will also be a 4 hours written exam, unless there are 10 or fewer students signed up, in which case it will be an oral exam (25 minutes oral exam without preparation).
Criteria for exam assesment

See learning outcome.

Workload
CategoryHours
Theory exercises9
Lectures36
Exam4
Preparation157
Total206
Saved on the 04-12-2014