Программа по дисциплине математическая логика и теория алгоритмов

Содержание

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

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

• группах, полугруппах, моноидах;
  

• кольцах и полях
  
• основных формулах комбинаторики
  
• многозначных логиках
  
• неклассических логиках;
  
• алгоритмах Маркова.
  

Форма обучения	Всего ауд. занятий	Самостоятельная работа
очная	54ч	31ч
очно-заочная(вечерняя)	18ч	67ч
заочная	12ч	73ч

1. Лихтарников Л.М., Сукачева Т.Г. Математическая логика – СПб: Лань, 2008
   

2. Шапорев С.Д.. Математическая логика - СПб: БХВ-Петербург, 2007
   

3. А.Н. Колмагоров, А.Г.Драгалин «Математическая логика» классический университетский учебник, МГУ им Ломоносова 2009
   

4. Ю.А. Алеев, С.Ф. Тюрин «дискретная математика и математическая логика» Москва, 2006