ОСНОВЫ АЛГОРИТМИЗАЦИИ

Понятие алгоритма

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

Программа – это упорядоченная последовательность команд, которые понимает ЭВМ.

В основе любой программы лежит алгоритм.

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

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

Свойства алгоритмов

1.  дискретный (пошаговый) характер определяемого им процесса.

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

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

4.  обязательное требование к алгоритмам – требование их конечности.

5.  эффективность алгоритма. Время выполнения алгоритма и необходимые ресурсы.

Алгоритмизация – процесс разработки и описания алгоритма решения какой-либо задачи.

Существует два вида средств для представления алгоритмов – языковые и графические .

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

Пример Составим алгоритм вычисления коэффициентов приведенного квадратного уравнения x² + px + q = 0, корни которого x₁, x₂ известны.

алгоритм:

Начало.

1. Ввести x₁, x₂.

2. p = –(x₁+x₂).

3. q = x₁x₂.

4. Вывести p, q.

Конец. □

ГОСТ 19.701-90 Схемы алгоритмов , программ, данных и систем.

Схемы алгоритмов

Схема алгоритма – это графический способ его представления с элементами словесной записи.

Таблица Изображение блоков в схемах алгоритмов

Наименование символа	Обозначение и размеры	Функция
Процесс (вычислительный блок)		Выполнение операции или группы операций, в результате которых изменяются значение, форма представления или расположение данных
Решение (логический блок)		Выбор направления выполнения алгоритма в зависимости от некоторых условий
Модификация (заголовок цикла)		Выполнение операций по управлению циклом – повторением команды или группы команд алгоритма
Пуск-останов (начало-конец)		Начало или конец выполнения программы или подпрограммы
Предопределенный процесс (вызов подпрограммы)		Вызов и использование ранее созданных и отдельно описанных алгоритмов (подпрограмм)
Ввод-вывод		Общее обозначение ввода или вывода данных в алгоритме безотносительно к внешнему устройству
Соединитель		Указание прерванной связи между блокам в пределах одной страницы
Межстраничный соединитель		Указание прерванной связи между блоками, расположенными на разных листах

Рис. 1 Алгоритм вычисления коэффициентов
приведенного квадратного уравнения

Технология разработки алгоритмов

Какими качествами должен обладать хороший алгоритм?

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

Но не менее важно, какой ценой это достигается. Речь идет о разумности затрат на его создание.

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

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

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

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

а) структуры следования или последовательности;

б) структуры ветвления;

в) структуры цикла .

Рис.2. Базисные управляющие структуры

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

а) структура сокращенного ветвления;

б) структура выбора; в) структура цикла с параметром;

г) структура цикла с постусловием (Рис. 0 .1, соответственно а, б, в, г).

Рис. 0.1. Дополнительные управляющие структуры

Любой алгоритм может быть построен посредством композиции базисных и дополнительных структур:

- путем их последовательного соединения  образования последовательных конструкций;

- путем их вложения друг в друга  образования вложенных конструкций.

В области автоматизированной обработки данных такой подход называют нисходящим проектированием или проектированием «сверху вниз» .

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

При восходящей схеме алгоритм начинают разрабатывать с создания алгоритмов для подпрограмм.

Структуры алгоритмов

Алгоритмы линейной структуры

Ветвления

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

Рис. 0.2. Алгоритм решения квадратного уравнения

К операндам вещественного типа не следует применять операцию отношения «=» (равно), условие может не выполняться из-за неточного представления вещественных чисел в памяти ЭВМ и неизбежных ошибок округления при вычислениях. В алгоритме отношение D = 0 заменено отношением |D| < , где  – допустимая погрешность округления. □

Циклы

Вычислительные процессы с многократным повторением однотипных вычислений/действий для различных значений входящих величин/данных называются циклическими, повторяемые участки вычислений – циклами, изменяющиеся в цикле величины – переменными цикла. Для организации циклов в алгоритмах необходимо предусмотреть (Рис. 0 .3):

- подготовку цикла – задание начальных значений переменным цикла перед первым его выполнением;

- тело цикла – вычислении/действия, повторяемые в цикле для различных значений переменных цикла;

- модификацию/изменение значений переменных цикла перед каждым новым его повторением;

- управление циклом – проверку условия продолжения/окончания цикла и переход на повторение цикла или его окончание.

Рис. 0.3. Общие схемы циклического алгоритма

Рис. 0.4. Общие схемы алгоритма табулирования функции

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

Системы программирования

Это комплекс средств для разработки программ:

• Языки программирования

(ассемблер, Алгоритмические языки;)

• Инструментальные системы;

• Системы визуальной разработки программ.

• Системы создания ПО для работы в Internet

