5. Алгоритмизация и языки программирования

5.1. <big><big>Алгоритмы и основные алгоритмические структуры</big></big>

<big>Понятие алгоритма в информатике является фундаментальным, таким, какими являются понятия точки, прямой и плоскости в геометрии, множества - в математике, пространства и времени - в физике, вещества - в химии. Алгоритм - это система правил, описывающая последовательность действий, которые необходимо выполнить, чтобы решить задачу. Это название происходит от латинского написания родившегося в Хиве узбекского математика IX века Аль-Хорезми (Algorithmi), который в свое время сформировал четкие правила выполнения четырех арифметических действий.</big>

<big>Программа - есть запись алгоритма на языке, понятном компьютеру, то есть последовательность операций (набор инструкций), которые выполняет компьютер при решении задачи. Только выполняя инструкции, записанные в виде программы, компьютер получит результат.</big>

 

5.2. <big>Основные свойства алгоритма.</big>

<big>Всякий алгоритм обработки информации характеризуется дискретностью, определенностью, результативностью и массовостью.</big>

<big>Дискретность означает, что выполнение алгоритма разбивается на последовательность законченных действий - шагов. Каждое действие должно быть завершено исполнителем прежде, чем он перейдет к выполнению следующего. Значения величин в каждом шаге алгоритма получаются по определенным правилам из значений величин, определенных на предшествующем шаге.</big>

<big>Под определенностью понимается то обстоятельство, что компьютер, должен быть в состоянии выполнить каждую команду алгоритма в строгом соответствии с ее назначением. Значения величин, получаемые на каком-либо шаге, однозначно определяются значениями величин, полученными на предыдущем шаге.</big>

<big>Результативность (или конечность) алгоритма предполагает, что его исполнение сводится к выполнению конечного числа действий и всегда приводит к некоторому результату. В качестве одного из возможных результатов является и установление того факта, что задача решения не имеет.</big>

<big>Под массовостью понимается, что алгоритм решения задачи разрабатывается в общем виде так, чтобы его можно было применить для целого класса задач, различающихся лишь наборами исходных данных. При этом исходные данные могут выбираться из некоторой области, называемой областью применимости алгоритма. В свойстве массовости заключена основная практическая ценность алгоритмов.</big>

5.3. <big><big>Формы представления алгоритмов</big></big>

<big>Основные формы представления алгоритмов:</big>

<big>– словесное описание алгоритма на естественном языке (вербальная форма);</big>

<big>– построчная запись алгоритма;</big>

<big>– блок-схема;</big>

<big>– информационный граф;</big>

<big>– запись на каком-либо языке программирования.</big>

<big>Рассмотрим особенности каждой из названных форм и в качестве примера представим в каждой форме один и тот же алгоритм для определения нормального веса человека по методу Л.А.Кетле, суть которого в следующем: если соотношение веса (в граммах) к росту (в см) (весоростовой индекс) меньше 300, то это признак истощения, если больше 500, то это избыточный вес.</big>

<big>Словесное описание</big>

<big>Словесное описание имеет минимум ограничений и является наименее формализованным. Однако при этом алгоритм получается и наименее строгим, допускающим появление неопределенностей. Алгоритм в вербальной форме может оказаться очень объемным и трудным для восприятия человеком.</big>

<big>Например: ввести рост и вес; вычислить весоростовой индекс; если весоростовой индекс меньше 300 - признак истощения, если весоростовой индекс больше 500 - избыточный вес, если весоростовой индекс находится в пределах от 300 до 500 - вес в норме.</big>

<big>Построчная запись алгоритма</big>

<big>Это запись на естественном языке, но с соблюдением некоторых дополнительных правил. Сформулируем эти правила.</big>

<big>1. Шаги (предписания) алгоритма нумеруются.</big>

<big>2. Исполнение алгоритма происходит в порядке возрастания номеров шагов, начиная с первого (если не встречается никаких специальных указаний).</big>

<big>3. Типичными шагами алгоритма являются:</big>

<big>     - чтение (ввод) данных, которое записывается в виде Чтение А, В, ...,</big>

<big>     - обработка данных (вычисления) по формулам, записанная в виде  V=....,</big>

<big>     - сообщение (вывод) результата, который имеет вид Запись х, у,....,</big>

<big>     - проверка условия, запись которого Если...то,</big>

<big>     - переход к шагу с номером N,</big>

<big>     - конец вычислений.</big>

Пример:

[1] Чтение А, В

[2] Вычислить весоростовой индекс, К

[3] Если К > 500, идти к [6]

[4] Если К < 300, идти к [7]

[5] Идти к [8]

[6] Вывод: "Избыточный вес"

[7] Вывод: "Истощение"

[8] Вывод: "Вес в норме"

[9] Останов.

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

<big>Блок-схема</big>

<big>Изображение алгоритма в виде блок-схемы отличается высокой степенью наглядности. Блок-схема состоит из соединенных между собой стрелками (линиями потока) блоков различного вида (см. табл. 4).</big>

