Лекция

Тема: «Понятие алгоритма. Алгоритмические языки. Машинные коды»

План

1. Понятие об алгоритмических языках

2. Этапы разработки программы

3. Основные понятия программирования

1. Понятие об алгоритмических языках

Алгоритмические языки близки к естественному языку. Именно такая цель ставилась при их разработке. Однако правила построения конструкций в алгоритмическом языке более «жесткие». Это означает, что алгоритмические языки допускают меньшее разнообразие для описания действий алгоритма, чем естественный язык и привычная математическая символика, и машина однозначно понимает любую конструкцию языка.

Например, для умножения двух переменных а и b общепринятая математическая символика допускает несколько возможных форм записи: 1) ab; 2) axb и т. п. А на алгоритмическом языке, например на языке Бейсик, эту операцию можно записать только единственным образом как А*В. Небольшие ошибки или описки, допускаемые в предложениях естественного языка и не искажающие, на наш взгляд, смысла, совершенно недопустимы в алгоритмическим языке, где каждый символ и его место в конструкции имеют строго фиксированное значение.

Так как программа на алгоритмическом языке предназначена для выполнения на ЭВМ, то в алгоритмическом языке, помимо средств, описывающих действия алгоритма, обязательно должны быть также определены средства, позволяющие вводить исходные данные в ЭВМ и выводить результаты выполнения программы.

Алгоритмический язык – формальный язык, используемый для записи, реализации или изучения алгоритмов

Компьютер не понимает естественного языка человека, а понимает только свой язык – машинный код. Что касается языка программирования, то он с помощью фиксированных систем обозначений и правил позволяет описывать алгоритмы и структуры данных, которые впоследствии будут переведены транслятором в машинный код.

Процессор – это, по сути, очень сложный и продвинутый калькулятор. У него есть множество ячеек памяти (называемых регистрами) с которыми и между которыми проводятся различные математические и байтовые операции. Машинный код как раз и представляет собой описание последовательности выполнения операций и набора участвующих данных. По сути, это единственный язык, который понимает процессор вашего компьютера.

Все языки программирования можно разделить на языки низкого, высокого и сверхвысокого уровней.

Языки низкого уровня – это средство записи инструкций компьютеру простыми приказами-командами на аппаратном уровне. Такой язык зависит от структуры конкретной ЭВМ и иногда называется машинно-ориентированным языком. Этот язык плохо приспособлен для использования человеком, ведь запись программы на этом языке представляет собой последовательность нулей и единиц, и мало шансов, что сложная задача будет запрограммирована безошибочно. Для упрощения программирования был разработан язык символического кодирования (автокод, или язык ассемблера). Программа, написанная на таком языке, ближе человеку, но все равно требует от программиста широких познаний в этой области.

Следующая группа – языки программирования высокого уровня. Это языки, которые допускают описание задачи в наглядном, легко воспринимаемом виде. Их отличительной особенностью является ориентация не на систему команд той или иной ЭВМ, а на систему инструкций, характерных для записи алгоритмов определенного класса. К языкам программирования высокого класса относятся Бейсик, Фортран, Алгол, Паскаль, Си и др.

К языкам программирования сверхвысокого уровня можно отнести Алгол-68, в котором сделана попытка формализовать описание языка, приведшая к появлению двух типов программ: абстрактной и конкретной. Первый тип программы – абстрактный – создается программистом, конкретный – выводится из первого. Существует предположение, что при таком подходе принципиально невозможно породить синтаксически (а на практике и семантически) неверную конкретную программу.

Программа, написанная на любом языке программирования, является исходной программой. Особенность таких программ, как мы помним, заключается в том, что они состоят из инструкций, понятных человеку, но не понятных процессору компьютера. Чтобы процессор мог выполнить работу в соответствии с алгоритмом, записанным в исходной программе, эта программа должна быть переведена на машинный язык – язык команд процессора. Такой перевод программы называется трансляцией (translation – перевод), а выполняется он специальными программами – трансляторами. В программе-трансляторе «заложены» все правила алгоритмического языка и способы преобразования различных его конструкций на машинный язык. Именно поэтому при составлении программы на алгоритмическом языке нужно скрупулезно придерживаться правил этого языка, иначе ЭВМ не поймет вашу программу или поймет неправильно.

Существует три вида трансляторов: интерпретаторы, компиляторы и ассемблеры.

Интерпретатор – транслятор, переводящий текст программы поэтапно (покомандно) и сразу же (то есть параллельно) выполняющий оттранслированную команду исходной программы.

Компилятор транслирует текст программы в модуль на машинном языке, затем программа переписывается в оперативную память и лишь после этого исполняется процессором компьютера. Именно с использованием трансляторов такого типа осуществляется перевод программы на многих языках программирования в машинный код. Поэтому рассмотрим схему его работы.

Цифрой 1 на схеме обозначен блок синтаксического контроля текста программы, цифрой 2 –генератор машинного кода.

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

Последний вид трансляторов – ассемблеры. Они предназначены для перевода программы, написанной на языке ассемблера (автокода), в программу на машинном языке.

Все трансляторы, независимо от их вида, решают следующие основные задачи:

· ·        выполняют анализ и проверяют синтаксис транслируемой программы;

· ·        генерируют машинный код программы;

· ·        распределяют память для выходной программы.

2. Этапы разработки программы

