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

2.  Вычисление временной сложности как функции размера задачи.

Этапы выполнения расчетного задания:

1.  Изучение учебной и дополнительной литературы по теме работы (2 часа);

2.  Разработка алгоритма для решения задачи (5 часов);

3.  Написание, отладка и тестирование программы, реализующей предложенный алгоритм (7 часов);

4.  Оформление результатов работы и ее защиту (3 часа).

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

Пояснительная записка к расчетному заданию должна содержать:

1.  Титульный лист

2.  Содержание

3.  Введение

4.  Формализованную постановку задачи (0,5-1 стр);

5.  Доказательство NP-полноты задачи;

6.  Разработанный алгоритм ее решения в виде укрупненной блок-схемы или словесного описания;

7.  Описание функций, реализующих предложенный алгоритм;

8.  Результаты тестирования программы (в том числе, экранные формы в виде рисунков);

9.  Оценку временной сложности программы;

10.  Заключение (0,5-1 стр).

11.  Список использованных источников литературы.

Карта компетенций дисциплины приведена в таблицах 3.1 и 3.2 соответственно для направлений 090900 и 230100, компонентный состав дисциплины приведен в таблице 3.3.

Таблица 3.1 - Наименование компетенций дисциплины для направления 090900

Код компетенции	Формулировка компетенции
ОК-8	способность к обобщению, анализу, восприятию информации, постановке цели и выбору путей ее достижения, владеть культурой мышления
ОК-11	способность к саморазвитию, самореализации, приобретению новых знаний, повышению своей квалификации и мастерства
ОК-12	способность критически оценивать свои достоинства и недостатки, определять пути и выбрать средства развития достоинств и устранения недостатков
ПК-1	способность использовать основные естественнонаучные законы, применять математический аппарат в профессиональной деятельности, выявлять сущность проблем, возникающих в ходе профессиональной деятельности

Таблица 3.2 - Наименование компетенций дисциплины для направления 230100

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

Таблица 3.3 - Компонентный состав дисциплины

Модуль дисциплины (раздел, тема)	Результаты освоения дисциплины	Технологии формирования компетенций	Средства и технологии оценки	Объем в ЗЕТ
Модуль 1	Знает: - свойства алгоритма; - способы доказательства примитивной и частичной рекурсивности функций; - тезис Черча	Лекции Практические занятия Самостоятельная работа	Контрольный опрос	0,5
Умеет: - доказывать принадлежность функции к классу ПРФ или ЧРФ; - разрабатывать программу вычисления значения ПРФ или ЧРФ в соответствии с доказательством	Практические занятия Лабораторные работы Самостоятельная работа	Контрольный опрос Защита лабораторной работы
Владеет: - навыками использования формальных методов доказательства принадлежности функции к классу ПРФ или ЧРФ; - навыками разработки рекурсивной и нерекурсивной программ вычисления значения функции, заданной оператором примитивной рекурсии; - навыками оформления и представления результатов решения задачи	Выполнение лабораторной работы	Защита лабораторной работы
Модуль 2	Знает: - способы задания машины Тьюринга; - понятие вычислимости по Тьюрингу; - способы синтеза машин Тьюринга при вычислении композиции, суперпозиции, разветвления и повторения вычислимых функций	Лекции Практические занятия Самостоятельная работа	Контрольный опрос	0,5
Умеет: - осуществлять синтез машины Тьюринга, выполняющей правильную переработку цепочек; - осуществлять синтез машины Тьюринга, вычисляющей заданную функцию	Практические занятия Лабораторные работы Самостоятельная работа	Контрольный опрос Защита лабораторной работы
Владеет: - навыками синтеза машин Тьюринга; - навыками оформления и представления результатов решения задачи	Выполнение лабораторной работы	Защита лабораторной работы
Модуль 3	Знает: - понятие алгоритма Маркова; - эквивалентность алгоритмических моделей; - правила геделевской нумерации объектов; - неразрешимые проблемы теории алгоритмов	Лекции Практические занятия Самостоятельная работа	Контрольный опрос	0,5
Умеет: - разрабатывать алгоритмы Маркова	Лабораторные работы Практические занятия Самостоятельная работа	Контрольный опрос Защита лабораторной работы
Владеет: - навыками разработки алгоритмов Маркова ; - навыками оформления и представления результатов решения задачи	Выполнение лабораторной работы	Защита лабораторной работы
Модуль 4	Знает: - понятие размера задачи; - классы сложности, P, NP, NP-полные проблемы; - методы разработки эффективных алгоритмов решения прикладных задач	Лекции Практические занятия Самостоятельная работа	Контрольный опрос	0,5
Умеет: - разрабатывать эффективные алгоритмы решения задач; - оценивать временную сложность решения задачи и класс задачи; - использовать методы уменьшения временной сложности алгоритмов для решения задачи;	Практические занятия Лабораторные работы Самостоятельная работа	Контрольный опрос Защита лабораторной работы
Владеет: - навыками разработки эффективных алгоритмов решения задачи; - навыками оценки временной сложности алгоритмов; - навыками оформления и представления результатов решения задачи	Выполнение лабораторных работ Выполнение расчетного задания (090900)	Защита лабораторной работы Защита расчетного задания (090900)
Модуль 5	Знает: - понятие формулы при исчислении высказываний и предикатов; - тавтологии логики высказываний и предикатов; - понятие выводимости; - теоремы о дедукции исчисления высказываний и предикатов; - метод резолюций; - современные логические теории.	Лекции Практические занятия Самостоятельная работа	Контрольный опрос	1
Умеет: - выполнять равносильные преобразования формул логики высказываний и предикатов; - использовать правила вывода; - преобразовывать формулу логики предикатов к нормальной форме Сколема	Практические занятия Лабораторные работы Самостоятельная работа	Контрольный опрос Защита лабораторной работы
Владеет: - навыками выполнения преобразований формул логики высказываний и предикатов; - навыками осуществления логических выводов; - навыками оформления результатов решения задачи	Выполнение лабораторной работы Выполнение расчетного задания	Защита лабораторной работы Защита расчетного задания (090900)

Матрица распределения компетенций по разделам и темам дисциплины

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

№ темы/раздела учебной дисциплины	Кол-во часов	Формируемые компетенции	Примечание
Модуль 1	4	ОК-8, ОК-11, ОК-12, ПК-1	-
Модуль 2	2	ОК-8, ОК-11, ОК-12, ПК-1	-
Модуль 3	2	ОК-8, ОК-11, ОК-12, ПК-1	-
Модуль 4	4	ОК-8, ОК-11, ОК-12, ПК-1	-
Модуль 5	5	ОК-8, ОК-11, ОК-12, ПК-1	-

Матрица распределения компетенций по разделам и темам дисциплины

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

№ темы/раздела учебной дисциплины	Кол-во часов	Формируемые компетенции	Примечание
Модуль 1	4	ОК-1, ОК-10	-
Модуль 2	2	ОК-1, ОК-10	-
Модуль 3	2	ОК-1, ОК-10	-
Модуль 4	4	ОК-1, ОК-10	-
Модуль 5	5	ОК-1, ОК-10	-

3.1.2 Учебно-методическое и информационное обеспечение дисциплины