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

Формы записей алгоритмов. Общие принципы построения.

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

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

Объектно-ориентированное программирование (ООП)

Чтобы написать еще более сложную программу, необходим новый подход к программированию - технология объектно-ориентированного программирования.

OOП включает лучшие идеи, воплощённые как в структурном программировании, так и в модульном. «Является еще более структурным программированием, еще более модульным» (Джеф Дантеманн?).

И, кроме того, ООП сочетает старые принципы с мощными новыми концепциями, которые позволяют оптимально организовывать программы.

Объектно-ориентированное программирование позволяет разложить проблему на составные части. Каждая составляющая становится самостоятельным объектом, содержащим свои собственные коды и данные, которые относятся к этому объекту. В этом случае программирование в целом упрощается, и программист получает возможность оперировать гораздо большими по объёму программами.

Таким образом, ООП – «это методология, основанная на представлении программы в виде совокупности объектов, каждый из которых является реализацией собственного класса» (А.Д. Александровский).

Основным понятием ООП является понятие класса.

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

Coordinates = class

x, y: byte;

procedure Init (Xinit, Yinit: byte);

function GetX: byte;

function GetY: byte;

end;

Для разработки приложений в Delphi используются специальным образом оформленные классы – компоненты.

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

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

В Object Pascal объекты существуют только в динамической памяти (т.е. переменная, являющаяся объектом, по сути является указателем на объект, и содержит адрес объекта).

Лекция 3.

Понятие алгоритма. Свойства алгоритмов. Формы записей алго­ритмов. Общие принципы построения.

Вопросы:

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

Происходит от имени узбекского ученого IX в. Аль-Хорезми, который в своем труде "Арифметический трактат", переведенном в XII в. с арабского на латынь, изложил правила арифметических действий над числами в позиционной десятичной системе счисления. Эти правила и называ­ли алгоритмами.

Алгоритм означает точное описание некоторого процесса, инструкцию по его выполнению. Разработка алгоритма является сложным и трудоемким процессом. Алгоритмизация – это техника разработки (составления) алгоритма для решения задач на ЭВМ.

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

Принято выделять следующие семь:

1. Наличие ввода исходных данных.

2. Наличие вывода результата выполнения.

3. Однозначность (компьютер «понимает» только однозначные инструкции).

4. Общность – алгоритм предназначен для решения некоторого класса задач.

5. Корректность – алгоритм должен давать правильное решение задачи.

6. Конечность – решение задачи должно быть получено за конечное число шагов.

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

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

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

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

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

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

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

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

Всякий человек при планировании деятельности обязательно выполняет две операции:

1. Оценивает исходные данные (создает исходную модель).

2. Прогнозирует результат (прогнозирует какую-то конечную модель).

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

Формы записей алго­ритмов. Общие принципы построения

Этапы информационных технологий решения прикладных задач:

- общая формулировка задачи;

- математическая формулировка задачи;

- выбор математического метода решения;

- составление алгоритма решения;

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

- тестирование программы;

- решение поставленной задачи и представление результатов.

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

- Каждый алгоритм должен иметь имя, которое раскрывает его смысл.

- Необходимо обозначить начало и конец алгоритма.

- Описать входные и выходные данные.

- Указать команды, которые позволяют выполнять определенные действия над выделенными данными

Общий вид алгоритма

Алгоритм: Название алгоритма

Описание данных

Начало

Команды

Конец

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

- Словесно- формульное описание

- Блок-схема (схема графических символов)(по ГОСТ 19.701-90 "Единая система программной документации"/ИСО 5807-85);

- Алгоритмические языки

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

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

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

Основные блоки.

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

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

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

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

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

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

Основные алгоритмические конструкции. Сложность алгоритмов.

Вопросы:

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

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

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

Несмотря на многообразие алгоритмов все они строятся из 3-х типов алгоритмических структур.

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

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

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

 

…

 

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

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

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

а) если – то

б) если – то иначе

в) выбор

условие 1: действие 1

…

условие N: действие N

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

 

нет

 

да

 

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

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

а) Пока <условие> делай<тело цикла>

б) для i от i₁ до i₂ делай<тело цикла>.

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

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

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

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

- следование;

- ветвление (в полной и сокращенной форме);

- цикл (с предусловием или постусловием).

Характерной особенностью этих структур является наличие у них одного входа и одного выхода.

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

 

…

 

да

 

нет