Решение любой задачи с помощью компьютера – это совместная деятельность человека и ЭВМ. Чтобы человек и компьютер понимали друг друга, они должны «разговаривать» на одном языке – языке программирования.

Программирование – это процесс создания (разработки) программы, который может быть представлен как последовательность нескольких этапов.

1. Постановка задачи. На этом этапе подробно описывается исходная информация, и формируются требования к результату, а также описывается поведение программы в особых случаях.

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

3. Разработка или выбор алгоритма. Здесь необходимо определить последовательность действий, которые надо выполнить для получения результата.

4. Программирование. Программой называют последовательность действий, направленных на выполнение их некоторым исполнителем (например, компьютером).

5. Ввод программы и исходных данных в ЭВМ.

6. Тестирование и отладка программы. На этом этапе происходит исполнение алгоритма с помощью ЭВМ, поиск и исправление ошибок. Отладка программы заключается в тестировании программы на контрольных примерах.

7. Исполнение отлаженной программы и анализ результатов. На этом этапе программист задает исходные данные и анализирует результаты, полученные в ходе выполнения программы.

3. Основные понятия программирования

Введем основные понятия программирования:

Исполнитель – это человек или автомат (в частности, им может быть процессор ЭВМ), умеющий выполнять некоторый, вполне определенный конечный набор действий. Приказ на выполнение действия из указанного набора, выраженный каким-либо заранее оговоренным способом, называется предписанием, а вся совокупность допустимых приказов – системой предписаний исполнителя.

Давая задание исполнителю на выполнение некоторой работы, мы обычно выдаем ему не одно предписание, а некоторую конечную последовательность предписаний, задавая также порядок, в котором эти предписания должны быть выполнены. Такая последовательность предписаний с указанием порядка их выполнения называется программой.

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

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

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

Переменную можно представить себе как ящик, обозначенный именем, идентифицирующим эту переменную. Присвоение переменной с именем n значения 5 можно представить себе так: положить в ящик, обозначенный n, 5 шаров. (Ящик является аналогом ячейки памяти ЭВМ.)

Значение одной переменной можно переслать в другую переменную. При этой операции значение пересылаемой переменной не изменяется. Например, переслать значение n в переменную i, или присвоить переменной i значение n, означает задать i такое же значение, которое имеет переменная n, т. е. скопировать значение n. Если было, допустим, n=5, то присвоение i значения n (записывается i=n) означает, что нужно как бы посмотреть, какое число находится в ячейке памяти n, и такое же число «положить» в ячейку памяти i. Теперь будет i=5, но при этом n сохранило значение (n=5).

Часто в программировании используется такая операция присваивания, когда слева и справа используется одна и та же переменная, например, i=i+1. Такая запись означает, что сначала должна быть выполнена операция сложения (i+1), а затем полученная сумма присвоена переменной i в качестве ее нового значения. При этом старое значение i пропадает (стирается). После выполнения этой операции i будет иметь значение на 1 больше, чем перед ее выполнением.

Вернемся к нашей задаче. Чтобы получить произведение n на m, используя операцию сложения, нужно просуммировать m слагаемых, равных n, т. е. вычислить

k = n+n+ ...+n m раз

Но эта формула – не программа, хотя бы потому, что здесь есть неопределенность (например, многоточие).

Решение этой задачи можно представить как последовательность выполнения следующих простых шагов: Положить k=0. Далее выполнить операцию k=k+n m раз. При этом после каждого выполнения указанной операции значение к увеличивается на n. В итоге в к будет получен результат решения задачи.

Чтобы выполнить операцию требуемое число раз, нужно считать, сколько раз эта операция уже выполнена. Используем для этого вспомогательную переменную i. Назовем ее счетчиком. Перед первым прибавлением к к значения n положим i= 1 и после очередного изменения к значение счетчика i будем менять на 1.

Тогда программа может быть записана так:

1) задать конкретные значения n, m

2) k=0

3) i=1

4) k=k+n

5) i=i+l

6) если i<=m идти к 4. (Повторить выполнение операций, начиная с п. 4.)

7) закончить вычисления

Пояснения к программе.

Программа написана на обычном языке человеческого общения с использованием общепринятой математической символики (это так называемый «естественный» язык).

Операторы 1, 2, 3 задают начальные значения переменных к и i. Оператор 4 при каждом своем выполнении увеличивает значение к на n. Оператор 5 увеличивает значение счетчика на 1 после того, как выполнено очередное сложение. Оператор 6 проверяет условие i<=m, и если оно выполняется, т. е. не все m сложений еще выполнены, то происходит возврат к оператору 4 и повторное выполнение программы, начиная с оператора 4. Как только в процессе выполнения программы условие i<=m не будет выполнено, процесс вычислений заканчивается. Это произойдет, когда будет i>m, т. е. все нужные сложения выполнены.

Приведенная программа задает порядок действий, которые могут быть выполнены, когда n и m получат конкретные значения.

Вопросы для самоконтроля

1. Что такое алгоритмический язык? Особенности алгоритмических языков?

2. Что такое машинный код?

3. Дайте характеристику языкам низкого уровня. Приведите примеры.

4. Дайте характеристику языкам высокого уровня. Приведите примеры.

5. Дайте характеристику языкам сверхвысокого уровня. Приведите примеры.

6. Что такое исходная программа, трансляция программы, трансляторы?

7. Что такое компилятор? Интерпретатор? Ассемблер?

8. Что такое программирование? Назовите этапы разработки программы?

9. Что такое исполнитель, программа;