Computability, Decidability, and Complexity

Course Information

Discipline Sheet: Fisa-EN_Tiplea(CDC) / Fisa-RO_Tiplea(CDC).

Course Goal: The course is intended for undergraduate students. Its purpose is to clarify the power and limitations of algorithmic computation. Specifically, we will try to answer questions such as:

• What is an algorithm?
• What are the limits of computation?
• Are there problems that no algorithm will ever solve?
• Are there problems that cannot be solved efficiently?
• How do we classify problems according to the difficulty of solving them?

These are all closely related to practical issues such as compiler design, program checking, computational intractability, approximability, and cryptography.

Prerequisites: The course does not require special prior knowledge. However, an acquaintance with the o, O, Ω, and Θ notation, as introduced in this site’s “Algebraic Foundations of Computer Science,” may be helpful.

Readings: Many excellent textbooks on computability, decidability, and complexity exist. However, the course follows its own path, so each lecture will end with a bibliographic list and study recommendations. The recommended literature will be easily accessible to all students.

Lectures, office hours, exam sessions:

• Teaching weeks and examination sessions: see the university calendar;
• Lectures: Thursday, 12-14, in C112;
• Seminar taught by the course instructor: Thursday, 14-16, in C309;
• Office hours: Tuesday, 12-14, in C301.

Grading:

• The evaluation is based on active class participation by exercise solving (40%) and four tests of a maximum of 50′ each (60%). You will get details during the first class;
• Please pay attention to the fact that you can retake only the tests in the re-examination session!

Course Staff

Instructor: Prof.dr. Ferucio Laurențiu ȚIPLEA, Department of Computer Science, “Alexandru Ioan Cuza” University of Iași, Romania, e-mail: ferucio dot tiplea at uaic dot ro or fltiplea at gmail dot com.

Course assistants: Ph.D. student Simona-Maria Lăzărescu. Check her web page or 1st-semester timetable for details on schedule!

Course Syllabus and Seminar Guide

The last section contains a guide for seminaries!

• Enrollment in this course closed on 10/31/2024.