Рабочая программа по дисциплине "Теория алгоритмов" для специальности 09.02.03 "Программирование в компьютерных системах"

ОДОБРЕНА

ПЦК математических и

естественнонаучных дисциплин

Протокол №______от «___»________2016г.

Председатель ПЦК

__________Т.И. Кабалина

Рабочая программа учебной дисциплины разработана на основе Федерального государственного образовательного стандарта (далее – ФГОС) среднего профессионального образования (далее СПО) по специальности 09.02.03 «Программирование в компьютерных системах».

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

_____________Е.В. Путюнина

Разработчик: _________________ У.А.Никифорова, преподаватель ГБПОУ «НАМТ»

Рецензент: _________________ Г.Н. Атмайкина, преподаватель ГБПОУ «НАМТ»

4

5

9

11

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

Объем часов

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

96

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

64

в том числе:

лабораторные занятия

14

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

6

контрольные работы

-

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

32

Итоговая аттестация в форме экзамена

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

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

самостоятельная работа обучающихся, курсовая работ (проект) (если предусмотрены)

Объем часов

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

1

2

3

4

Раздел 1

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

84

Тема 1.1 Общие сведения об алгоритмах

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

6

Понятие алгоритма. Свойства алгоритмов.

Формы представления алгоритмов: словесная, формульно-словесная, графическая.

4

1-2

Самостоятельная работа обучающихся

Подготовка сообщений (презентаций) на темы:

• Эволюция языков программирования

• Классификация и характеристики современных языков программирования

2

Тема 1.2 Основные алгоритмические структуры

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

Линейные алгоритмы. Запись линейного алгоритма. Свойства и характеристики.

Решение алгоритмов линейной структуры.

Разветвляющиеся алгоритмы. Команда ветвления. Команда выбора.

Решение разветвляющихся алгоритмов.

Циклические алгоритмы. Циклы с предусловием.

Циклы с постусловием. Параметрические циклы.

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

Решение алгоритмов с параметрическим циклом.

Сложные циклы.

32

2-3

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

№1. Решение линейных и разветвляющихся алгоритмов.

№2. Решение циклических алгоритмов с предусловием и постусловием.

№3. Решение алгоритмов с параметрическим циклом.

6

Лабораторные работы

№1. «Разработка и построение блок-схем алгоритмов разветвляющейся структуры».

№2. «Разработка и построение блок-схем алгоритмов с использованием циклов с предусловием».

№2. «Разработка и построение блок-схем алгоритмов с использованием циклов с постусловием».

№4. «Разработка и построение блок-схем алгоритмов с использованием цикла с параметром».

№5. «Разработка и построение блок-схем алгоритмов с использованием одномерных массивов».

№6. «Разработка и построение блок-схем алгоритмов с использованием двумерных массивов».

№7. «Разработка и построение блок-схем алгоритмов с использованием двумерных массивов».

14

Самостоятельная работа обучающихся

Заполнить хронологическую таблицу фундаментальных достижений в области Теории алгоритмов

Подготовка рефератов на тему:

• Применение алгоритмов в повседневной жизни.

• Модели вычислений.

• Тезис Чѐрча-Тьюринга и алгоритмически неразрешимые проблемы.

• Современное состояние теории алгоритмов.

• Классы сложности.

• Волновой алгоритм. Двулучевой алгоритм. Четырехлучевой алгоритм.

Решение задач:

• Решение вариативных задач с линейным типом алгоритма.

• Решение вариативных задач с использованием ветвления.

• Решение вариативных задач циклической структуры.

• Маршрутный алгоритм.

• Геометрическая задача о лабиринте.

• Алгоритмы составления расписаний.

• Задача упаковки.

26

Раздел 2

Алгоритмы и структуры данных

12

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

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

8

Примеры известных алгоритмов.

Методы сортировки: выбором, вставкой, слиянием, обменом. Сортировка Шелла, быстрая сортировка (Хоара). Турнирная сортировка. Пирамидальная сортировка.

Методы поиска: последовательный, бинарный, фиббоначчиев, интерполяционный, по бинарному дереву, по бору, поиск хешированием.

Итеративные и рекурсивные алгоритмы.

Теория графов. Алгоритмы на графах.

Эвристические алгоритмы: волновой, двулучевой, четырехлучевой, маршрутный.

Моделирование с использованием генераторов случайных чисел.

Машина Тьюринга. Устройство машины Тьюринга. Машина Поста. Устройство машины Поста.

1-2

Самостоятельная работа обучающихся

Подготовка рефератов на тему:

• Алгоритмы поиска словесной информации

• Метод Крускала

• Метод Прима

• Метод Дейкстры

• Метод ветвей и границ

Составление кроссвордов на тему:

• Построение дерева решений

• Метод динамического программирования

• Алгоритм Флойда

• Алгоритм Йена

• Алгоритм Беллмана-Форда

Выполнение тестирования

4

Всего:

96

Результаты обучения

(освоенные умения, усвоенные знания)

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

Умения:

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

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

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

Знания:

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

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

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

Комбинированный: индивидуальный и фронтальный опрос в ходе аудиторных занятий, тестировании, контроль выполнения индивидуальных заданий, тестирование.