Программа как формализованное описание процесса обработки данных

Введение

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

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

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

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

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

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

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

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

Программа как формализованное описание процесса обработки данных

Целью программирования является описание процессов обработки данных (в дальнейшем - просто процессов). Данные - это представление фактов и идей в формализованном виде, пригодном для передачи и переработке в некоем процессе, а информация - это смысл, который придается данным при их представлении. Обработка данных - это выполнение систематической последовательности действий с данными. Данные представляются и хранятся на носителях данных. Совокупность носителей данных, используемых при какой-либо обработке данных, будем называть информационной средой. Набор данных, содержащихся в какой-либо момент в информационной среде, будем называть состоянием этой информационной среды. Процесс можно определить как последовательность сменяющих друг друга состояний некоторой информационной среды.

Описать процесс - значит определить последовательность состояний заданной информационной среды. Если мы хотим, чтобы по заданному описанию требуемый процесс порождался автоматически на компьютере, необходимо, чтобы это описание было формализованным. Такое описание называется программой. С другой стороны, программа должна быть понятной и человеку, так как и при разработке программ, и при их использовании часто приходится выяснять, какой именно процесс она порождает. Поэтому программа составляется на понятном человеку формализованном языке программирования, с которого она автоматически переводится на язык соответствующего компьютера с помощью другой программы, называемой транслятором. Программисту, прежде чем составить программу, приходится проделывать большую подготовительную работу по уточнению постановки задачи, выбору метода ее решения, выяснению специфики применения требуемой программы, прояснению общей организации разрабатываемой программы и многое другое.