Стандарт организации (стр. 2 )

Номер/индекс компетенции по ФГОС ВПО	Содержание компетенции	В результате изучения дисциплины обучающиеся должны:
знать	уметь	владеть
ОК-1	Владеет культурой мышления, способен к обобщению, анализу, восприятию информации, постановке цели и выбору путей её достижения	- предмет и задачи основных разделов математической логики и теории алгоритмов	- формализовать предложенную проблему и предложить пути ее решения; - формулировать, устно и письменно, важнейшие положения основных разделов математики и естественных наук, пояснять их примерами	- культурой мышления, способностью к обобщению, анализу и восприятию информации
ОК-10	Использует основные законы естественнонаучных дисциплин в профессиональной деятельности, применяет методы математического анализа и моделирования, теоретического и экспериментального исследования	- основные понятия и методы фундаментальных разделов математики, необходимые для разработки компонентов информационных систем; - основные понятия и методы математической логики и теории алгоритмов	- использовать математические методы для решения прикладных задач; - читать техническую литературу по своей специальности, использующую математический аппарат	- техникой основных математических действий, преобразований и вычислений - методами количественного анализа процессов обработки, поиска и передачи информации

2.5 Объем и виды занятий по дисциплине

Паспорт дисциплины

Кафедра __прикладной математики__________________________________________

(наименование кафедры, обеспечивающей преподавание дисциплины)

Дисциплина шифр Б.2.В.8 (направление 090900) Б.2.В.7 (направление 230100 ) (математический и естественно-научный цикл) «Математическая логика и теория алгоритмов»__________________________________ (шифр с указанием цикла подготовки, наименование дисциплины)

Статус дисциплины ___вариативная____________________________________________

(базовая, вариативная, вариативная по выбору, факультативная)

Направления

090900 Информационная безопасность (квалификация (степень) "бакалавр")________

(код и наименование направления или специальности)

230100 Информатика и вычислительная техника (квалификация (степень) "бакалавр")_

(код и наименование направления или специальности)

Профили направления 230100:

Вычислительные машины, комплексы, системы и сети

Системы автоматизированного проектирования

(наименование профиля)

Форма обучения_____очная________________________________________________

(очная, очно - заочная, заочная)

Объем дисциплины______108_______________________________________________

(общий объем дисциплины, час.)

Общая трудоёмкость дисциплины __3___ зачётных единицы

Распределение по видам занятий для направления 090900:

Се-местр	Учебные занятия (час.)	Наличие курсовых проектов (КП), курсовых работ (КР), расчетных заданий (РЗ)	Форма итоговой аттеста-ции (зачёт, экзамен)
Всего	Аудиторные	СРС
Всего ауди-торных	Лек-ции	Лабора-торные работы	Практи-ческие занятия (семина-ры)
4	108	51	17	17	17	57	1 РЗ	зачет

Распределение по видам занятий для направления 230100:

Се-местр	Учебные занятия (час.)	Наличие курсовых проектов (КП), курсовых работ (КР), расчетных заданий (РЗ)	Форма итоговой аттеста-ции (зачёт, экзамен)
Всего	Аудиторные	СРС
Всего ауди-торных	Лек-ции	Лабора-торные работы	Практи-ческие занятия (семина-ры)
4	108	51	17	17	17	57	-	зачет

3 Рабочая программа дисциплины

3.1 Содержание дисциплины

3.1.1 Тематический план дисциплины

Лекционный материал (17 часов) Литература основная [1-3] и дополнительная [4-7]

Модуль 1. Частично-рекурсивные функции как формальная модель алгоритма (4 часа) [1-4]

1.1. Неформальное понятие алгоритма. Свойства алгоритма.

1.2. Примитивно рекурсивные функции. Простейшие функции, оператор суперпозиции, оператор примитивной рекурсии. Вычисление функций, заданных при помощи оператора примитивной рекурсии.

1.3. Частично рекурсивные функции. Оператор минимизации. Ограниченный оператор минимизации. Быстро растущие функции. Функция Аккермана, диагональная функция Аккермана. В-мажорируемость примитивно рекурсивных функций. Частично рекурсивные функции. Тезис Черча.

Модуль 2. Машина Тьюринга как формальная модель алгоритма. Тезис Тьюринга. (2 часа) [1-4]