Выполнение алгоритма всегда начинается с блока начала и оканчивается при попадании на блок конца. Порядок вычислений определяется стрелками.

<big>В блоке обработки данных содержится описание тех действий, которые должны быть выполнены над объектами при попадании на этот блок по входящей в него стрелке. Здесь вычисляются выражения и присваиваются новые значения переменным.</big>

<big>Проверка условия изображается с помощью блока принятия решения, внутри которого записывается это условие. В результате проверки выбирает-

 

Таблица 4</big>

<big>Обозначения блок-схемы</big>

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

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

 <big>Внутри блока ввода или вывода пишется (необязательно) слово <Ввод> или <Вывод> и перечисляются переменные, значения которых должны быть введены или выведены в данном месте схемы.</big>

<big>Комментарии используются в тех случаях, когда пояснение не помещается внутри блока. Совокупность комментариев должна делать блок-схему понятной для любого пользователя.</big>

 

<div align="center">

<big></big>

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

<big>Рис. 5. Блок-схема программы определения нормального веса по методу Л.А.Кетле</big>

Помимо этих блоков допустимо использование и некоторых других, однако, перечисленных выше вполне достаточно для разработки учебных блок-схем. Блок-схема к предыдущему заданию представлена на рис. 5.</big>

Информационные графы

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

Информационные графы делятся на две группы: двудольные (бихроматические) и однодольные (монохроматические). В двудольных информационных графах узлы делятся на два подмножества: f - узлы, соответствующие уравнениям математической модели и x - узлы, соответствующие переменным модели. Дуги графа соответствуют связи (инциденции) некоторого уравнения и переменной. Ориентация данной дуги от переменной к уравнению означает, что данная переменная является для уравнения свободной (заданной), а в обратном направлении - что данная переменная является выходной (определяемой, базисной) для указанного уравнения.</big>

 <big>В однодольных информационных графах узлы соответствуют уравнениям, а дуги - порядку (направлению) их решения, т.е. ориентированный однодольный информационный граф является аналогом блок-схемы алгоритма.</big>

<big>С помощью информационных графов, помимо наглядного изображения алгоритма решения задачи, можно решать также следующие вопросы: определение оптимального алгоритма решения, включающего или минимальное количество итерационных блоков или итерационные блоки с минимальным количеством уравнений; определение совместности систем уравнений; определение избыточных уравнений; определение оптимального набора свободных переменных.</big>

<big>Процесс ориентирования дуг информационных графов и их декомпозиции фактически является формализованным процессом составления алгоритма решения задачи.</big>

<big>Использование информационных графов особенно эффективно при решении больших систем уравнений, т.к. позволяет полностью формализовать процесс составления алгоритма решения в случае, когда составление алгоритма вручную громоздко и затруднительно.</big>

Запись алгоритма на языке программирования

<big>Эта запись представляет собой форму изображения алгоритма в том случае, когда исполнителем алгоритма является компьютер. Языки программирования имеют более жесткие правила, чем, например, правила описания алгоритма на естественном языке, так как их должна "понимать" машина.</big>

5.4. <big>Основные типы алгоритмических структур</big>

<big>Их всего три: линейная, разветвляющаяся и циклическая (Рис. 6).

<big>Линейная структура предполагает однократное выполнение одной и той же последовательности шагов при любых наборах исходных данных. Для разветвляющейся структуры характерно однократное выполнение последовательности шагов, однако, состав этой последовательности определяется результатами проверки некоторого условия, т. е. зависит от обрабатываемой информации. Циклическая структура обеспечивает многократное выполнение одной и той же последовательности шагов тела цикла с модифицируемой (изменяемой) информацией.</big>

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

</big>

	Действие 1
			Действие 2

 

Действие 2

                                                                      Да

 

Действие 3

                                                   Нет.

			Действие 1

 

 

          a                                                         b

 

 

 

 

 

 

 

 

 

 

                                                    с

<big>Рис. 6. Основные типы алгоритмических структур: а - линейная; b -  разветвляющаяся, с - циклическая.

<big>Можно выделить циклы с известным заранее количеством повторений и так называемые итерационные циклы, в которых число прохождений тела цикла заранее не определяется. Для циклов с известным количеством повторений задаются начальное и конечное значения переменной цикла. В итерационных циклах закон изменения переменной цикла в явном виде не описывается.</big>

<big>Если один цикл находится в теле другого, то он называется вложенным (внутренним). Внешний цикл сам может оказаться вложенным по отношению к какому-либо другому циклу. Глубина вложения определяется условиями задачи. Использование вложенных циклов позволяет компактно описывать довольно сложные алгоритмы.</big>

<big>При разработке алгоритмов нередко возникают ситуации, когда в разных местах алгоритма необходимо обращение к одной и той же последовательности шагов обработки данных. Для такой последовательности создают отдельный алгоритм, называемый вспомогательным, а в основном алгоритме предусматривают обращение к нему.</big>

 

5.5. Введение в теорию программирования

