Рассмотрена

Разработана на основе Федерального

Предметной (цикловой)

государственного образовательного

комиссией ОПД

стандарта по специальности среднего

укрупненной группы   090000

профессионального образования

Протокол №_____                          

от «_____»___________2014г.                          

090905 Организация и технология защиты информации

Председатель предметной

(цикловой) комиссии

Заместитель директора по УМР

__________А.А.Юмаева      

____________И.Г.Бозрова

                                                                                 «______» _______ 2014г.

стр.

1. ПАСПОРТ РАБОЧЕЙ ПРОГРАММЫ УЧЕБНОЙ ДИСЦИПЛИНЫ

4

2. СТРУКТУРА И СОДЕРЖАНИЕ УЧЕБНОЙ ДИСЦИПЛИНЫ

5

3. УСЛОВИЯ РЕАЛИЗАЦИИ РАБОЧЕЙ ПРОГРАММЫ УЧЕБНОЙ ДИСЦИПЛИНЫ

9

4. КОНТРОЛЬ И ОЦЕНКА РЕЗУЛЬТАТОВ ОСВОЕНИЯ УЧЕБНОЙ ДИСЦИПЛИНЫ

10

Вид учебной работы

Объем часов

Максимальная учебная нагрузка (всего)

171

Обязательная аудиторная учебная нагрузка (всего)

114

в том числе:

 Практические занятия

64

Самостоятельная работа обучающегося (всего)

57

Промежуточная  аттестация в форме контрольной работы (3 семестр) и зачета (4 семестр)

Наименование разделов и тем

Содержание учебного материала, практические работы, самостоятельная работа обучающихся

Объем часов

Уровень освоения

1

2

3

4

Раздел 1. Элементы теории алгоритмов

80

Тема 1.1. Интуитивное представление об алгоритмах

2

Содержание учебного материала

8

Введение. Алгоритмы вокруг нас. Неформальное понятие алгоритма. Необходимость уточнения понятия алгоритма. Виды алгоритмов.

Эффективность алгоритмов.  Сходимость, сложность, надежность.

Самостоятельная работа №1.

13

1.Подготовка реферата на тему: «Основные определения теории алгоритмов»

2.Подготовка презентации к теме: «Виды и способы представления алгоритмов»

3.Поиск в сети интернет дополнительной информации.

Тема 1.2. Машина Тьюринга

2

Содержание учебного материала

16

Определение машины Тьюринга. Применение машин Тьюринга к словам. Конструирование машин Тьюринга. Вычислимые по Тьюрингу функции. Правильная вычислимость функций на машине Тьюринга. Композиция машин Тьюринга. Тезис Тьюринга (основная гипотеза теории алгоритмов). Машины Тьюринга и современные электронно-вычислительные машины. Контрольная работа.

Практические занятия.

30

1-2.  Применение машин Тьюринга к словам.

3-4. Вычислимые по Тьюрингу функции.

5-6. Правильная вычислимость функций на машине Тьюринга.

7-8. Композиция машин Тьюринга.

9-10. Конструирование машин Тьюринга.

11-12. Операции над машиной Тьюринга

13-14. Оценка сложности алгоритма. Временная сложность алгоритма.   Объемная сложность алгоритма.

15. Применение методов построения алгоритмов.

Самостоятельная работа №2.

13

1.Поиск в сети интернет дополнительной информации к теме: «Применение машины Тьюринга к словам».

2.Решение задач по образцу.

3.Подготовка реферата на тему: «Тезис Тьюринга (основная гипотеза теории алгоритмов)».

Раздел 2. Математические основы анализа алгоритмов.

91

Тема 2.1. Основные алгоритмы на графах.

2

Содержание учебного материала

10

Представление графов. Поиск в ширину. Поиск в глубину. Топологическая сортировка. Сильно связные компоненты.

Практические занятия.

20

16-17. Представление графов.

18-19. Поиск в ширину.

20-21. Поиск в глубину.

22-23. Топологическая сортировка.

24-25. Сильно связные компоненты.

Самостоятельная работа  №3.

15

1.Изучить тему: «Основные понятия и определения теории графов».

2.Подготовить презентацию к теме: «Топологическая сортировка».

3.Решение задач по темам: «Поиск в ширину», «Поиск в глубину»

Тема 2.2. Минимальные покрывающие деревья.

2

Содержание учебного материала

4

Построение минимального покрывающего дерева. Алгоритмы Крускала и Прима.

Практические занятия

8

26-27. Построение минимального покрывающего дерева

28-29. Алгоритмы Крускала и Прима.

Самостоятельная работа №4.

6

1.Поиск дополнительной информации по теме: «Алгоритм Крускала».

2.Решение дополнительных задач по теме: «Алгоритм Крускала».

Тема 2.3. Кратчайшие пути из одной вершины

2

Содержание учебного материала

12

Кратчайшие пути и релаксация. Алгоритм Дейкстры. Алгоритм Беллмана-Форда. Кратчайшие пути в ациклическом ориентированном графе. Ограничения на разности и кратчайшие пути. Итоговое занятие.

Практические занятия

6

30-31. Кратчайшие пути и релаксация.

32. Алгоритмы Дейкстры.

Самостоятельная работа №5.

10

1.Подготовить реферат на тему: «Алгоритм Дейкстры».

2.Решение дополнительных (более сложных) задач по теме: «Кратчайшие пути в ациклическом ориентированном графе».

3.Поиск в сети интернет дополнительной информации  на тему: «Алгоритм Беллмана-Форда».

Всего

171

Результаты обучения (освоенные умения, усвоенные знания)

Формы и методы контроля и оценки результатов обучения

Освоенные умения:

разрабатывать алгоритмы для конкретных задач;

определять сложность работы алгоритмов.

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

Усвоенные знания:

основных моделей алгоритмов;

методов построения алгоритмов;

методов вычисления сложности работы алгоритмов.

Экспертная оценка результатов деятельности студентов при выполнении и защите практических работ, тестирования, зачета.