РАБОЧАЯ ПРОГРАММА по дисциплине ОП 08 Теория алгоритмов .
рабочая программа на тему

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

Всего часов

Семестр

5

Аудиторные занятия (всего)

48

48

в том числе:

лекции (Л)

32

32

практические занятия (ПЗ)

16

16

Самостоятельная работа студентов (СРС) (всего)

24

24

в том числе:

подготовка презентационного материала

4

4

работа с конспектом лекций

20

20

Форма промежуточной аттестации:

Экзамен в 5 семестре

Общая трудоемкость

72

72

№

п/п

Раздел дисциплины

Семестр / неделя семестра

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

Формы текущего контроля успеваемости (по неделям семестра)

Формы промежуточной аттестации (по семестрам)

Л

ПЗ

СРС

1

Введение

5/1

2

-

-

2

Формализация понятия алгоритма, компьютерные модели

54 / 1-8

16

12

16

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

3

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

5 / 8-10

10

-

4

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

4

Сложность алгоритма

5/ 11-12

4

4

4

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

Промежуточная аттестация

экзамен

Итого

32

16

24

№ п/п

Наименование тем

Трудоёмкость

Содержание

Формируемые компетенции

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

Образовательные технологии

1

2

3

4

5

6

7

1.

Введение

2

Цели, задачи дисциплины. Место дисциплины «Теория алгоритмов» в теоретической информатике

ОК 1-10

Знать: Сущность и задачи дисциплины. Связь дисциплины «Теория алгоритмов» с другими учебными дисциплинами. Построение и логика данного курса. Роль дисциплины в профессиональной деятельности

Уметь: организовать свою  самостоятельную работу по изучению основной и дополнительной литературы.

Лекция

2.

Подходы  к уточнению понятия алгоритма

2

Интуитивное (неформальное) понятие алгоритма. Необходимость в формализации понятия «алгоритм». Подходы к формализации понятия «алгоритм».Основные модели алгоритмов. Методы построения алгоритмов;

ОК 1-10

ПК 1.1-1.2

Знать: подходы к формализации понятия «алгоритм»

Лекция-беседа

3.

Графическое представление алгоритмов

4

Различные способы представления алгоритмов. Конструкции для изображения блок-схем алгоритмов. Блок схема как ориентированный граф. Три типа вершин графа. Основные алгоритмические конструкции: композиция, альтернатива, итерация.

Практическое занятие № 1. Решение задач по созданию блок-схем с использованием основных алгоритмических конструкций.

ОК 1-10

ПК 1.1-1.2

Знать: различные способы представления алгоритмов; основные алгоритмические конструкции

Уметь: применять основные алгоритмические конструкции для изображения блок-схем алгоритмов

Комбинированный урок

4.

4.

Свойства алгоритмов

2

Свойства неформального толкования понятия алгоритма: дискретность, понятность, определенность(детерминированность), результативность, массовость.

ОК 1-10

ПК 1.1-1.2

Знать: свойства неформального толкования понятия алгоритма:

Комбинированный урок

5.

Понятие алгоритмического языка

4

Алгоритмический язык. Требования к записи алгоритма на алгоритмическом языке. Вспомогательный алгоритм. Встроенные(стандартные)вспомогательные алгоритмы. Рекурсивный алгоритм. Прямая и косвенная рекурсия. Алгоритмический язык исполнителя робот.

Практическое занятие № 2. Составление алгоритмов решения задач на алгоритмическом языке.  

ОК 1-10

ПК 1.1-1.2

Знать: понятие алгоритмического языка и вспомогательного алгоритма

Уметь: применять вспомогательные алгоритмы  для решения задач в среде алгоритмического языка

Комбинированный урок

6.

Машина Поста

4

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

Практическое занятие № 3. Составление программ для машины Поста

ОК 1-10

ПК 1.1-1.2

Знать: понятие машины Поста, команды машины Поста

Уметь: составлять программы для машины Поста

Комбинированный урок

7.

Машина Тьюринга

4

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

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

ОК 1-10

ПК 1.1-1.2

Знать: понятие машины Тьюринга, команды машины Тьюринга

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

Комбинированный урок

8.

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

4

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

Практическое занятие № 5. Составление нормальных алгоритмов Маркова.

ОК 1-10

ПК 1.1-1.2

Знать: понятие ассоциативного исчисления. Понятие нормального алгоритма Маркова. Способы композиции нормальных алгоритмов.

Уметь: составлять алгоритмы Маркова для решения прикладных задач

Комбинированный урок

9.

Рекурсивные функции

4

Формализация понятия алгоритма на основе теории рекурсивных функций. Простейшие функции. Частичная функция, вычислимая частичная функция, полувычислимая функция, невычислимая функция. Элементарные операции над частичными функциями: композиция, соединение, рекурсия. Частично-рекурсивная функция, примитивно-рекурсивная функция. Тезис Чёрча.

Практическое занятие № 6. Решение задач по вычислению значений функций.

ОК 1-10

ПК 1.1-1.2

знать:

• принцип равносильности теорий машин Тьюринга, машин Поста, нормальных алгоритмов Маркова и рекурсивных функций;

уметь:

