Тема 7. Алгоритмизация и программирование

1.    Основные свойства и способы записи алгоритмов.

2.    История развития ЯП. Этапы развития языков программирования. Классификация ЯП.

 1.       Основные свойства и способы записи алгоритмов.

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

Основными свойствами алгоритмов являются:

1. Универсальность (массовость) - применимость алгоритма к различным наборам исходных данных.

2. Дискретность - процесс решения задачи по алгоритму разбит на отдельные действия.

3. Однозначность - правила и порядок выполнения действий алгоритма имеют единственное толкование.

4. Конечность - каждое из действий и весь алгоритм в целом обязательно завершаются.

5. Результативность - по завершении выполнения алгоритма обязательно получается конечный результат.

6. Выполнимость - результата алгоритма достигается за конечное число шагов.

Алгоритм считается правильным, если его выполнение дает правильный результат. Соответственно алгоритм содержит ошибки, если можно указать такие допустимые исходные данные или условия, при которых выполнение алгоритма либо не завершится вообще, либо не будет получено никаких результатов, либо полученные результаты окажутся неправильными.

Выделяют три крупных класса алгоритмов:

- вычислительные алгоритмы, работающие со сравнительно простыми видами данных, такими как числа и матрицы, хотя сам процесс вычисления может быть долгим и сложным;

- информационные алгоритмы, представляющие собой набор сравнительно простых процедур, работающих с большими объемами информации (алгоритмы баз данных);

- управляющие алгоритмы, генерирующие различные управляющие воздействия на основе данных, полученных от внешних процессов, которыми алгоритмы управляют.

Алгоритм может быть записан различными способами:

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

Формальное описание - на формализованном языке, например на языке программирования. 

Графическое описание алгоритма в виде блок-схемы – это описание структуры алгоритма с помощью геометрических фигур с линиями связи.

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

Основные элементы блок-схем:

 

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

Существует несколько типов алгоритмов: линейные, разветвляющие, циклические.

Линейный алгоритм

Имеет простую линейную структуру, в которой все шаги выполняются друг за другом один раз в порядке их следования.

 

Графическое изображение

Разветвляющийся алгоритм

Разветвляющийся алгоритм - последовательность выполнения шагов алгоритма изменяется в зависимости от некоторых условий. Осуществляется выбор одного из двух/нескольких возможных вариантов. Словесно эта конструкция записывается так:

ЕСЛИ условие справедливо, ТО выполнить действия 1,

ИНАЧЕ выполнить действия 2.

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

Если есть «действия 1» и «действия 2», то говорят о полной альтернативе

                    

Полная альтернатива                                     неполная альтернатива

Графическое изображение разветвленного алгоритма

 Циклический алгоритм

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

Основной блок цикла - тело цикла - производит требуемые вычисления. Вспомогательные блоки цикла организуют циклический процесс: устанавливают начальное значение и новые значения данных, проверяют условие окончания циклического процесса.

Циклический алгоритм позволяет компактно описать большое число одинаковых вычислений над разными данными для получения необходимого результата. Различают циклические структуры с предварительным условием циклы с предусловием и циклические структуры с последующим условием -циклы с постусловием.

Известно, что первым программистом была женщина - леди Ада Лавлейс, дочь лорда Байрона. Она разрабатывала программы для одного из первых механических компьютеров, созданного в начале прошлого века английским ученым Чарльзом Беббиджом. Однако настоящее программирование в современном понимании началось с момента создания первой электронной вычислительной машины. Но тем не менее, имя этой замечательной женщины - Ada - присвоено одному из самых мощных современных ЯП, который является базовым для министерства обороны США.

 

 

 

 

 

2.   История развития ЯП. Этапы развития языков программирования. Классификация ЯП.

 Первые ЭВМ, созданные человеком, имели небольшой набор команд и встроенных типов данных, но позволяли выполнять программы на машинном языке. Машинный язык (МЯ) - единственный язык, понятный ЭВМ. Он реализуется аппаратно: каждую команду выполняет некоторое электронное устройство. Программа на МЯ представляет собой последовательность команд и данных, заданных в цифровом виде. Например, команда вида 1А12 в 16-ричном виде или 0001101000010010 в двоичном виде означает операцию сложения (1А) содержимого регистров 1 и 2.

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

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

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

Принципиальными отличиями ЯВУ от языков низкого уровня являются:

·      использование переменных;

·      возможность записи сложных выражений;

·      расширяемость типов данных за счет конструирования новых типов из базовых;

·      расширяемость набора операций за счет подключения библиотек подпрограмм;

·      слабая зависимость от типа ЭВМ.

С усложнением ЯП усложняются и трансляторы для них. Теперь в набор инструментов программиста, кроме транслятора, входит текстовый редактор для ввода текста программ, отладчик для устранения ошибок, библиотекарь для создания библиотек программных модулей и множество других служебных программ. Все вместе это называется системой программирования. Наиболее яркими представителями ЯВУ являются FORTRAN, PL/1, Pascal, C, Basic, Ada.

Может возникнуть вопрос: почему создано столько различных языков одного класса? Почему нельзя создать один язык на все случаи жизни? Ответ на этот вопрос может быть таким же, как и на вопрос о различных языках народов мира: так уж получилось. Каждый из разработчиков ЯВУ стремился создать самый лучший и самый универсальный язык, который позволял бы быстро получать самые эффективные, надежные и безошибочные программы. Однако в процессе этого поиска выяснилось, что дело не в самом языке, а в технологии его использования. Поэтому дальнейшее развитие языков стало определяться новыми технологиями программирования.

Одновременно с развитием универсальных ЯВУ стали развиваться проблемно-ориентированные ЯП, которые решали экономические задачи (COBOL), задачи реального времени (Modula-2, Ada), символьной обработки (Snobol), моделирования (GPSS, Simula, SmallTalk), численно-аналитические задачи (Analitic) и другие. Эти специализированные языки позволяли более адекватно описывать объекты и явления реального мира, приближая язык программирования к языку специалиста в проблемной области.

Другим направлением развития ЯП является создание языков сверхвысокого уровня (ЯСВУ).

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

На ЯСВУ программист задает отношения между объектами в программе, например систему линейных уравнений, и определяет, что нужно найти, но не задает как получить результат. Такие языки еще называют непроцедурными, т.к. сама процедура поиска решения встроена в язык (в его интерпретатор). Такие языки используются, например, для решения задач искусственного интеллекта (Lisp, Prolog) и позволяют моделировать мыслительную деятельность человека в процессе поиска решений.

К непроцедурным языкам относят и языки запросов систем управления базами данных (QBE, SQL).