ВВЕДЕНИЕ. Любая дисциплина для описания очень сложных

Любая дисциплина для описания очень сложных

явлений обычно обращается к математике,

чтобы та помогла ей преодолеть эти сложности.

Программирование не является исключением.

Давид Грис

Следуя А. П. Ершову, мы употребляем термин «теоретическое программирование» в качестве названия математическойдисциплины, изучающей синтаксические и семантические свойства программ, их структуру, преобразования, процесс их составления и исполнения. Это словосочетание построено по аналогии с названиями таких наук, как теоретическая физика, теоретическая механика и т. д. В такой аналогии есть глубокий смысл: во всех случаях теоретическая научная дисциплина изучает фундаментальные понятия и законы основной науки и на основании обнаруженных закономерностей строит более частные математические модели исследуемых объектов, на которых ставит и решает прикладные задачи. В нашем случае ситуация усложняется еще тем, что объект моделирования – программа – уже представляет собой абстрактный объект.

В настоящее время сложились следующие основные направления исследований теоретического программирования.

1.Математические основы программирования. Основная цель исследований – развитие математического аппарата, ориентированного на теоретическое программирование, разработка общей теории машинных вычислений. Эта теория тесно соприкасается с теорией алгоритмов и вычислимых функций, теорией автоматов и формальных языков, логикой, алгеброй, с теорией сложности вычислений.

2.Теория схем программ. В этих работах внимание концентрируется на изучении структурных свойств и преобразований программ, а именно тех, которые отличают программы от других способов задания алгоритмов. Главным объектом исследования становится схема программы – математическая модель программы, в которой с той или иной степенью детализации отражено строение программы, взаимодействие составляющих ее компонентов.

3.Семантическая теория программ. Семантика программы или отдельных конструкций языков программирования – это их смысл, математический смысл для программиста и описание функционирования для машины. Этот раздел теоретического программирования изучает методы формального описания семантики программ, семантические методы преобразования и доказательства утверждений о программах для вычислительных машин. В частности, работы по методам проверки семантической правильности программ нацелены на автоматизацию их отладки и автоматический синтез программ.

4.Теория вычислительных процессов и структур (теория параллельных вычислений). Исследования в этой области направлены на разработку и обоснование новых методов программирования, прежде всего методов программирования параллельных процессов, взаимодействующих между собой. В частности, изучаются модели, структуры и функционирование операционных систем, методы распараллеливания алгоритмов и программ, ведется поиск новых архитектурных принципов конструирования вычислительных машин и систем на основе результатов и рекомендаций теоретического программирования и вычислительной математики.

5. Прикладные задачи теоретического программирования. Сюда в первую очередь относятся разработка и обоснование алгоритмов трансляции и алгоритмов автоматической оптимизации программ.

Две дисциплины государственного стандарта специальности 230105 – Программное обеспечение вычислительной техники и автоматизированных систем – «Теория языков программирования и методы трансляции» и «Теория вычислительных процессов» рассматривают основы теоретического программирования. Первая дисциплина охватывает первый и последний пункты нашей, не претендующей на классификационную строгость и полноту, рубрикации. Вторая дисциплина, составляющая предмет настоящего курса, раскрывает пункты 2 – 4.