Алгоритмический язык предназначен для записи алгоритма, удобный для программиста и понятный ЭВМ.

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

Трансляторы могут быть компилирующего типа – компиляторы и интерпретирующего типа – интерпретаторы.

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

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

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

Выбор языка программирования определяется многими факторами: типом решаемой задачи, располагаемыми вычислительными средствами, вкусами и знаниями заказчика и разработчика.

Разработать язык – это создать транслятор для него.

Типы языков программирования

1. процедурные (императивные, указывают порядок выполнения операторов) (Паскаль ,Си)

2. логические (декларативные, основаны на мат. Логике) (Лисп, Пролог),

3. языки запросов (SQL)

Среди 1. – можно выделить 3 направления

1. Фортран-ориентированные (Фортран, Кобол, Visual Basic)

2. Паскаль-ориентированные ( Borland Pascal, Turbo-Pascal, Delphi, Ада, Zonnon)

3. Си-ориентированные (Си, С++, Java, C#, Borland C++, Turbo C++, Visual C++ )

История создания языка Паскаль 1970 год.

Автор – Никлаус Вирт – профессор, директор Института информатики Швейцарской высшей политехнической школы.

Назван – в честь французского математика Блеза Паскаля, в 1641 г. сконструировал суммирующую машину

Цель – для обучения программированию

Турбо – Паскаль

Автор француз Филип Кан Ученик Вирта Курил Aple 2 и написал компилятор для Паскаля в Калифорнии, имея 2000 дол.. Один из создателей фирмы Borland В 1984 за 1 месяц заработал 150 тыс. дол.

Среда Delphi 1995 , язык Object Pascal

История создания языка Си 1972 г.

Автор Деннис Ритчи программист лаборатории американской корпорации AT&T (Американ телефон и телеграф) как язык системного программирования.

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

Преимущества: язык высокого уровня; имеет низкоуровневые средства.

Кен Томсон - создатель системы UNIX в AT&T использовал С (90% ядра системы написано на С)

В 1983г. в Американском национальном институте стандартов ( ANSI) ,был утвержден стандарт языка С, ANSI C.

B начале 80 в той же лаборатории Бьерном Страуструпом создан новый язык С с классами , в 1983 назван С++, как расширение С. Существует много трансляторов С++, будем ориентироваться на трансляторы, созданные фирмой Борланд.

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

Алгол 1958 Швейцария международный коллектив для записи алгоритмов

Алгол 60 1960 Питер Наур и др. Международный.

Фортран 1957(54) США Джон Бэкус (группа IBM)

Лисп 1958 обработка списков для экспертных систем Джон Маккарти, США

Кобол 1960 США обработка эконом. Информации несколько авторов

международный

Бейсик 1963 США Курт и Джон Кемени и др для начинающих

ПЛ1 1964 США (группа IBM) универсальный язык Джордж Радин

Паскаль 1970 Швейцария Никлаус Вирт для обучения

В честь французского математика Блез Паскаль 1623-1662 (суммирующая машина)

Пролог 1973 Марсель Европа язык логического программирования

Алан Кольмеро

Си 1972 США Деннис Ритчи для профессионалов

Ада 1980 США (Пентагон) сложный и надежный Джин Имбиа и др.

С++ 1984 США Бьерн Страуструп объектно-ориентир. расширение С

Турбо - Паскаль 1984 США Филипп Кан (Борланд) Паскаль для ПК

Андерс Хельсберг- руковод проекта Delphi

Версия 7.0 - Borland Pascal

Borland Pascal 7.0 1992 -.- для MS DOS и Windows

Java 1995 для разработки сетевых мультимедийных программ, США

Джеймс Гослинг

Borland C++ Builder

Среда Delphi 1995 , язык Object Pascal

Delphi 5-6 1999 – 2001 Пример RAD – системы среды быстрой визуальной разработки

Среда Delphi Delphi 7 2002 , язык Delphi

Turbo-Delphi 2007

Delphi 8 2008 для платформы Microsoft .Net

Delphi/ Rad Studio 2010 2009

Embarcadero RAD Studio основана в1993г, для разработки БД

а купила Borland в 2008

Delphi , С++ Builder

2014 год Embarcadero® RAD Studio XE7

создание приложений для

Windows 8, Mac, .NET, Web и мобильных платформ.

Содержит: Delphi®, C++Builder®, Embarcadero Prism™ и HTML5 Builder.

С RAD Studio XE3 сущствует встроенная поддержка для SQL Server, Oracle, Sybase, DB2, InterBase, SQL Anywhere, SQLite, MySQL и облачными сервисами, включая Windows Azure и Amazon.

Инструментальные системы - это комплекс средств для разработки программ:

• Текстовый редактор;

• Транслятор;

• Отладчик;

• Средства выполнения программ

• Интерфейс среды.

Системы визуальной разработки программ включают:

• Инструментальную систему

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

• Автоматическое написание кода программы при использовании визуального интерфейса системы.

Системы создания ПО для работы в Internet

Технология .Net

.Net – это стратегия создания крупных распределенных систем, разработанная компанией Microsoft. Ключевым элементом .Net является платформа .Net Framework, т.е. компонентная модель программного обеспечения для работы в сети. Она позволяет совместно использовать отдельные программные компоненты, созданные на разных языках программирования.

Компонент – это некий функциональный элемент, содержащий определенные свойства и размещаемый программистом внутри формы.

С# - основан на синтаксисе С ( с упрощением его) предназначен для технологии .Net.

Отладка и тестирование программы

Отладка программы является итеративным процессом обнаружения и исправления ошибок и обычно требует последовательного выполнения четырех этапов:

• выявления ошибки;

• локализации ошибки в тексте программы;

• установления причины ошибки;

• исправления ошибки.

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

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

ТЕСТ – это совокупность входных и выходных данных, полученных до выполнения программы.

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

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

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

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

Причины и типы ошибок

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

• синтаксические ошибки;

• семантические ошибки;

• логические ошибки.

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

Семантические ошибки – это ошибки, проявляющиеся на этапе выполнения программы при ее попытке вычислить недопустимые значения параметров или выполнить недопустимые действия. Причина возникновения ошибок данного типа связана с нарушением семантических правил написания программ (примером являются ситуации попытки открыть несуществующий файл или выполнить деление на нуль). Если программа обнаруживает ошибку такого типа, то она завершает свое выполнение и выводит соответствующее сообщение в окне Build, содержащее номер строки с ошибкой и ее возможный характер. Список сообщений можно просмотреть с помощью команды меню View/Debug Windows/Event Log.

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

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

Выявлению ошибок второго типа часто помогает использование контролирующих режимов компиляции с проверкой допустимых значений тех или иных параметров (границ индексов элементов массивов, значений переменных типа диапазона, ситуаций переполнения, ошибок ввода-вывода). Устанавливаются эти режимы с помощью ключей компилятора, задаваемых либо в программе, либо в меню Project/Options/Compiler среды Delphi, либо в меню Options/Compiler Турбо-среды.

1. Способы и средства отладки

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

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

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

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

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

Процесс отладки значительно облегчается, если использовать для этого системные средства отладки – специальные программы-отладчики, имеющиеся в программном обеспечении компьютера.

Встроенный отладчик среды Delphi или Турбо Паскаля (Debugger) позволяет контролировать ход выполнения программы – выполнять трассировку программы без изменения самой программы с помощью следующих действий:

• выполнения программы построчно/по шагам;

• остановки выполнения программы в заданной точке останова;

• перезапуска программы, не закончив ее выполнение;

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

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

Отладка программ в среде Delphi

(для программирующих в Delphi)

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

1. Точки контрольного останова

Точка контрольного останова определяет оператор в программе, перед выполнением которого программа прервет свою работу, и управление будет передано среде Delphi. Точка останова задается с помощью опции View|Debug windows|Breakponts.

Окно точек останова содержит список всех установленных в проекте точек, перед выполнением которых происходит прекращение работы программы и управление получает среда Delphi.

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

FileName – определяет имя файла;

Line number – номер строки от начала файла (в момент появления окна оно содержит файл и строку с текстовым курсором);

Condition – можно указать условие останова в виде логического выражения (например, MyValue = Мах-Value-12);

Pass count – количество проходов программы через контрольную точку без прерывания вычислений.

Окно точек останова (слева) и окно добавления новой точки (справа)

1. Окно наблюдения

Наблюдать за состоянием переменной или выражения можно с помощью специального окна, вызываемого опцией View|Debug windows|Watches.

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

Для добавления нового выражения следует щелкнуть по окну правой кнопкой мыши и выбрать опцию New Watch. В строке Expression ввести выражение. Окно Repeat count определяет количество показываемых элементов массивов данных; окно Digits указывает количество значащих цифр для отображения вещественных данных; переключатель Enabled разрешает или запрещает вычисление выражения. Остальные элементы определяют вид представления значения.

Значения переменных можно также посмотреть во время останова программы, наведя курсор мыши на переменную в тексте кода.

Окно наблюдения и окно добавления в него нового выражения

1. Принудительное прерывание работы программы

Если программа запущена из среды Delphi, ее работу можно прервать в любой момент с помощью клавиш Ctrl+F2, кнопки ESC, опцией Run|Program Pause или, наконец, установив точку контрольного останова в той части программы, которая выполняется в данный момент или будет выполнена.

1. Трассировка программы

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

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

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

21