1.Информация о дисциплине

1.1.Предисловие

Естественнонаучная дисциплина федерального компонента “Математическая логика и теория алгоритмов” (МЛТА) изучается всеми студентами института информационных систем и вычислительной техники. Она включает в себя следующие разделы: логика высказываний; логика предикатов; формальные теории; логическое программирование, модальная, нечеткая и темпоральная логики; элементы теории алгоритмов; верификация алгоритмов и программ, эффективность алгоритмов. При изучении дисциплины активно используются дистанционные образовательные технологии (ДОТ).

Студенты очной формы обучения изучают дисциплину МЛТА во втором семестре первого курса в объеме 28 лекционных часов. На практических занятиях в объеме 22 часа студенты решают типовые задачи и выполняют две аудиторные контрольныеработы.

Студенты очно-заочной и заочной форм обучения изучают дисциплину МЛТА во втором семестре второго курса в объеме 16 лекционных часов для очно-заочной и 8 лекционных часов для заочной форм обучения. Практические занятия в объеме 8 часов и 4 часов, соответственно, посвящены методике выполнения двух контрольныхработ, которыестудентывыполняютсамостоятельно.

ИтоговыйконтрольподисциплинеМЛТА – экзамен.

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

Задачи изучения дисциплины – усвоение основных положений математической логикиитеорииалгоритмов.

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

Знать основные понятия математической логики и теории алгоритмов, используемые в практической информатике и вычислительной технике.

Уметь применять их для решения задач анализа и проектирования аппаратных и программных средств вычислительной техники:

-выполнять равносильные преобразования и упрощения формул логики высказываний;

-определять отношения логического следования и эквивалентности формул логикивысказываний;

3

-применятьдляверификацииианализа функцийнесложныхпрограмм.

Иметьпредставление:

-об аксиоматических системах, формальных теориях и исчислениях;

-онечеткой, модальной и темпоральной логике;

-о методе резолюций и принципах логического программирования;

-об элементах теории и методах оценки сложности алгоритмов;

-о методах верификации алгоритмов и программ средствами логики. Владеть методами формализации предложений естественного языка средствами

логикивысказыванийилогикипредикатов.

Местодисциплинывучебномпроцессе.

Для изучения дисциплины МЛТА студенты должны быть знакомы с разделами дискретной математики, в которых рассматриваются понятия множества и отношения. Полученные знания прежде всего необходимы для изучения таких дисциплин, как “Теория автоматов”, “Схемотехника ЭВМ” и “Организация ЭВМ и систем”, а также используются для анализа и проектирования аппаратных и программных средств вычислительной техники.

1.2.Содержание дисциплины и виды учебной работы

1.2.1.Содержание дисциплины по ГОС

Логика высказываний; логика предикатов; исчисления; непротиворечивость; полнота; синтаксис и семантика языка логики предикатов. Клаузальная форма. Метод резолюций в логике предикатов. Принцип логического программирования. Темпоральная логика; нечеткая и модальная логики; нечеткая арифметика; алгоритмическая логика Ч. Хоара. Логика высказываний. Логическое следование, принцип дедукции. Метод резолюций. Аксиоматические системы, формальный вывод. Метатеория формальных систем. Понятие алгоритмической системы. Рекурсивные функции. Формализация понятия алгоритма; Машина Тьюринга. Тезис Черча; Алгоритмически неразрешимые проблемы. Меры сложности алгоритмов. Легко и трудноразрешимые задачи. Классы задач P и NP. NPполные задачи. Понятие сложности вычислений; эффективные алгоритмы. Основы нечеткой логики. Элементы алгоритмической логики.

4