<big>Программа (инструкция по обработке информации) - есть реализация алгоритма на каком-либо языке программирования. Процесс написания программы называется программированием.</big>

<big>В программировании выделяют языки различных уровней: машинные (низкоуровневые), Ассемблер и языки высокого уровня (алгоритмические языки).</big>

<big>Машинный язык (язык низкого уровня) представляет собой систему команд компьютера и реализуется им непосредственно. Программа на машинном языке представляет собой последовательность машинных команд и фиксированных областей памяти, выделенных под переменные и константы. При разработке программы на машинном языке необходимо, прежде всего, распределить память под переменные и константы, т. е. для каждой переменной или константы выделить некоторое количество ячеек памяти. Для задания, например, константы в выделенную область памяти записывается соответствующее значение. Структура машинной программы не фиксирована, так как переменные и константы могут чередоваться с командами в любом порядке. При этом никакой разницы между элементами памяти, в которых содержатся команды, константы или переменные, нет. Так, элемент памяти, отведенный под команду, может быть использован как переменная или константа. Контроль за правильностью их использования осуществляет только программист. Это приводит к большому числу ошибок, которые иногда очень трудно обнаружить.</big>

<big>Действия, выполняемые машинными командами, элементарны: например, переслать содержимое одной ячейки памяти в другую, сложить содержимое двух ячеек и т. д. Между тем запись программы с помощью таких действий требует больших трудозатрат. На машинном языке очень неудобна отладка программы, так как, например, добавление всего лишь одной команды в программу может вызывать изменение большого количества адресов.</big>

<big>Машинный язык позволяет использовать все возможности аппаратуры персонального компьютера. С его помощью можно создавать достаточно эффективные программы. Но достичь высоких характеристик надежности программы и производительности труда программистов, работая на нем, очень сложно.</big>

<big>Языки уровня Ассемблера являются машинно-ориентированными, соответствующими системам команд компьютера, но позволяющими составлять программы в форме, более удобной для человека. Преимуществом языка Ассемблера является символическая адресация, когда командам, константам и переменным присваиваются некоторые имена, по которым к ним можно обращаться. Предусматриваются также средства соединения нескольких программ в единый программный модуль и средства контроля ошибок. К недостаткам относятся излишняя детализация записи программ, отсутствие контроля за обращением к элементам памяти.</big>

<big>Программирование в таких системах весьма трудоемко. Решение – использование транслятора, который позволяет записать адреса ячеек памяти в виде буквенных обозначений, понятных человеку, а затем преобразовать эти обозначения в реальные числа. Для этого транслятор должен знать все ячейки памяти, требуемые алгоритму, назначить им адреса из доступной памяти и заменить символьные адреса (определенные программистом) на числовые адреса по всей программе.</big>

<big>Резюмируя вышесказанное, транслятор – есть программа-переводчик с языка программирования с использованием слов и выражений, понятных человеку, на язык машинных команд.</big>

<big>Язык и транслятор этого языка называют системой программирования.</big>

<big>Различают два вида трансляторов: интерпретаторы и компиляторы. Программа-интерпретатор переводит текст программы, составленный программистом, в машинные коды пооператорно без выхода из системы программирования, и при этом не создается исполнимый файл.</big>

<big>Программа-компилятор позволяет транслировать текст программы на язык машинных команд, которые записываются в виде исполнимого файла (и др. служебных файлов, необходимых для работы программы в автономном режиме). Исполнимые файлы могут запускаться на любом другом компьютере, независимо от того, установлена там система программирования или нет.</big>

<big>Языки программирования, которые позволяют писать программы на языках, понятных человеку (например, английский), а затем с помощью программы-транслятора переводить их в машинные коды, называются языками высокого уровня или алгоритмическими языками.</big>

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

<big>Алгоритмические языки, которые позволяют фрагментировать программу на подпрограммы, каждая из которых имеет собственное имя, а затем обращаться к этим подпрограммам по их именам, еще называют процедурными языками.</big>

<big>Подпрограммы могут быть представлены в виде процедур и функций (а также процедур-функций, например, в Бейсике). Процедура (функция) – некоторая последовательность операторов, имеющая собственное имя. Указание этого имени в тексте программы приводит к активизации процедуры (функции) и называется ее вызовом. Сразу после активизации начинают выполняться входящие в нее операторы, после выполнения последнего из них управление возвращается обратно в основную программу, и выполняются операторы, стоящие непосредственно за оператором вызова процедуры.</big>

<big>Функция отличается от процедуры тем, что результат ее работы возвращается в виде значения этой функции, следовательно, в теле функции должен обязательно присутствовать оператор присвоения вычислений в функции имени этой функции.</big>

<big>Развитием процедурного программирования является объектно-ориентированное программирование, суть которого: сначала создается «каркас» в виде формы с кнопками, различными переключателями, полями, а затем каждому объекту формы приписывает отклик (набор операторов) на определенное событие, например, нажатие кнопки (Delphi, Visual Basic, C++, Java).