Важнейшими фундаментальными компонентами профессиональных компетенций в сфере компьютерных наук и информационных технологий являются знания и умения в области математической логики и теории алгоритмов. В настоящее время специалисты в сфере компьютерных наук и информационных технологий готовятся не только в высших учебных заведениях (университетах), но и в образовательных учреждениях среднего профессионального образования (колледжи, техникумы). Чрезвычайно важно, чтобы их уровень подготовки в указанных областях соответствовал современным требованиям, выраженным в Федеральном государственном образовательном стандарте среднего профессионального образования по соответствующему профилю.
В связи с этим Издательский центр «Академия» (Москва) приступил к выпуску учебно-методических комплектов нового поколения по ряду специальностей. Эти комплекты включают традиционные и инновационные учебные материалы, позволяющие обеспечить изучение общеобразовательных и общепрофессиональных дисциплин и профессиональных модулей. Каждый комплект содержит учебники и учебные пособия, средства обучения и контроля, необходимые для освоения общих и профессиональных компетенций, в том числе с учетом требований работодателя.
Профессор кафедры геометрии В.И.Игошин приглашен Издательским центром «Академия» для работы над учебно-методическим комплектом по специальности 230115 «Программирование в компьютерных системах». Он занимается разработкой учебных пособий, входящих в указанный комплект и предназначенных для изучения общепрофессиональных дисциплин ОП.07 «Математическая логика» и ОП.08 «Теория алгоритмов». В конце 2013 г. увидело свет второе из указанных пособий:
В.И.Игошин. Теория алгоритмов: Учебное пособие для студ. учреждений сред. проф. образования. – М.: Издат. центр «Академия», 2013. – 320 с. [Гриф ФГАУ «ФИРО»: «Рекомендовано Федеральным государственным автономным учреждением «Федеральный институт развития образования» (ФГАУ «ФИРО») в качестве учебного пособия для использования в учебном процессе образовательных учреждений, реализующих программы среднего профессионального образования по специальности 230115 «Программирование в компьютерных системах», учебная дисциплина «Теория алгоритмов» ».]
Данное учебное пособие по теории алгоритмов состоит из двух частей. В первой части теория алгоритмов рассматривается с интуитивно-содержательной точки зрения; во второй части изучается формально-логическая (абстрактная) теория алгоритмов.
В главе I первой части сначала характеризуется неформальное (интуитивное) понятие алгоритма (подразделы 1.1 и 1.2), описываются два языка представления таких алгоритмов – язык блок-схем (подраздел 1.3) и алгоритмический язык (подраздел 1.4). Затем обсуждаются вопросы доказательства корректности (правильности) алгоритмов (подраздел 1.4). В заключение рассматриваются примеры алгоритмов, в основном, имеющих дело с играми и головоломками (подраздел 1.5).
Глава II первой части посвящается вопросам анализа сложности алгоритмов и массовых проблем на неформальном (интуитивно-содержательном) уровне. Сначала кратко описывается математический инструментарий, используемый при анализе алгоритмов на сложность (подраздел 2.1) и приводятся примеры анализа на сложность нескольких простых алгоритмов (подраздел 2.2). Затем в подразделах 2.3 и 2.4 подробно анализируются различные алгоритмы, решающие проблемы нахождения минимального и максимального элементов массива, а также проблему сортировки элементов массива. В подразделе 2.5 анализируются на сложность алгоритмы, решающие ряд практически важных массовых проблем на графах. Завершается глава II и первая часть подразделами 2.6 и 2.7, в которых рассматриваются способы сравнения и классификации массовых проблем по их сложности, выделяются различные классы сложности массовых проблем, важнейшими из которых являются классы P, NP и NP-полных массовых проблем.
Часть вторая посвящена формально-логической (абстрактной) теории алгоритмов. В главах III и IV описываются формализации понятий алгоритма и вычислимой функции – машины Тьюринга и рекурсивные функции, устанавливается их равносильность. В подразделе 5.1 главы V рассматриваются основные методы общей теории алгоритмов – метод нумераций и метод диагонализации (или диагональный метод Кантора). С их помощью устанавливаются фундаментальные результаты общей теории алгоритмов, доказанные С.Клини – теорема о параметризации (s-m-n-теорема), теорема об универсальной функции и теорема о неподвижной точке; обсуждаются применения этих теорем в теории и практике программирования (подраздел 5.2). Алгоритмической теории множеств (разрешимым и перечислимым множествам) посвящается подраздел 5.3. Здесь два классических способа задания множеств изучаются с точки зрения алгоритмической эффективности, конструктивности. Важность понятий разрешимости и перечислимости множеств для оснований математики связана с тем, что язык теории множеств является в известном смысле универсальным языком математики.
Завершают книгу главы VI и VII, в которых рассматриваются алгоритмически неразрешимые массовые проблемы – в теории алгоритмов и в математике. Сначала в качестве понятия, уточняющего понятие алгоритма, используется понятие машины Тьюринга (подраздел 6.1). Затем проблема алгоритмической разрешимости рассматривается в рамках общей теории алгоритмов (подраздел 6.2). В подразделе 7.1 главы VII рассматриваются алгоритмически неразрешимые проблемы в математической логике, важнейшей из которых является проблема разрешимости формализованного исчисления предикатов, неразрешимость которой доказал А.Чёрч в 1937 г. В подразделе 7.2 главы VII даётся краткий обзор алгоритмических проблем – неразрешимых и разрешимых – в различных разделах математики. Среди них – 10-я проблема Гильберта о разрешимости диофантовых уравнений, проблема тождества слов в полугруппах и в группах.
Теория алгоритмов развивалась в тесном взаимодействии с математической логикой. И изучается данный курс обычно после курса математической логики. Это, вне всякого сомнения, обусловлено тесной взаимосвязью алгоритмического и логического мышления человека, схожестью алгоритмов с процессами построения логических умозаключений и доказательств, использованием обеими дисциплинами формальных языков. Теория алгоритмов наряду с неотделимой от неё математической логикой являются фундаментальными теоретическими основаниями, на которых зиждутся теория и практика компьютеров, программирования и информатики. Ведь каждая компьютерная программа представляет собой выражение алгоритма решения задачи на одном из алгоритмических языков, которые тесно связаны с формализованными языками математической логики. Так что овладение основами теории алгоритмов является в настоящее время неотъемлемым компонентом образования всякого высококвалифицированного специалиста, имеющего дело с перечисленными областями.
В конце книги приведён обширный список литературы, разделённый по темам. Её можно использовать для более глубокого изучения вопросов, затронутых в этом пособии, а также для извлечения оттуда задач, без решения которых ни одна математическая дисциплина не может быть освоена на сколько-нибудь удовлетворительном уровне. Особенно в этом плане рекомендуется сборник задач: Игошин В.И. Задачи и упражнения по математической логике и теории алгоритмов. – М.: Издательский центр «Академия», 2005, 2008 (2-е изд.), 2008 (3-е изд.), 2010 (4-е изд.).
В настоящее время профессор В.И.Игошин работает над вторым учебным пособием, которое войдёт в учебно-методический комплект по специальности 230115 «Программирование в компьютерных системах», – по общепрофессиональной дисциплине ОП.07 «Математическая логика». Оно выйдет из печати в 2014 г.
