2.2.2. ПРОГРАММИРОВАНИЕ ЗАДАЧИ

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

Разработка алгоритма

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

Алгоритм обладает следующими свойствами (они следуют из определения):

1) определенностью (детерминированностью) – каждая команда (или предписание) понятна исполнителю (человеку или компьютеру) и исключает неоднозначность исполнения;

2) результативностью – реализация вычислительного процесса, преду­смотренного алгоритмом, должна через определенное число шагов привести к результату или сообщению о невозможности его получения;

3) массовостью – если алгоритм разработан для решения определенной задачи, он должен быть применим для решения задач этого типа при всех допустимых значениях исходных данных;

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

Различают следующие простейшие виды алгоритмов:

1) линейный, когда предписания алгоритма выполняются в той последовательности, в которой они представлены в алгоритме;

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

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

Для описания алгоритма существуют следующие способы:

1) словесный;

2) структурно-стилизованный;

3) языка графических символов;

4) операторного языка.

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

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

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

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

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

2) автокоды явились развитием машинных кодов, когда числовые коды операций заменились мнемоническими обозначениями, по которым можно восстановить смысл операции, а в адресной части можно было использовать имена переменных, а не их адреса. Автокоды современных ЭВМ образуют группу языков, которые называются ассемблерами. И автокоды, и машинные коды являются машинно-зависимыми языками программирования: состав и структура команд полностью соответствует составу и структуре команд ЭВМ;

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

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

1) при написании программы надо учитывать особенности распределения памяти под переменные и константы, в силу чего рациональнее использовать индексированные переменные, а не множества разноименных переменных;

2) программа в процессе работы ясно анализируется за счет выдачи промежуточных результатов, что поясняет окончательный результат;

3) рекомендуется снабжать текст программы комментариями в количестве 1 комментарий на 2 – 3 строки текста (в среднем);

4) использование машинно-независимых языков предпочтительнее ассемблеров, поскольку первые легче читаются;

5) следует минимально использовать оператор безусловной передачи управления, поскольку он затрудняет отладку и понимание программы;

6) необходимо обеспечить мнемоничность имен переменных, констант, подпрограмм, меток, поскольку это облегчает ориентацию в программе.

                 Здесь рекомендуется применять так называемую венскую запись, когда то или иное имя определяет семантику описываемого объекта (современные языки программирования позволяют использовать очень длинные имена для переменных, констант и прочих объектов);

1) свойство гибкости программы определяет простоту ее изменения, расширения, модификации в процессе эксплуатации. Это достигается простотой стиля программирования и применением прогрессивных методов проектирования алгоритмов.

Язык графических символов предполагает, что каждому типу действий соответствует геометрическая фигура, представленная в виде блочного символа. Действия (блоки) соединяются линиями потока. Совокупность таких связанных блоков называется блок-схемой. Составление блок-схем регламентируется ГОСТ 19.701-90. Основные блоки, используемые в блок-схемах, представлены в табл. 2.1.

Таблица 2.1

Основные блоки, используемые в блок-схемах

Схема

Название символа, его значение

Данные

Символ отображает данные, носитель данных не определен

Документ

Символ отображает данные, представленные на носителе в удобочитаемой форме (в форме машинограммы, документа для оптического или магнитного считывания, микрофильма, рулона ленты с итоговыми данными, бланков ввода данных)

Ручной ввод

Символ отображает данные, вводимые вручную во время обработки с устройств любого типа (с клавиатуры, переключателей, кнопок, светового пера, полосок со штриховым кодом)

Запоминаемые данные

Символ отображает хранимые данные в виде, пригодном для обработки, носитель данных не определен

Карта

Символ отображает данные, представленные на носителе в виде карты (перфокарты, магнитные карты, карты со считываемыми метками, карты с отрывным ярлыком, карты со сканируемыми метками)

Дисплей

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

Процесс

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

Предопределенный процесс

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

Продолжение табл. 2.1

Схема

Название символа, его значение

Решение

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

Граница цикла

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

Терминатор

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

Линия

Символ отображает поток данных или управление

Соединитель

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

Комментарий

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

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

Блоки «процесс», «решение», «модификация», «предопределенный процесс», «ввод-вывод», «останов» имеют единый вход (т.е. входящую линию потока), который располагается вверху блока. Например, для блока «процесс»:

Описание: http://www.klgtu.ru/ru/students/literature/inf_asu/img/img_50.jpg

Блоки: «процесс», «предопределенный процесс», «ввод-вывод», «пуск» имеют единый выход (т.е. выходящую линию потока), который располагается внизу блока. Например, для блока «процесс»:

Описание: http://www.klgtu.ru/ru/students/literature/inf_asu/img/img_51.jpg

