Документ взят из кэша поисковой машины. Адрес оригинального документа : http://sp.cs.msu.ru/info/1/voprivan.html
Дата изменения: Wed Feb 11 22:31:41 2015
Дата индексирования: Sat Apr 9 23:43:30 2016
Кодировка: Windows-1251
Программа курса «Алгоритмы и алгоритмические языки»

Программа курса лекций «Алгоритмы и алгоритмические языки» для студентов 1 курса. 2001/2002 учебный год
Лектор - профессор В. П. Иванников.

---

---

    Часть 1. Алгоритмы

  1. Алгоритмы. Основные свойства алгоритмов.
  2. Машина Тьюринга. Тезис Тьюринга.
  3. Диаграммы Тьюринга. Примеры машин Тьюринга.
  4. Варианты машин Тьюринга.
  5. Машины Тьюринга. Неразрешимость проблемы останова.
  6. Машина Маркова. Тезис Маркова. Примеры машин Маркова.
  7. Композиция машин Маркова.
  8. Машины Маркова. Неразрешимость проблемы самоприменимости.

    Часть 2. Алгоритмические языки. Язык Паскаль

  9. Синтаксис и семантика языка. Синтаксические диаграммы. Примеры.
  10. Имена и числа.
  11. Простые типы данных.
  12. Перечислимые и ограниченные типы данных.
  13. Регулярный, комбинированный и множественный типы данных.
  14. Файловый тип данных. Программа игры в лото.
  15. Операторы: составной, выбирающий, цикла, присоединения.
  16. Рекуррентные соотношения и итерации. Программирование рекуррентных соотношений.
  17. Процедуры и функции. Способы передачи параметров.
  18. Локализация имен. Коллизии.
  19. Итерации и рекурсии. Примеры рекурсивных и итеративных программ.
  20. Ссылочный тип данных.
  21. Структура программы.

    Часть 3. Структуры данных

  22. Абстрактные структуры. Отношения.
  23. Графы, деревья, линейные деревья(списки).
  24. Стек. Отображение на линейную и списковую памяти.
  25. Очередь. Отображение на линейную и списковую памяти.
  26. Внутренние таблицы. Операции с последовательными таблицами в векторной памяти. Оценки сложности.
  27. Таблицы, организованные как деревья сравнений. Деревья Фибоначчи.
  28. Деревья. Определение. Способы обхода дерева. Рекурсивные процедуры обхода деревьев.
  29. Деревья двоичного поиска. Процедуры поиска, вставки и удаления элемента для дерева двоичного поиска.
  30. Сбалансированные деревья. Характеристика различных видов сбалансированных деревьев (совершенные деревья, деревья Фибоначчи, АВЛ-деревья, 2-3 деревья, понятие красно-черных деревьев)
  31. АВЛ-деревья. Поиск. Оценка сложности.
  32. АВЛ-деревья. Включение. Оценка сложности.
  33. 2-3 деревья. Вставка элемента в 2-3 дерево. Удаление элемента из 2-3 дерева.
  34. Перемешанные таблицы. Поиск. Оценка сложности.
  35. Перемешанные таблицы. Включение и исключение. Коллизии.
  36. Поиск с возвращением. Задача расстановки ферзей.
  37. Метод решета. Решето Эратосфена.
  38. Метод „разделяй и властвуй“. Быстрая сортировка.

    Литература

  1. М. Минский. Вычисления и автоматы. – М.: «Мир», 1971.
  2. Т. Кормен, Ч. Лейзерсон, Р. Ривест. Алгоритмы: построение и анализ. – МЦНМО, 1999.
  3. Н. Вирт. Алгоритмы + структуры данных = программы. – М.: «Мир», 1985.
  4. К. Йенсен, Н. Вирт. Паскаль. Руководство для пользователя. – М.: «Финансы и статистика», 1989.
  5. В. Г. Абрамов, Н. П. Трифонов, Г. Н. Трифонова. Введение в язык Паскаль. – М.: «Наука», 1988.
  6. Д. Кнут. Искусство программирования для ЭВМ. Т.1. Основные алгоритмы. – М.: Издательский дом «Вильямс», 2000.
  7. Д. Кнут. Искусство программирования для ЭВМ. Т.2. Сортировка и поиск. – М.: Издательский дом «Вильямс», 2000.
  8. Г. Лорин. Сортировка и системы сортировки. – М.: «Наука», 1983.
  9. М. Сибуя, Т. Ямомото. Алгоритмы обработки данных. – М.: «Мир», 1986.
  10. П. Холл. Вычислительные структуры. Введение в нечисленное программирование. – М.: «Мир», 1978.
  11. Э. З. Любимский, В. В. Мартынюк, Н. П. Трифонов. Программирование. – М.: «Наука», 1980.
  12. А. Ахо, Д. Хопкрофт, Д. Ульман. Структуры данных и алгоритмы. – М.: Издательский дом «Вильямс», 2000.
---

---