Вопросы к экзамену по дисциплине «Математическая логика и теория алгоритмов» 2 курс - страница №1/1
Рассмотрено и утверждено
на заседании кафедры математики, ТиМОМ
протокол № 2 от 12.10.2012 г.
зав. кафедрой _________________ Шебанова Л.П.
Примерные вопросы к экзамену по дисциплине «Математическая логика и теория алгоритмов»
2 курс, направление подготовки 050100.62 – Педагогическое образование
(профиль «Информатика»)
3 семестр, 2012-2013 уч. г., ОДО
Вопросы составил: к.ф.-м.н, доц. Валицкас А.И.
-
Формулы исчисления высказываний. Таблицы истинности. Тождественно истинные, тождественно ложные и выполнимые формулы. Примеры.
-
Равносильные формулы. Равносильные преобразования формул. Примеры.
-
Конъюнктивная и дизъюнктивная нормальные формы. Примеры. Теорема о СДНФ и СКНФ.
-
Основные понятия теории множеств. Примеры.
-
Доказательство тождеств с множествами. Примеры.
-
Понятие булевой алгебры. Основные свойства булевых алгебр.
-
Понятие машины Тьюринга. Философский тезис Тьюринга. Примеры.
-
Основные операции над машинами Тьюринга (композиция, ветвление, зацикливание). Примеры.
-
Конструирование машин Тьюринга из стандартных. Примеры.
-
Гёделева нумерация наборов и машин Тьюринга. Примеры.
-
Функция, не вычислимая по Тьюрингу.
-
Алгоритмически неразрешимые массовые проблемы.
-
Примитивно рекурсивные функции и их основные свойства. Примеры.
-
Частично рекурсивные функции и их основные свойства. Примеры.
-
Совпадение классов функций, вычислимых по Тьюрингу, с классом частично рекурсивных функций. Философский тезис Чёрча.
-
Формальная арифметика.
-
Теорема Гёделя о неполноте формальной арифметики.
ТРЕБОВАНИЯ К ОТВЕТУ
Для получения оценки “удовлетворительно” необходимо знать основные определения и формулировки теорем (по всему курсу), уметь приводить примеры и решать стандартные задачи.
Для получения оценки “хорошо” нужно, в дополнение к вышеизложенному, уметь доказывать основные результаты билета.
Для получения оценки “отлично” нужно, кроме прочего, доказать все теоретические результаты.
ЛИТЕРАТУРА
-
Лекции И ПРАКТИКА
-
е-ЛЕКЦИИ
-
Игошин В.И. Задачник-практикум по математической логике. – М.: Просвещение, 1986.
-
Игошин В.И. Математическая логика и теория алгоритмов. – М.: Издательский центр “Академия”, 2004.