Теория графов и математическая логика 1 семестр (68 час.)

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

1 семестр (68 час.)

1. Графы

1. 
   Основные понятия и алгоритмы (поиск в глубину, поиск в ширину, алгоритмы Дейкстры, Краскала и Демукрона).
   

2. 
   Гомоморфизмы и изоморфизы. Группа автоморфизмов.
   

3. 
   Пространство циклов неориентированного графа.
   

4. 
   Анализ размеченных орграфов
   
   1. 
      Постановка задачи и основная теорема
      

   2. 
      Транзитивное замыкание и задача о кратчайших расстояниях
      

   3. 
      Конечные автоматы
      
      1. 
         Алфвит, слово, язык. Полукольцо всех языков в заданном алфавите
         

      2. 
         Полукольцо регулярных языков
         

      3. 
         Анализ конечных автоматов
         

      4. 
         Синтез конечных автоматов. Теорема Клини
         

2. 
   

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

1. 
   Основы теории алгоритмов
   
   1. 
      Интуитивная концепция вычислимости
      

   2. 
      Машины Тьюринга
      

   3. 
      Нормальные алгорифмы
      

   4. 
      Универсальный нормальный алгорифм
      

   5. 
      Разрешимость и перечислимость.
      

   6. 
      Неразрешимые массовые проблемы
      
2. 
   Булевы функции
   

3. 
   Исчисление высказываний (непротиворечивость, полнота, разрешимость)
   

2 семестр (34 часа)

4. 
   Исчисление предикатов 1-го порядка
   
   1. 
      Определение и основные свойства (непротиворечивость, полнота, неразрешимость)
      

   2. 
      Теории 1-го порядка
      

   3. 
      Теорема Геделя о неполноте