|
| Udgave: |
Efterår 2012 NAT |
| Point: |
7,5 |
| Blokstruktur: |
2. blok |
| Skemagruppe: |
C |
| Fagområde: |
dat |
| Varighed: |
9 uger |
| Omfang: |
4 hours of lecture per week. One hour of discussion of exercises per week. |
| Institutter: |
Datalogisk Institut |
| Uddannelsesdel: |
Kandidat niveau |
| Kontaktpersoner: |
Christian Wulff-Nilsen |
| Andre undervisere: |
Nils Andersen |
| Skema- oplysninger: |
 Vis skema for kurset
Samlet oversigt over tid og sted for alle kurser inden for Lektionsplan for Det Naturvidenskabelige Fakultet Efterår 2012 NAT |
| Undervisnings- form: |
Lectures |
| Formål: |
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.
|
| Indhold: |
Regular languages, context-free languages, Turing machines, decidability, reducibility, complexity, complexity classes (P, NP, PSPACE, L, and NL), intractability
|
| Målbeskrivelse: |
1. Prove relationships between the various language classes (regular, context-free, non-context-free, decidable by Turing machines with various constraints).
2. Demonstrate the functioning of the various machines (DFA, NFA, pushdown automata, Turing machines) associated with these language classes.
3. Prove that various languages are or are not in various language classes (regular, context-free, non-context-free, decidable by Turing machines with various constraints).
4. Show that various problems are in various complexity classes (P, NP, PSPACE, EXPSPACE, L, and NL). |
| Lærebøger: |
Is expected to be: Introduction to the Theory of Computation, Michael Sipser, second edition, Course Technology. |
| Tilmelding: |
Via KUnet from May 15th to June 1st. |
| Faglige forudsætninger: |
The course "logik i datalogi" or some math courses such as DIMS would be useful, but are not essential. |
| Formelle krav: |
Ingen |
| Eksamensform: |
The 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. The exam will be a 4-hour written final exam, and will be graded using the 7-step scale with an internal censor. All books and notes may be brought to the exam.
Reexam: The 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).
|
| Eksamen: |
Skriftlig prøve den 23. januar 2013.
Reeksamen: Skriftlig prøve den 17. april 2013. Såfremt der er 10 eller færre tilmeldte til reeksamen, vil den blive afholdt som en mundtlig prøve.
|
| Kursus hjemmeside: |
 |
| Undervisnings- sprog: |
Kun engelsk
|
| Sidst redigeret: |
5/9-2012 |