Arvutiteaduse instituut
  1. Kursused
  2. 2017/18 sügis
  3. Sissejuhatus teoreetilisse informaatikasse (LTAT.04.001)
EN
Logi sisse

Sissejuhatus teoreetilisse informaatikasse 2017/18 sügis

  • Pealeht (Home)
  • Loengud (Lectures)
  • Kodutööd (Homeworks)
  • Viited (Links)

Introduction to Theoretical Computer Science

Instructor: Vitaly Skachek
Assistant: Reimo Palm
Lecture: Monday 12:15 - 14:00, Ülikooli 17-219 (Paabel 219)
Practice: Thursday 12:15 - 14:00, Ülikooli 17-220 (Paabel 220)
Office hours:

  • Vitaly Skachek: Monday 15:15-16:15, Thursday 15:15-16:15
  • Reimo Palm: contact by email

Language of instruction: English

Note: The students in Computer Science curriculum, who started their Bachelor studies in Fall 2015/2016, are allowed to choose one course from MTAT.05.125 Introduction to Theoretical Computer Science and MTAT.06.008 Artificial Intelligence I as a part of the degree requirements. In a case of doubt, please check your eligibility with the study coordinator.

Final Exam

The date and time for the final exam is Thursday, December 21st, 12:00 - 14:00, in Paabel 220 (during the practise session, but we start 15 minutes earlier). The exam will cover the matrial of the last eight weeks (Turing machines and computability theory). Any printed and hand-written material is allowed in the exam. No electronic devices (phones, tablets, calculators, etc.) can be used.

Final exam on December 21st, 2017:

  • Exam in English
  • Exam in Estonian
  • Solutions in Estonian

Midterm Exam

Midterm exam on November 2nd, 2017:

  • Exam in English
  • Exam in Estonian
  • Solutions in Estonian

Literature

  • Michael Sipser, Introduction to the Theory of Computation
  • Jiri Matousek and Jaroslav Nesetril, An Invitation to Discrete Mathematics

Course description

This is a bachelor-level introductory course into the theory of computer science. The course will emphasize mathematical foundations of computer science, and will focus on analysis and proofs. The course will not focus on implementations and programming.

In the first few weeks we will briefly cover basic counting techniques in combinatorics. Then, approximately half of the semester will be devoted to the automata theory. The second half of the semester will be devoted to computational models, Turing machines and NP-hardness.

Grading policy

There will be a number of homeworks, the mid-term and final exams. The homeworks and exams are evaluated on the scale 0-100. The final grade is taken as a weighted average of homeworks and exams, and translated into "A"-"F" scale. The composition of the grade is: homeworks (30%), mid-term exam (30%) and final exam (40%). The homeworks will mainly contain questions of theoretical and mathematical nature, and typically will not include programming tasks.

Syllabus

The following is a preliminary list of topics (some deviations from this list are possible):

Part 1: Enumerative combinatorics

  • Permutations and combinations
  • Newton’s binomial theorem
  • Inclusion-exclusion principle

Part 2: Automata theory

  • Deterministic and non-deterministic finite automata
  • Regular expressions and regular languages
  • Context-free languages

Part 3: Computability theory

  • Turing machines
  • Undecidable problems
  • Equivalences between different models of Turing machines
  • SAT and Cook's theorem
  • Examples of NP-complete problems
  • Arvutiteaduse instituut
  • Loodus- ja täppisteaduste valdkond
  • Tartu Ülikool
Tehniliste probleemide või küsimuste korral kirjuta:

Kursuse sisu ja korralduslike küsimustega pöörduge kursuse korraldajate poole.
Õppematerjalide varalised autoriõigused kuuluvad Tartu Ülikoolile. Õppematerjalide kasutamine on lubatud autoriõiguse seaduses ettenähtud teose vaba kasutamise eesmärkidel ja tingimustel. Õppematerjalide kasutamisel on kasutaja kohustatud viitama õppematerjalide autorile.
Õppematerjalide kasutamine muudel eesmärkidel on lubatud ainult Tartu Ülikooli eelneval kirjalikul nõusolekul.
Tartu Ülikooli arvutiteaduse instituudi kursuste läbiviimist toetavad järgmised programmid:
euroopa sotsiaalfondi logo