Автор
Игошин В.И.
Место издания
Москва

Теория алгоритмов: учеб. пособие для студ. учреждений сред. проф. образования / В.И. Игошин. – М.: Издательский центр «Академия», 2013. – 320 с.
ISBN 978-5-7695-9362-8
Представлены алгоритмы на языке блок-схем и алгоритмическом языке. Рассмотрена на неформальном уровне сложность алгоритмов и массовых проблем вплоть до характеристики классов сложности Р, PN и класса NP – полных массовых проблем. На формально-логическом (абстрактном) уровне подробно изложены две формализации понятия алгоритма (машины Тьюринга и рекурсивные функции), доказана их эквивалентность. Рассмотрены основные теоремы общей (абстрактной) теории алгоритмов, теория разрешимых и перечислимых множеств, алгоритмически неразрешимые массовые проблемы, в частности, и в математической логике, и в математике.
Учебное пособие может быть использовано при изучении общепрофессиональной дисциплины ОП.08 «Теория алгоритмов» по специальности 230115 «Программирование в компьютерных системах» укрупненной группы специальностей 230000 «Информатика и вычислительная техника».
Для студентов учреждений среднего профессионального образования.