Трансляция - перевод программы, написанной на языке программирования, в последовательность машинных команд.
Схему работы компилятора можно представить в следующем виде.
Алгоритм - формальное описание последовательности действий, которое необходимо выполнить для решения задачи.
Свойства алгоритма
1. Дискретность. Алгоритм представляет процесс решения задачи как последовательность выполнения шагов-этапов. Для выполнения каждого этапа требуется определенное время, т.е. преобразование исходных данных в результат происходит дискретно во времени.
2. Определенность (детерминированность). Каждое правило алгоритма должно быть четким и однозначным. Отсюда выполнение алгоритма носит механический характер.
3. Результативность (финитность, конечность). Алгоритм должен приводить к решению задачи за конечное число шагов.
4. Массовость. Алгоритм решения задачи разрабатывается в общем виде, т.е. он должен быть применим для некоторого класса задач, различающихся исходными данными (область применимости алгоритма).
Язык блок-схем – способ формального описания алгоритмов
алгоритмов
Основные элементы блок схем:
1. Обработка данных (вычисление, пересылка и т.п.)
2. Вызов процедуры
3. Проверка условия
4. Соединительные линии и их объединение.
5. Ввод-вывод данных
6. Точки связи или соединители
7. Начало, завершение программы или подпрограммы
8. Комментарий
Основные (базовые) структуры алгоритмов – это ограниченный набор стандартных способов соединения отдельных блоков или структур блоков для выполнения типичных последовательностей действий. Доказано, что программу для любой простой логической задачи можно составить из структур следование, разветвление и повторение (цикл).
Эти базовые структуры были положены в основу технологии структурного программирования. Эта технология для разработки сложных программ рекомендует разбивать (декомпозировать) программу на подпрограммы (процедуры), решающие отдельные подзадачи, т.е. базируется на процедурной декомпозиции.
Простая программа - алгоритм, для которого:
• Существует единственный вход и единственный выход.
• Для каждого элемента алгоритма существует путь от входа к выходу через этот элемент (т.е. алгоритм не содержит бесконечных циклов и не содержит бесполезных (недостижимых) фрагментов).
Примеры простой и непростых программ
Простая программа
Бесконечный цикл
Недостижимый фрагмент
Основные (базовые) структуры алгоритмов и их производные
Следование последовательное выполнение действий (блоков).
Цикл «До» (с постусловием) - тело цикла (блок 2) выполняется до тех пор, пока условие (блок 3) не станет истинным.
Цикл «Пока» (с предусловием) - пока не будет нарушено условие (блок 3), осуществляется повторение тела цикла (блок 2).
Разветвление - применяется, когда в зависимости от условия требуется выполнить либо одно действие, либо другое.
Обход - частный случай разветвления, когда одна ветвь не содержит ни каких действий.
Множественный выбор - обобщение разветвления, когда в зависимости от значения переменной I выполняется одно из нескольких действий.
Альтернативный способ описания логики программы на этапе проектирования – использование псевдокода (или языка проектирования программ PDL – Process Design Language). Он занимает промежуточное положение между естественным языком и языком программирования и состоит из внешнего синтаксиса и внутреннего синтаксиса.
Внешний синтаксис – заданный набор операторов, построенных по образцу языков программирования и описывающий логику программы. Внешний синтаксис соответствует основным структурам алгоритмов. Кроме того, к внешнему синтаксису также относятся процедуры и модули.
Процедура – это хранимые в памяти машины подпрограммы, которые могут вызываться для выполнения из различных мест основной программы, либо из других процедур. Она вызывается и выполняется до завершения без сохранения внутренних данных.
Модуль – это несколько процедур, организованных в систему для удобства работы пользователя. Модуль имеет доступ к общим данным, которые сохраняются между последовательными вызовами модуля.
Внутренний синтаксис – общий, обычно специально не определяемый синтаксис, пригодный для описания задач в данной области. Практически любое предложение, написанное на естественном языке, либо на специализированном языке (например, математические формулы) может быть использовано.
- Следование. Записываются последовательно операции одна под другой. Для отделения части последовательности операторов используются операторы – do…end-do.
первая операция
вторая операция
do
третья операция
end-do
- Индексная последовательность (цикл по счетчику). Цикл с заранее определенным числом шагов (среднее между обычными последовательностью и классическим циклом).
for
индексный список
do
do-часть
end-do
- Цикл-До. Операции структуры, включая модификацию until-теста, выполняются один или более раз до тех пор, пока until-тест не примет значение истина;
do
do-часть
until
until-тест
end-do
Операторы внешнего синтаксиса псевдокода:
- Цикл-Пока. Do-часть выполняется пока while-тест имеет значение истина. Do-часть модифицирует условие while-теста для того, чтобы окончить вычисления.
while
while-тест
do
do-часть
end-do
- Разветвление. Если…то…иначе
if
if-тест
then
then-часть
else
else-часть
end-if
- Множественный выбор
case
список 1
case-часть 1
список 2
case-часть 2
…список n
case-часть n
else
else-часть
end-case
Алгоритмы вычисления суммы квадратов первых N целых чисел с использованием псевдокода и языка блок-схем
Ввести Число слагаемых
Сумма = 0
Номер = 1
do
Сумма = Сумма + Номер2
Увеличить Номер на единицу
Until
Номер > Число слагаемых
end-do
Напечатать Сумму
Помимо совокупности управляющих структур, важным аспектом структурного программирования является организация данных, участвующих в решении проблемы. Структура программы и строение данных неразрывно связаны.
«Программа – это конкретное, основанное на некотором реальном представ-лении и строении данных, воплощение абстрактного алгоритма». (Н. Вирт).
