Инфоурок / Информатика / Другие методич. материалы / РАБОЧАЯ ПРОГРАММА УЧЕБНОЙ ДИСЦИПЛИНЫ ОП.11. ТЕОРИЯ АЛГОРИТМОВ

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


библиотека
материалов

ДЕПАРТАМЕНТ ОБРАЗОВАНИЯ ГОРОДА МОСКВА

ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

СРЕДНЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ ГОРОДА МОСКВЫ

КОЛЛЕДЖ СВЯЗИ №54













рабочая ПРОГРАММа



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



СПЕЦИАЛЬНОСТЬ 090905 Организация и технология защиты информации



по программе базовой подготовки



















Москва

2014



Протокол №_____


от «_____»___________2014г.


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


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

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



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


__________А.А.Юмаева

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


«______» _______ 2014г.










Разработал: Ф.И.Казиханов, преподаватель ГБОУ СПО Колледж связи №54







СОДЕРЖАНИЕ



стр.

  1. ПАСПОРТ рабочей ПРОГРАММЫ УЧЕБНОЙ ДИСЦИПЛИНЫ


4

  1. СТРУКТУРА и содержание УЧЕБНОЙ ДИСЦИПЛИНЫ

5

  1. условия реализации рабочей программы учебной дисциплины

9

  1. Контроль и оценка результатов Освоения учебной дисциплины

10









1. паспорт рабочей ПРОГРАММЫ УЧЕБНОЙ ДИСЦИПЛИНЫ

Теория алгоритмов

1.1. Область применения программы

Рабочая программа учебной дисциплины является частью основной профессиональной образовательной программы в соответствии с ФГОС по специальности СПО 090905 Организация и технология защиты информации.

1.2. Место учебной дисциплины в структуре основной профессиональной образовательной программы.

Дисциплина входит в профессиональный цикл, как общепрофессиональная дисциплина вариативной части

1.3. Цели и задачи дисциплины – требования к результатам освоения дисциплины:

В результате освоения дисциплины обучающийся должен

Уметь:

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

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

Знать:

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

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

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

1.4. Рекомендуемое количество часов на освоение программы дисциплины:

максимальной учебной нагрузки обучающегося 171час, в том числе:

обязательной аудиторной учебной нагрузки обучающегося 114 часов;

самостоятельной работы обучающегося 57 часов.


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

2.1. Объем учебной дисциплины и виды учебной работы


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

64

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

57

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


2.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




3. условия реализации рабочей программы дисциплины

3.1. Требования к материально-техническому обеспечению

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

Оборудование учебного кабинета: посадочные места, видеопроектор, интерактивная доска, электронные учебники по дисциплине.

3.2. Информационное обеспечение обучения

Перечень рекомендуемых учебных изданий, Интернет-ресурсов, дополнительной литературы

Основные источники:

  1. Игошин В.И. Математическая логика и теория алгоритмов. – М.: Академия, 2008.

  2. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. - М.: МЦНМО, 2001

Дополнительные источники:

  1. Марков А. А., Нагорный Н. М. Теория алгоритмов, изд. 2. М.: ФАЗИС, 1996

  2. Трахтенброт Б.А. Алгоритмы и вычислительные автоматы. М.: Сов. радио, 1974.


Интернет ресурсы:

  1. http://life-prog.ru/view_zam2.php?id=228&cat=5&page=17.

2. http://window.edu.ru/resource/651/45651/files/unn078.pdf

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

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

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

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

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

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

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

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

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

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

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




8

Только до конца зимы! Скидка 60% для педагогов на ДИПЛОМЫ от Столичного учебного центра!

Курсы профессиональной переподготовки и повышения квалификации от 1 400 руб.
Для выбора курса воспользуйтесь удобным поиском на сайте KURSY.ORG


Вы получите официальный Диплом или Удостоверение установленного образца в соответствии с требованиями государства (образовательная Лицензия № 038767 выдана ООО "Столичный учебный центр" Департаментом образования города МОСКВЫ).

Московские документы для аттестации: KURSY.ORG


Общая информация

Номер материала: ДБ-326039

Похожие материалы



Очень низкие цены на курсы переподготовки от Московского учебного центра для педагогов

Специально для учителей, воспитателей и других работников системы образования действуют 60% скидки (только до конца зимы) при обучении на курсах профессиональной переподготовки (124 курса на выбор).

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

Подайте заявку на интересующий Вас курс сейчас: KURSY.ORG