Рабочая программа дисциплины Теория алгоритмов
рабочая программа по теме

СОГЛАСОВАНО

Заместитель директора по учебно -методической работе

_______________ Наважап Л.Б.

от «_____» _____________ 2015 г.

УТВЕРЖДАЮ

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

 по учебной работе

_______________ Чадамба А.А.

от «_____» _____________ 2015 г.

РАССМОТРЕНО

на заседании предметно-цикловой комиссии

от «_____» _____________ 2015 г.

Председатель:

__________________ Сырат А.-Х.Л.

стр.

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

4

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

5

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

8

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

10

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

Объем часов

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

120

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

80

в том числе:

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

–

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

40

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

–

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

–

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

40

в том числе:

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

–

выполнение домашнего задания

выполнение индивидуального задания

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

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

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

Объем часов

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

1

2

3

4

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

Тема 1.1. 

Интуитивное определение алгоритма.

Интуитивное (неформальное) понятие алгоритма. Необходимость в формализации понятия «алгоритм». Подходы к формализации понятия «алгоритм». Свойства неформального толкования понятия алгоритма: дискретность, понятность, определенность (детерминированность), результативность, массовость. Исполнитель. Система команд исполнителя. Среда исполнителя. Формы представления алгоритма: словесная, графическая, псевдокод. Алгоритмический язык. Требования к записи алгоритма на алгоритмическом языке. Основные базовые типы данных.

10

2

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

1. Словесная форма представления алгоритма.
2. Графическая форма представления алгоритма.
3. Представление алгоритма на псевдокоде.

8

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

1. Правила оформления блок-схем алгоритма.

4

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

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

Формализация понятия алгоритма в теории автоматов на примере машин Тьюринга. Понятие машины Тьюринга. Команды машины Тьюринга. Программа для машины Тьюринга. Примеры программ.

4

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

1. Составление программ для машины Тьюринга.

4

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

1. Принцип работы программы-эмулятора машины Тьюринга.

4

Тема 2.2. Машина Поста.

Формализация понятия алгоритма в теории автоматов на примере машин Поста. Понятие машины Поста. Команды машины Поста. Программа для машины Поста. Примеры программ.

4

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

1. Составление программ для машины Поста.

2

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

1. Принцип работы программы-эмулятора машины Поста.

4

Тема 2.3. Нормальные алгоритмы Маркова.

Формализация понятия алгоритма в теории автоматов на примере нормальных алгоритмов Маркова. Алфавит, буква, слово. Смежные слова. Понятие нормального алгоритма. Нормализуемый алгоритм. Способы композиции нормальных алгоритмов. Примеры нормальных алгоритмов.

4

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

1. Составление нормальных алгоритмов Маркова.

2

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

1. Принцип работы программы-эмулятора нормального алгоритма Маркова.

2

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

Основные алгоритмические конструкции: следование, ветвление, цикл. Вспомогательный алгоритм.  Понятие спецификации программного продукта.

4

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

1. Решение задач по составлению линейных алгоритмов.
2. Решение задач по составлению разветвляющихся алгоритмов.
3. Решение задач по составлению циклических алгоритмов.
4. Решение задач по составлению циклических алгоритмов.

10

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

1. Составление спецификации задачи  линейной структуры.
2. Решение задач по составлению сложных условий.
3. Составление спецификации задачи разветвляющейся структуры.
4. Составление спецификаций алгоритмической структуры «Выбор».
5. Составление спецификации задачи  циклической структуры.

10

Раздел 3. Методы построения алгоритмов

Тема 3.1. Типовые задачи поиска и сортировки данных.

Последовательный поиск в неупорядоченном массиве: алгоритм последовательного поиска в неупорядоченном массиве, алгоритм поиска минимального и максимального элемента в неупорядоченном массиве. Алгоритм бинарного поиска в упорядоченном массиве. Алгоритм обменной сортировки методом «пузырька». Сортировка выбором. Сортировка вставками.

8

2-3

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

1. Составление алгоритма поиска в неупорядоченном массиве.
2. Составление алгоритма сортировки в неупорядоченном массиве.
3. Некоторые методы решения типовых задач в одномерном массиве.
4. Некоторые методы решения типовых задач в двумерном массиве.

8

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

1. Составление спецификации задачи «Одномерные массивы».
2. Составление спецификации задачи «Двумерные массивы».

4

Тема 3.2. Рекурсивные функции.

Рекурсия. Структура рекурсивных подпрограмм. Рекуррентные соотношения.

2

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

1. Разработка рекурсивных алгоритмов.

2

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

1. Эвристические методы.

4

Раздел 4. Оценка сложности задач и алгоритмов

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

Понятие сложности алгоритма. Временная сложность. Теоретическая сложность: линейная, квадратичная, кубическая.  Эффективность алгоритма: эффективный алгоритм поиска в неупорядоченном массиве максимального и минимального элементов одновременно.

4

2

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

1. Решение задач на определение сложности алгоритма.
2. Анализ алгоритмов поиска.
3. Анализ алгоритмов сортировки.

6

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

1. Оценка сложности алгоритмов поиска.
2. Оценка сложности алгоритмов сортировки.

6

Всего:

120

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

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

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

1

2

Умения:

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

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

Знания: 

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

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