Л. Д. Беклемишев, Д. С. Шамканов, В. Б. Шехтман Доказательства и вычисления



Дата30.07.2018
Размер9.31 Kb.

Л.Д. Беклемишев, Д.С. Шамканов, В.Б. Шехтман
Доказательства и вычисления
(весенний семестр 2013 г.)

В курсе будут рассматриваться вопросы математической логики, которые не вошли в программу обязательного курса "Логика и алгоритмы" (1й курс), но без которых нельзя невозможно себе представить знакомство с предметом.

Предполагается, что содержание из года в год будет варьироваться с тем, чтобы слушатели могли ознакомиться с разными темами.

Пререквизиты: теория множеств, логика высказываний и логика предикатов в объеме курса "Логика и алгоритмы".


В 2012-13 году в программу войдут следующие темы:
1) Разрешимые и неразрешимые алгоритмические проблемы. Проблема

равенства слов в полугруппах.

Проблема замощения.

2) Основы теории сложности вычислений. Сложностные классы P и NP,

NP-полнота. Стандартные NP-полные задачи.

3) Формальная арифметика. Представление вычислимых функций в арифметике.

Теорема о неподвижной точке.

4) Теоремы Гёделя о неполноте. Теорема Тарского о невыразимости



истинности. Неразрешимость арифметики и логики предикатов.


Поделитесь с Вашими друзьями:


База данных защищена авторским правом ©znate.ru 2017
обратиться к администрации

    Главная страница