на заседании кафедры математики, ТиМОМ

протокол № 2 от 12.10.2012 г.

зав. кафедрой _________________ Шебанова Л.П.

Примерные вопросы к экзамену по дисциплине «Математическая логика и теория алгоритмов»

2 курс, направление подготовки 050100.62 – Педагогическое образование

(профиль «Информатика»)

3 семестр, 2012-2013 уч. г., ОДО
Вопросы составил: к.ф.-м.н, доц. Валицкас А.И.

1. 
   Формулы исчисления высказываний. Таблицы истинности. Тождественно истинные, тождественно ложные и выполнимые формулы. Примеры.
   
2. 
   Равносильные формулы. Равносильные преобразования формул. Примеры.
   
3. 
   Конъюнктивная и дизъюнктивная нормальные формы. Примеры. Теорема о СДНФ и СКНФ.
   
4. 
   Основные понятия теории множеств. Примеры.
   
5. 
   Доказательство тождеств с множествами. Примеры.
   
6. 
   Понятие булевой алгебры. Основные свойства булевых алгебр.
   
7. 
   Понятие машины Тьюринга. Философский тезис Тьюринга. Примеры.
   
8. 
   Основные операции над машинами Тьюринга (композиция, ветвление, зацикливание). Примеры.
   
9. 
   Конструирование машин Тьюринга из стандартных. Примеры.
   
10. 
    Гёделева нумерация наборов и машин Тьюринга. Примеры.
    
11. 
    Функция, не вычислимая по Тьюрингу.
    
12. 
    Алгоритмически неразрешимые массовые проблемы.
    
13. 
    Примитивно рекурсивные функции и их основные свойства. Примеры.
    
14. 
    Частично рекурсивные функции и их основные свойства. Примеры.
    
15. 
    Совпадение классов функций, вычислимых по Тьюрингу, с классом частично рекурсивных функций. Философский тезис Чёрча.
    
16. 
    Формальная арифметика.
    
17. 
    Теорема Гёделя о неполноте формальной арифметики.
    

Для получения оценки “удовлетворительно” необходимо знать основные определения и формулировки теорем (по всему курсу), уметь приводить примеры и решать стандартные задачи.

Для получения оценки “хорошо” нужно, в дополнение к вышеизложенному, уметь доказывать основные результаты билета.

Для получения оценки “отлично” нужно, кроме прочего, доказать все теоретические результаты.

1. 
   Лекции И ПРАКТИКА
   
2. 
   е-ЛЕКЦИИ
   
3. 
   Игошин В.И. Задачник-практикум по математической логике. – М.: Просвещение, 1986.
   
4. 
   Игошин В.И. Математическая логика и теория алгоритмов. – М.: Издательский центр “Академия”, 2004.