Базеева Н.А. Теория алгоритмов

Учебное пособие. — Под общ. ред. проф. М.И. Ломшина. — Саранск: Мордовский государственный университет им. Н.П. Огарёва, 2019. — 136 с. — ISBN 978-5-7103-3873-5.Рассматриваются основные разделы программы курса «Теория алгоритмов», соответствующие содержанию федерального государственного образовательного стандарта среднего профессионального образования «Программирование в компьютерных системах». Издание представляет собой комплекс теоретического материала и практических задач для закрепления полученных знаний, умений и навыков во время лекционных занятий.
Предназначено для студентов среднего профессионального образования.Предисловие.
Математические модели алгоритмов.
Основные понятия алгоритмизации.
Определение алгоритма. История термина.
Формальные свойства алгоритмов. Виды алгоритмов.
Способы описания алгоритмов.
Словесно-формульное описание алгоритмов.
Графическое описание алгоритмов. Блок-схемы.
Псевдокоды.
Алгоритмы и величины, линейные вычислительные алгоритмы, ветвление и циклы в вычислительных алгоритмах.
Эффективность алгоритмов.
Задача о Ханойской башне.
Тест.
Практическая работа №1.
Практическая работа №2.
Основные понятия алгоритмизации.
Структурная организация данных.
Комбинаторные алгоритмы.
Перебор и методы его сокращения.
Сортировка.
Алгоритмы на графах. Поиск в графе. Поиск в глубину. Поиск в ширину.
Алгоритмы на графах. Кратчайшие пути.
Динамическое программирование.
Тест.
Самостоятельная работа.
Практическая работа №3.
Практическая работа №4.
Основы теории алгоритмов и анализа их сложности.
Основные результаты теории алгоритмов.
Примитивно-рекурсивные функции.
Машина Тьюринга и функции, вычислимые по Тьюрингу.
Композиция машин Тьюринга.
Нормальные алгоритмы. Нумерация алгоритмов.
Алгоритмически неразрешимые проблемы.
Характеристики сложности вычислений. Классы сложности P и NP и их взаимосвязь. NP-полные задачи.
Практическая работа №5.
Практическая работа №6.
Практическая работа №7.
Итоговый тест.
Список использованных источников.