2.1. Определение машины Тьюринга. Конфигурация, непосредственный переход конфигурации в конфигурацию, процесс переработки цепочек. Способы задания машины Тьюринга.

2.2. Функции, вычислимые по Тьюрингу.

2.3. Композиция, суперпозиция, разветвление, повторение вычислимых функций.

Модуль 3. Нормальный алгоритм Маркова как формальная модель алгоритма. Эквивалентность алгоритмических моделей. Разрешимость алгоритмических проблем (2 часа) [1-3]

3.1. Определение алгоритма Маркова. Эквивалентность алгоритмических моделей.

3.2. Геделевская нумерация объектов. Неразрешимость проблем остановки, переводимости. Теорема Райса.

Модуль 4. Теория вычислительной сложности. Разработка эффективных алгоритмов (4 часа) [1-3]

4.1. Размер задачи. Понятия сложности как функции размера задачи. Легко и трудноразрешимые задачи. Порядок сложности. Классы сложности, P, NP и NP-полные проблемы. Примеры NP-полных проблем. Теорема Кука. Методы полного перебора. Оценка временной сложности программы для ЭВМ.

4.2. Разработка эффективных алгоритмов. Методы уменьшения временной сложности алгоритмов. Динамическое программирование. Методы отсечения.

Модуль 5. Логика высказываний и предикатов. Современные логические теории. (5 часов) [1-7]

5.1 Классическое исчисление высказываний. Формулы алгебры высказываний. Логическое следование формул. Правила логических умозаключений. Система аксиом и правила вывода. Теорема о дедукции для исчисления высказываний. Полнота и непротиворечивость в исчислении высказываний.

5.2 Операции над предикатами. Формулы логики предикатов. Тавтологии логики предикатов. Равносильные преобразования формул и логическое следование формул логики предикатов. Нормальная форма Сколема записи формулы логики предикатов. Формализованное исчисление предикатов. Аксиомы и правила вывода. Теорема о дедукции. Метод резолюций.

5.3 Современные логические теории. Нечеткая логика.

Практические занятия (17 часов) Литература основная [1-3] и дополнительная [4-7].

1. Примитивно-рекурсивные функции. (2 часа) [1-4]

2. Обычный и ограниченный операторы минимизации. Частично-рекурсивные функции (2 часа) [1-4]

3. Машины Тьюринга. (2 часа) [1-4]

4. Алгоритмы Маркова. (2 часа) [1-3]

5. Разработка рекурсивных алгоритмов. (2 часа) [1-3]

6. Оценка временной сложности программ. (2 часа) [1-3]

7. Логический вывод. Правила вывода. Преобразования формул логики высказываний и предикатов. (5 часов) [1-7].

Лабораторные работы (17 часов) Литература основная [1-3] и дополнительная [4-7].

1. Доказательство примитивной рекурсивности функции. Написание программы вычисления значения функции в заданной точке, соответствующее доказательству (2 часа) [1-4]

2. Использование ограниченного оператора минимизации при доказательстве примитивной рекурсивности функций. Доказательство частичной рекурсивности функции. (2 часа) [1-4]

3. Разработка машины Тьюринга (4 часа) [1-4]

4. Разработка алгоритма Маркова (2 часа) [1-3]

5. Рекурсивное программирование и оценка временной сложности алгоритма (4 часа) [1-3]

6. Правила вывода. Преобразования формул логики высказываний и предикатов. (3 часа) [1-7]

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

Самостоятельная работа включает в себя (57 час):

Для направления 090900 «Информационная безопасность»:

I.  Подготовка к защите лабораторных работ - 17 часов

II.  Выполнение расчетного задания - 17 часов

III.  Подготовка к контрольным опросам – 23 часа

Для направления 230100 «Информатика и вычислительная техника»:

I.  Подготовка к защите лабораторных работ - 34 часа

II.  Подготовка к контрольным опросам - 23 часа

Методические указания по выполнению лабораторных работ приведены в Приложении А, рекомендации по организации их выполнения – в п. 3.2.

Расчетное задание (17 часов) Литература основная [1-3] и дополнительная [4-7]

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

Тематика расчетного задания предусматривает:

1.  Разработку и программную реализацию алгоритма решения NP-полной задачи;