• доказать  равносильность теорий машин Тьюринга, машин Поста, нормальных алгоритмов Маркова и рекурсивных функций;

Комбинированный урок

10.

Вычислимые функции

2

Понятие вычислимой функции. Теория вычислимых функций. Эффективная вычислимость. Эквивалентность утверждений «функция вычислима» и «существует алгоритм, вычисляющий функцию».

ОК 1-10

ПК 1.1-1.2

знать:

• понятия вычислимой функции и эффективной вычислимости;

Комбинированный урок

11.

Нумерация алгоритмов

2

Нумерация множества. Нумерация программ. Эффективно-счетное множество. Нумерация вычислимых функций.

ОК 1-10

ПК 1.1-1.2

знать:

• понятия нумерации множества, нумерации программ, нумерации алгоритмов;

Комбинированный урок

12.

Разрешимые множества и перечислимые множества

2

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

ОК 1-10

ПК 1.1-1.2

знать:

• понятие разрешимого множества;
• свойства разрешимого множества;
• понятие перечислимого множества;
• свойства перечислимого множества;

Комбинированный урок

13.

Примеры алгоритмически неразрешимых проблем в математике и информатике

2

Математические проблемы Д.Гильберта. Проблема «самоприменимости» алгоритма. Проблема распознавания выводимости. Тезис Чёрча.. Проблема «остановки». Метод сведения как метод доказательства алгоритмической неразрешимости

ОК 1-10

ПК 1.1-1.2

знать:

• алгоритмически неразрешимые проблемы в математике;
• алгоритмически неразрешимые проблемы в информатике;

Комбинированный урок

14.

Проблема универсального алгоритма

2

Понятие универсальной функции. Вычислимость универсальной функции. Теорема о существовании универсального алгоритма.

ОК 1-10

ПК 1.1-1.2

знать:

• понятие универсальной функции;
• понятие универсального алгоритма.

Комбинированный урок

15.

Понятие сложности алгоритма

4

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

Практическое занятие № 7. Вычисление сложности алгоритмов, имеющих линейную структуру.

ОК 1-10

ПК 1.1-1.2

знать:

•  понятие сложности алгоритма;
• понятие временной сложности;
• понятие теоретической сложности;
• понятие эффективности алгоритма;
• уметь:
• определять сложность алгоритма;
• приводить примеры алгоритмов, имеющих линейную сложность;

Комбинированный урок

16.

Анализ алгоритмов поиска

Анализ алгоритмов сортировки

4

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

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

Практическое занятие № 8 Определение сложности алгоритмов сортировки.

ОК 1-10

ПК 1.1-1.2

знать:

• зависимость сложности алгоритма от размерности задачи.
• зависимость сложности алгоритма от размерности задачи.

уметь:

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

Комбинированный урок

Итого:

48

В том числе:

Лекции

ПЗ

32

16

№

п/п

Наименование практических и семинарских занятий

№ раздела дисциплины

Объем в часах

1

2

3

4

Практическое занятие № 1. Решение задач по созданию блок-схем с использованием основных алгоритмических конструкций.

Раздел 1. Формализация понятия алгоритма, компьютерные модели.

2

Практическое занятие № 2. Составление алгоритмов решения задач на алгоритмическом языке.  

Раздел 1. Формализация понятия алгоритма, компьютерные модели.

2

Практическое занятие № 3. Составление программ для машины Поста

Раздел 1. Формализация понятия алгоритма, компьютерные модели.

2

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

Раздел 1. Формализация понятия алгоритма, компьютерные модели.

2

Практическое занятие № 5 Составление нормальных алгоритмов Маркова.

Раздел 1. Формализация понятия алгоритма, компьютерные модели.

2

Практическое занятие № 6. Решение задач по вычислению значений функций.

Раздел 1. Формализация понятия алгоритма, компьютерные модели.

2

Практическое занятие № 7. Вычисление сложности алгоритмов, имеющих линейную структуру.

Раздел 3. Сложность алгоритма

2

Практическое занятие № 8. Составление алгоритма поиска в неупорядоченном массиве максимального и минимального элементов одновременно Определение сложности алгоритмов сортировки.

Раздел 3. Сложность алгоритма

2

Итого

16

№

п\п

Разделы и темы рабочей программы самостоятельного изучения

Перечень домашних заданий и других вопросов для самостоятельного изучения

Сроки

выполнения

Объем в

часах

1

2

3

4

5

Составить хронологическую таблицу фундаментальных достижений (с указанием фамилий авторов и дат их жизни) в области теории алгоритмов

Написание  конспекта

сентябрь

4

Познакомиться с правилами оформления блок-схем алгоритмов в соответствии с ГОСТ 10.002-80 ЕСПД, ГОСТ 10.003-80 ЕСПД

Написание  конспекта

сентябрь

4

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

Написание  конспекта

октябрь

2

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

Написание  конспекта

октябрь

4

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

Написание  конспекта

ноябрь

2

Подготовить сообщение на тему «Теория множеств».

Написание  конспекта

ноябрь

4

Подготовить компьютерную презентацию по теме «Алгоритмически неразрешимые проблемы в информатике»

Подготовить презентацию

декабрь

4

Всего

24