104.558 AKALG Finite Model Theory
This course is in all assigned curricula part of the STEOP.
This course is in at least 1 assigned curriculum part of the STEOP.

2022S, VO, 2.0h, 3.0EC

Properties

  • Semester hours: 2.0
  • Credits: 3.0
  • Type: VO Lecture
  • Format: Presence

Learning outcomes

After successful completion of the course, students are able to have a basic understanding of interactions of mathematical logic with computational complexity. They will unterstand the fundamentals of computation, be able to formalize computation and translate logical descriptions of computational problems into algorithms and vice-versa.

Subject of course

A logical description of the complexity class NP, some (un-)definability resutls for finite structures, Gödel's incompleteness theorem and the undecidability of the halting problem for Turing machines.

Teaching methods

The subject is presented on the blackboard.

Mode of examination

Oral

Additional information

Literature: L. Libkin, Elements of finite model theory

http://homepages.inf.ed.ac.uk/libkin/fmt/fmt.pdf

Lecturers

Institute

Course dates

DayTimeDateLocationDescription
Wed15:00 - 16:3002.03.2022 - 29.06.2022 Meeting Room, Freihaus, green area, 5th floorFinite Model Theory
AKALG Finite Model Theory - Single appointments
DayDateTimeLocationDescription
Wed02.03.202215:00 - 16:30 Meeting Room, Freihaus, green area, 5th floorFinite Model Theory
Wed09.03.202215:00 - 16:30 Meeting Room, Freihaus, green area, 5th floorFinite Model Theory
Wed16.03.202215:00 - 16:30 Meeting Room, Freihaus, green area, 5th floorFinite Model Theory
Wed23.03.202215:00 - 16:30 Meeting Room, Freihaus, green area, 5th floorFinite Model Theory
Wed30.03.202215:00 - 16:30 Meeting Room, Freihaus, green area, 5th floorFinite Model Theory
Wed06.04.202215:00 - 16:30 Meeting Room, Freihaus, green area, 5th floorFinite Model Theory
Wed27.04.202215:00 - 16:30 Meeting Room, Freihaus, green area, 5th floorFinite Model Theory
Wed04.05.202215:00 - 16:30 Meeting Room, Freihaus, green area, 5th floorFinite Model Theory
Wed11.05.202215:00 - 16:30 Meeting Room, Freihaus, green area, 5th floorFinite Model Theory
Wed18.05.202215:00 - 16:30 Meeting Room, Freihaus, green area, 5th floorFinite Model Theory
Wed25.05.202215:00 - 16:30 Meeting Room, Freihaus, green area, 5th floorFinite Model Theory
Wed01.06.202215:00 - 16:30 Meeting Room, Freihaus, green area, 5th floorFinite Model Theory
Wed08.06.202215:00 - 16:30 Meeting Room, Freihaus, green area, 5th floorFinite Model Theory
Wed15.06.202215:00 - 16:30 Meeting Room, Freihaus, green area, 5th floorFinite Model Theory
Wed22.06.202215:00 - 16:30 Meeting Room, Freihaus, green area, 5th floorFinite Model Theory
Wed29.06.202215:00 - 16:30 Meeting Room, Freihaus, green area, 5th floorFinite Model Theory

Examination modalities

An oral exam is held at the end of the semester.

Course registration

Not necessary

Curricula

Study CodeObligationSemesterPrecon.Info
860 GW Optional Courses - Technical Mathematics Mandatory elective

Literature

No lecture notes are available.

Previous knowledge

Basic knowledge of mathematical logic or of general algebra.

 

Accompanying courses

Language

German