Код: 317933

Назва:

Обчислюваність

Анотація: Теорія обчислень є важливим курсом при підготовці фахівців з прикладної математики та інформатики. Метою курсу є ознайомлення та оволодіння сучасними методами теорії обчислюваності та складності, застосуваннями теорії алгоритмів у різних задачах математики та комп'ютерних наук. В курсі розглядаються різні підходи до формалізації поняття алгоритму, доводиться еквівалентність деяких підходів. Розглядається поняття алгоритмічно обчислювальних функцій, розглядається клас функцій, обчислювальних за Тьюрінгом, загальнорекурсивних функції, функції, що обчислюються машинами з необмеженими регістрами. Формулюється теза Чорча і Тьюрінга, обговорюється існування алгоритмічно нерозв'язних задач. Обговорюється поняття складності алгоритмів і розглядаються класи складності задач. Курс потребує базових знань з таких курсів як дискретна математика, математична логіка та теорія алгоритмів. Computational theory is an important course in the education of applied mathematicians. The aim of the course is to get acquainted with and master modern methods of the theory of computability and complexity, applications of the theory of algorithms in various mathematics problems and computer science problems. The course requires basic knowledge of discrete mathematics, mathematical logic, and algorithm theory.