Kursusoversigt
Kursusbeskrivelse
 Kursusnavn (dansk): Logik og beregnelighed Kursusnavn (engelsk): Logic and Computability Semester: Efterår 2003 Udbydes under: cand.it., internet- og softwareteknologi (int) Omfang i ECTS: 7,50 Kursussprog: Engelsk Kursushjemmeside: https://learnit.itu.dk Min. antal deltagere: 0 Forventet antal deltagere: 10 Maks. antal deltagere: 30 Formelle forudsætninger: The students should be able towork with sets and functionswork with integer and real numbersbe familiar with the rates of growth of functions (big O, ?, ?);perform mathematical proofsbe familiar with the concept of programmingAt IT-C, these prerequisites can be picked up at the courses Introduction to Algorithmsand Data Structures and/or IT-mathematics. Læringsmål: After the course the students should be able toverify validity of propositional and 1st order formulas;construct models of 1st order languages and 1st order theories;construct models with prescribed properties;distinguish between decidable and undecidable problems;evaluate the complexity of algorithmic problems;construct reductions between algorithmic problems. Fagligt indhold: The subjects of logic,computability, and complexity are inherently intertwined.This becomes already apparent from a glance at the history:The very first examples of NP-complete, PSPACE-complete, as well as other key examples of problems with extremalalgorithmic properties, came from logic (propositional,1st order, as well as other kinds thereof).Today, capturing complexity classes with particular variationsof logical languages is an increasingly popular pastime.Complexity theory creates an appropriate framework for,among other things, the questionHow complex is a given algorithmic problem? (as opposedto how complex an individual algorithm for solving that problem is),and in many important situations, provides a satisfyingly precise answer to this question.This course will offer a reasonably comprehensive introduction to logic,computability, and complexity. In particular, we intend to cover the following topics: basic logical calculi; models and theories; Turing machines; NP-complete problems; complexity-theoretic classifications of algorithmic problems; elements of recursion theory; Gödel incompleteness. Læringsaktiviteter: 6 x 45 minutes a week worth of freely interleaved lectures, discussions, and exercises. Eksamensform og -beskrivelse: X. experimental examination form (7-scale; external exam), 13-skala, Ekstern censurAt the (4-hour) exam, students will be offered a collection of small problems of theoretical nature. Litteratur udover forskningsartikler: C. H. Papadimitriou. Computational Complexity.Addison-Wesley, 1994.ISBN 0-201-53082-1.