| Главная | Новости | Абитуриентам и школьникам | Учебный процесс | Аспирантура и докторантура | Научная деятельность | Фотогалерея | О кафедре | Партнёры |
Математическая логика и теория алгоритмов
ТРУДОЕМКОСТЬ ДИСЦИПЛИНЫ
Общая трудоемкость дисциплины составляет 4 ЗЕТ (144 час.).
ЦЕЛИ И ЗАДАЧИ ДИСЦИПЛИНЫ
Целью дисциплины является освоение студентами теоретических основ формальных систем и приобретения практических навыков
при формализации реальных систем и построении формальных непротиворечивых теорий.
МЕСТО ДИСЦИПЛИНЫ В СТРУКТУРЕ ООП
Дисциплина входит в вариативную часть математического и естественно-научного цикла и требует освоения
«Дискретной математики», «Программирования», «Информатики», используется далее при изучении «Экспертных систем»,
«Функционального и логического программирования», «Теории языков программирования и методов трансляции»,
«Системного анализа».
ТРЕБОВАНИЯ К УРОВНЮ ОСВОЕНИЯ ДИСЦИПЛИНЫ
Процесс изучения дисциплины направлен на формирование следующих общекультурных (ОК), профессиональных (ПК) и
профессионально-специализированных компетенций (ПСК):
- владеет культурой мышления, способен к обобщению, анализу, восприятию информации, постановке цели и выбору путей её достижения (ОК-1);
- использует основные законы естественнонаучных дисциплин в профессиональной деятельности, применяет методы математического анализа и моделирования, теоретического и экспериментального исследования (ОК-10).
Знать: основные понятия математической логики: формальной теории, исчисления; структуру исчислений высказываний и предикатов 1-го порядка; основные понятия теории алгоритмов: интуитивная концепция алгоритма, уточнения понятия алгоритма (машины Тьюринга и нормальные алгоритмы Маркова), понятия вычислимости, разрешимости, перечислимости; основные неразрешимые массовые проблемы.
Уметь: доказывать формулы в исчислении высказываний и предикатов 1-го порядка; составлять программы машин Тьюринга и схемы нормальных алгоритмов для решения простых вычислительных задач.
СОДЕРЖАНИЕ ДИСЦИПЛИНЫ. ОСНОВНЫЕ РАЗДЕЛЫ
Логика высказываний (пропозициональная логика). Высказывания и истинностные значения высказываний. Логические операции.
Формулы логики высказываний (пропозициональные формулы). Истинностные функции. Тавтологии. Эквивалентность формул.
Замена эквивалентным и двойственность. Дизъюнктивная и конъюнктивная нормальные формы. Классическое исчисление
высказываний. Аксиомы и правила вывода. Вывод формул и вывод формул из гипотез. Теорема о дедукции. Теоремы полноты и
непротиворечивости. Исчисление предикатов. Предикаты и кванторы. Предикатные формулы. Интерпретация предикатных формул.
Выполнимость, истинность. Логическая общезначимость. Аксиомы и правила вывода исчисления предикатов 1-го порядка.
Структура теории 1-го порядка. Нормальные алгоритмы и машины Тьюринга. Вычисление словарных функций нормальными алгоритмам
и машинами Тьюринга. Принцип нормализации и тезис Тьюринга. Универсальные алгоритмы. Теоремы сочетания. Разрешимость и
перечислимость. Неразрешимые массовые проблемы.
ВИДЫ УЧЕБНОЙ РАБОТЫ
Лекции, практические занятия.
ФОРМА АТТЕСТАЦИИ ПО ДИСЦИПЛИНЕ
Изучение дисциплины заканчивается экзаменом.
Методические материалы:
