Вопросы к экзамену по дисциплине «Математическая логика и теория алгоритмов» 2 курс, направление подготовки - davaiknam.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
Учебная программа Дисциплины б5 «Математическая логика и теория алгоритмов» 1 127.11kb.
Вопросы по курсу: Математическая логика и теория алгоритмов (2 курс) 1 30.21kb.
Вопросы к экзамену по курсу «Математическая логика и теория алгоритмов» 1 66.23kb.
Вопросы к экзамену по дисциплине "Математическая логика" 1 32.68kb.
Рабочая программа дисциплины «Математическая логика и теория алгоритмов»... 3 543.74kb.
Рабочая программа дисциплины Математическая логика и теория алгоритмов 1 115.26kb.
Учебно-методический комплекс по дисциплине теория алгоритмов 1 409.97kb.
Учебно-методический комплекс по дисциплине Б2 «Теория алгоритмов»... 8 1107.78kb.
Программа-минимум кандидатского экзамена по специальности 01. 1 37.04kb.
Кафедра: информатики и методики преподавания математики фио разработчиков... 1 46.98kb.
Программа дисциплины [Введите название дисциплины] для направления/... 1 197.04kb.
Программа вступительного экзамена по специальности 05. 13. 18 Математическое... 1 112.81kb.
Направления изучения представлений о справедливости 1 202.17kb.

Вопросы к экзамену по дисциплине «Математическая логика и теория алгоритмов» 2 курс - страница №1/1

Рассмотрено и утверждено

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

протокол № 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.





Даже воду пить неприятно, если ее прописал врач.
ещё >>