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

Цели и задачи дисциплины

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

Краткое содержание дисциплины

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

Компетенции обучающегося, формируемые в результате освоения дисциплины

Выпускник должен обладать:

ОПК-1 Способен применять естественнонаучные и общеинженерные знания, методы математического анализа и моделирования, теоретического и экспериментального исследования в профессиональной деятельности
ОПК-7 Способен применять в практической деятельности основные концепции, принципы, теории и факты, связанные с информатикой