Программа государственного экзамена по дискретной математике и информатике фивт, выпуск 2015 г



Скачать 46.16 Kb.
страница1/3
Дата27.04.2018
Размер46.16 Kb.
ТипПрограмма
  1   2   3

Программа государственного экзамена по дискретной математике и информатике ФИВТ, выпуск 2015 г.

1.Математическая логика и теория алгоритмов


2.Понятия множества и подмножества. Операции над множествами, тождества. Отображения и соответствия. Сравнение множеств по мощности. Теорема Кантора—Бернштейна. Счётные множества и их свойства. Теорема Кантора.

3.Булевы функции и пропозициональные формулы. Конъюнктивная и дизъюнктивная нормальные формы. Тавтологии. Исчисление высказываний: аксиомы, правила вывода, определение выводимости. Корректность исчисления высказываний. Лемма о дедукции. Полнота исчисления высказываний.

4.Языки первого порядка: сигнатуры, термы, правила построения формул. Интерпретации, оценки, определение истинности формулы. Выразимость предикатов.

5.Общезначимые формулы первого порядка. Исчисление предикатов: аксиомы и правила вывода. Корректность исчисления предикатов. Теорема Гёделя о полноте исчисления предикатов: различные формулировки и схема доказательства.

6.Машина Тьюринга. Вычислимые функции. Разрешимые и перечислимые множества. Неразрешимость проблем самоприменимости и остановки. Теорема Райса—Успенского (б/д). Теорема Клини о неподвижной точке (б/д). Существование программы, печатающей свой собственный текст.

7.Формальная арифметика. Моделирование машин Тьюринга в формальной арифметике. Теорема Гёделя о неполноте (б/д).

8.Лямбда-исчисление. Лямбда-термы и комбинаторы. Теорема Чёрча—Россера (б/д). Нумералы Чёрча. Комбинаторы, представляющие арифметические операции. Представление логических значений и операций. Комбинатор неподвижной точки.

9.Классы сложности и . -полнота.



Каталог: diht


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


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

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