Математическая логика и теория алгоритмов / ДО 2017

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

В результате освоения дисциплины Вы будете:

  • знать основы логики высказываний, логики предикатов, теории алгоритмов, иметь представление о дедуктивных теориях и о сложности вычислений с помощью алгоритмов.
  • уметь применять формализм логики высказываний, логики предикатов, метод резолюций, алгоритм Тьюринга в задачах матлогики и теории алгоритмов.

Образовательная программа (ООП/ДОП)

Направления подготовки бакалавриата:

09.03.01 Информатика и вычислительная техника

Программа курса

(названия тем учебных недель)

Неделя

Вид деятельности

1

Тема 1. Основы теории множеств

2

Тема 2. Операции логики Буля

3

Тема 3. Методы доказательства в логике Буля

4

Тема 4.  Дизъюнктивная нормальная форма булевых функций

5

Тема 5. Совершенные конъюнктивная и полиномиальная нормальные формы. Совершенные нормальные формы для элементарных логических функций от двух аргументов

6

Тема 6 Минимизация логических функций методом Куайна

7

Тема 7.  Логическое следствие и правильные рассуждения в логике высказываний

8

Тема 8. Метод резолюций в логике высказываний: метод насыщения уровней, стратегия вычёркивания

9

Тема 9. Метод резолюций в логике высказываний: лок-резолюция, метод резолюций для хорновских дизъюнктов.

10

Тема 10 Предикаты и формулы логики предикатов

11

Тема 11.  Основные равносильности, содержащие кванторы

12

Тема 12.  Машина Тьюринга

13

Тема 13.  Примитивно-рекурсивные и общерекурсивные функции. Тезис Чёрча.

14

Обобщение результатов обучения

15

Экзамен (итоговое тестирование)

Длительность курса, количество часов, кредиты

15 недель, 108 часов, 3 кредита

Авторы курса

Стоянов Александр Кириллович, ктн, доцент ИШИТР, 

http://portal.tpu.ru:7777/SHARED/s/STO

Copyright ©2018.
Tomsk Polytechnic University, All rights reserved.