Блок «решение» имеет как минимум два выхода, которые подписываются словами ДА и НЕТ, например:

Описание: http://www.klgtu.ru/ru/students/literature/inf_asu/img/img_52.jpg

Блок «модификация» имеет выходы и входы (кроме входа в блок) со следующими значениями:

Описание: http://www.klgtu.ru/ru/students/literature/inf_asu/img/img_53.jpg

· связь 1 – возврат к началу цикла. Существует, когда параметр цикла не превысил своего максимального значения;

· связь 2 – вход в тело цикла;

· связь 3 – выход из цикла, когда параметр цикла превысил свое максимальное значение.

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

Описание: http://www.klgtu.ru/ru/students/literature/inf_asu/img/img_54.jpg

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

Описание: http://www.klgtu.ru/ru/students/literature/inf_asu/img/img_55.jpgОписание: http://www.klgtu.ru/ru/students/literature/inf_asu/img/img_56.jpg

К линиям потока предъявляются следующие требования:

1) они должны быть параллельны внешним краям рамки листа;

2) допускается пересечение линий потока или их изгиб под углом 90°, например:

Описание: http://www.klgtu.ru/ru/students/literature/inf_asu/img/img_57.jpg

3) для обозначения слияния место слияния обозначается точкой, например:

Описание: http://www.klgtu.ru/ru/students/literature/inf_asu/img/img_58.jpg

4) направление линий потока сверху вниз и слева направо считается основным. В противном случае, направление указывается стрелкой;

5) расстояние между параллельными линиями потока не менее 3 мм, между остальными символами схемы не менее 5 мм.

Структурно-стилизованный способ – это формализованное представление предписаний, задаваемых путем использования ограниченного набора типовых синтаксических конструкций. Данный способ представления алгоритма требует подготовки и специальных несложных знаний. Примером его может служить нотация Бэкуса – Наура, которая часто используется для описания структуры формализованных языков, например, языков программирования, в частности, Турбо-Паскаля. В этой нотации типовыми синтаксическими конструкциями являются продукции вида:

А::=В,

где А – определяемое продукцией понятие; В – понятие или группа понятий, которые служат для раскрытия структуры понятия А; знак «::=» имеет смысл «есть по определению».

Отладка программы

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

В процессе отладки программы выделяются этапы:

1) трансляции исходного текста программы;

2) компоновки;

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

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

В процессе компиляции последовательно выполняются:

1) лексический анализ;

2) синтаксический анализ;

3) семантический анализ;

4) генерация промежуточного кода;

5) оптимизация промежуточного кода;

6) генерация внутреннего представления.

При лексическом анализе выявляются отельные составляющие текста программы, которые называются лексемами, и определяется их тип. К числу лексем относятся:

· названия операторов, например, readили write;

· имена (переменных или констант), например, NABOR или CHISLO;

· различные разделители, такие как круглые скобки, знаки препинания и т.д.

Одновременно типами указанных лексем являются названия операторов, имена переменных, разделители и т.д. Если программистом допущена ошибка и оператор ввода указан (например, rread), он будет распознан компилятором как имя. На этом этапе выявляется также использование недопустимых языком программирования символов, например, символа @. В результате лексического анализа исходная программа кодируется – каждая лексема заменяется кодом ее типа, что сокращает объем текста программы. Кроме того, из текста программы удаляются пробелы.

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

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

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

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

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

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

Компоновка

Компоновка программы создает готовую для работы программу, которая называется также исполняемой программой или загрузочным модулем. При этом решаются две основные задачи:

1) если в программе используются функции (например, sin, exp и т.д.), соответствующие им программные модули выбираются из библиотеки подпрограмм соответствующей системы программирования и вставляются в объектный модуль;

2) объектный модуль преобразуется в соответствии с реальными адресами основной памяти, куда будет размещаться программа для выполнения.

Выполнение и тестирование программы

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

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

Сдача программы в эксплуатацию

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

1) основные характеристики программы, сведения об ее эксплуатации;

2) сведения о назначении программы, области ее применения, используемых методах решения, ограничениях на применение, минимальной конфигурации технических средств;

3) сведения для проверки работоспособности и корректности выполнения программы, для обеспечения функционирования и настройки программы на условия конкретного применения;

4) сведения о необходимых запросах со стороны программы и форматах ответов пользователя;

5) данные о нештатных ситуациях и поведении пользователя в них.

Этот этап называется сдачей программы в эксплуатацию.

Как видно, все связи (см. рис. 2.2) двунаправленны. Это означает, что в процессе проектирования программы идет диалог, в ходе которого уточняется и/или корректируется предмет общения.