Что такое графический способ изображения алгоритмов

Что такое графический способ изображения алгоритмов

Графический способ представления алгоритмов является более компактным и наглядным по сравнению со словесным.

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

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

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

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

Блок «решение» используется для обозначения переходов управления по условию. В каждом блоке «решение» должны быть указаны вопрос, условие или сравнение, которые он определяет.

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

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

Источник

Методы изображения алгоритмов

ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ АЛГОРИТМОВ

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

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

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

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

· дискретность – алгоритм должен представлять процесс решения задачи как последовательное выполнение простых или ранее определенных шагов; каждое действие исполняется только после того, как закончилось исполнение предыдущего;

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

· результативность – алгоритм должен приводить к решению задачи за конечное число шагов;

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

Чтобы алгоритм выполнил свое предназначение, его необходимо строить по определенным правилам.

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

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

Третье правило – дискретность.

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

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

Виды алгоритмов

Виды алгоритмов как логико-математических средств:

· механические – или детерминированные, жесткие, задают определенные действия в единственной и достоверной последовательности, обеспечивая однозначный и требуемый результат;

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

· линейные – набор действий, выполняемых во времени последовательно, друг за другом;

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

· циклические – алгоритмы, предусматривающие многократное повторение одного и того же действия, но над новыми данными;

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

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

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

· циклические процессы, завершающиеся по достижении или нарушении некоторых условий — итерационные циклы;

· циклические процессы, из которых возможны два варианта выхода: по завершении процесса и досрочный выход по какому-либо дополнительному условию – поисковые циклы.

Методы изображения алгоритмов

На практике распространены формы представления алгоритмов:

· словесная — в виде последовательности записей на естественном языке;

· графическая — в виде совокупности графических знаков;

· псевдокоды – полуформализованное описание алгоритма на условном языке, включающем в себя как элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и др.;

· программная – текст на языке программирования.

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

1. Определить форматы переменных А, С и В.

2. Ввести значения А и В с клавиатуры.

4. Если А больше В, то переменной С присвоить значение А.

5. Если В больше А, то переменной С присвоить значение В.

6. Если А равно В, переменной С присвоить значение 0.

7. Вывести на экран значения А, В и С.

Запись алгоритма в виде совокупности графических знаков называется блок-схемой, и получила широкое распространение в научной и учебной литературе. На изображение схем алгоритмов существует ГОСТ 19.701-90. Знаки (блоки) соединены линиями информационного потока (стрелками); каждый знак имеет определенный смысл (см. табл. 1) и соответствует одному шагу (действию) алгоритма. Внутри блока дается описание соответствующего действия. Для простоты чтения схем желательно, чтобы линия входила в блок сверху, а выходила снизу, или шла слева направо. Блоки должны быть одного масштаба. В случае, когда схема алгоритма не умещается на листе, используются соединители. В Microsoft Word для выполнения алгоритмов используется панель инструментов «Рисование – Автофигуры – Блок-схема».

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

Знаки для изображения схем алгоритмов

Обозначение (графическое изображение)	Название	Назначение	Наименование автофигуры в Word
	Терминатор	Начало или завершение программы или подпрограммы	Знак завершения
	Процесс	Обработка данных (вычисления, пересылки т.п.)	Процесс
	Решение	Ветвления, выбор, итерационные и поисковые циклы	Решение
	Данные	Операции ввода-вывода	Данные
	Подготовка	Счетные циклы	Подготовка
	Документ	Вывод на бумагу	Документ
	Архив	Данные, хранящиеся в архиве или взятые из архива	—
	Документ	Документ, подготовленный вручную	—
	Файл	Файл или база данных	Магнитный диск
	Предопреде-ленный процесс	Вызов подпрограмм (процедур)	Типовой процесс
	Источник или приемник данных	Указание источника или приемника данных	—
	Монитор	Вывод информации на экран	Дисплей
	Соединитель	Маркировка разрывов линий	Узел
	Соединитель	Маркировка разрывов линий	Ссылка на другую страницу
	Комментарий	Пояснения к действиям	Выноска
	Поток информации	Линии, связывающие блоки	Стрелка

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

Рис. 1. Базовые алгоритмические структуры: а) следование, б) ветвление

Рис. 2. Базовая структура: цикл-пока

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

Рис. 3. Дополнительная структура «выбор» и реализация ее через базовые структуры

Рис. 4. Дополнительная структура: цикл – до

Рис. 5. Дополнительная структура: цикл с заданным числом повторений (счетный цикл).

На основе алгоритмов создается программное обеспечение (ПО) для решения прикладных задач.

Источник

2.2. Графический способ описания алгоритма.

Является достаточно наглядным и простым способом описания алгоритма.

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

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

Для указания последовательности выполнения блоков используют линии связи ( линии соединения ).

Последовательность блоков и линий образуют блок-схему алгоритма .

ПРАВИЛА ИЗОБРАЖЕНИЯ БЛОК- СХЕМ АЛГОРИТМА.

1. В блок-схеме можно использовать строго определённые типы блоков.

2. Стрелки на линиях связи можно не ставить при направлении сверху вниз и слева направо; противоположные направления обязательно указывают стрелкой на линии.

3. Для удобства блоки могут помечаться метками(буквами или цифрами).

4. Внутри блока ввода/вывода пишется ВВОД или ВЫВОД и перечисляются имена данных, подлежащих вводу/выводу.

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

Пример нахождения максимума трех чисел.

2.3. Описание алгоритмов с помощью программ.

Алгоритм, записанный на языке программирования называется программой.

Словесная и графическая форма записи алгоритма предназначены для человека. Алгоритм, предназначенный для исполнителя на компьютере записывается на языке программирования (языке, понятном ЭВМ). Сейчас известно несколько сот языков программирования. Наиболее популярные: Бейсик, Си, Паскаль, Пролог, ПЛ, Ада и т.д.

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

VAR A,B,C, max: INTEGER;

IF A>B THEN max:=A

IF C>max THEN max:=C;

Вид стандартного графического объекта

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

Условие выполнения действий записывается внутри ромба

Счетчик кол-во повторов

Последовательность выполнения действий.

33. Базовые структуры алгоритмов

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

Разветвление предполагает проверку некоторого условия. В зависимости от того выполняется это условие или нет, выполняется либо одна инструкция, либо другая.

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

Цикл предполагает повторение выполнения некоторой инструкции, а также проверку некоторого условия продолжения повторения этой инструкции. Различают два вида базовых циклов в зависимости от порядка выполнения этих действий: сначала проверка условия выполнения инструкции, а затем ее выполнение (цикл – пока) , или сначала выполнение инструкции, а затем проверка условия повторения ее выполнения (цикл – до) . Также рассматривается цикл со счетчиком. Базовая структура – цикл имеет один вход и один выход.

34. Классификация языков программирования

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

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

Если язык близок к естественному языку программирования, то он называется языком высокого уровня, если ближе к машинным командам, – языком низкого уровня.

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

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

К языкам программирования высокого уровня относят Фортран (переводчик формул – был разработан в середине 50–х годов программистами фирмы IBM и в основном используется для программ, выполняющих естественно – научные и математические расчеты), Алгол, Кобол(коммерческий язык – используется, в первую очередь, для программирования экономических задач), Паскаль, Бейсик (был разработан профессорами Дармутского колледжа Джоном Кемени и Томасом Курцом.), Си (Деннис Ритч – 1972 году), Пролог (в основе языка лежит аппарат математической логики) и т.д.

Языки программирования также можно разделять на поколения:

– языки первого поколения: машинно–ориентированные с ручным управлением памяти на компьютерах первого поколения.

– языки второго поколения: с мнемоническим представлением команд, так называемые автокоды.

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

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

– языки программирования пятого поколения: языки декларативные, объектно–ориентированные и визуальные. Например, Пролог, ЛИСП (используется для построения программ с использованием методов искусственного интеллекта), Си++, Visual Basic, Delphi.

Языки программирования также можно классифицировать на процедурные и непроцедурные.

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

Среди процедурных языков выделяют в свою очередь структурные и операционные языки. В структурных языках одним оператором записываются целые алгоритмические структуры: ветвления, циклы и т.д. В операционных языках для этого используются несколько операций. Широко распространены следующие структурные языки: Паскаль, Си, Ада, ПЛ/1. Среди операционных известны Фортран, Бейсик, Фокал.

Непроцедурное (декларативное) программирование появилось в начале 70-х годов 20 века, К непроцедурному программированию относятся функциональные и логические языки.

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

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

35. Понятие о системе программирования. Интерпретация и компиляция

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

Системы программирования обычно содержат:

· среду разработки программ;

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

· редакторы связей и др.

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

По этому критерию можно выделить следующие уровни языков программирования:

машинно-независимые (языки высокого уровня).

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

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

Языки высокого уровня делятся на:

алгоритмические (Basic, Pascal, C и др.), которые предназначены для однозначного описания алгоритмов;

логические (Prolog, Lisp и др.), которые ориентированы не на разработку алгоритма решения задачи, а на систематическое и формализованное описание задачи с тем, чтобы решение следовало из составленного описания;

объектно-ориентированные (Object Pascal, Delphi, C++, Visual Basic, Java и др.), в основе которых лежит понятие объекта, сочетающего в себе данные и действия над ними. Программа на объектно-ориентированном языке, решая некоторую задачу, по сути описывает часть мира, относящуюся к этой задаче. Описание действительности в форме системы взаимодействующих объектов естественнее, чем в форме взаимодействующих процедур.

Алгоритмический язык (как и любой другой язык), образуют три его составляющие: алфавит, синтаксис и семантика.

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

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

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

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

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

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

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

Транслятор (англ. translator — переводчик) — это программа-переводчик. Она преобразует программу, написанную на одном из языков высокого уровня, в программу, состоящую из машинных команд.

Трансляторы реализуются в виде компиляторов или интерпретаторов. С точки зрения выполнения работы компилятор и интерпретатор существенно различаются.

Компилятор (англ. compiler — составитель, собиратель) читает всю программу целиком, делает ее перевод и создает законченный вариант программы на машинном языке, который затем и выполняется. (Pascal, C).

Интерпретатор (англ. interpreter — истолкователь, устный переводчик) переводит и выполняет программу строка за строкой. (Basic).

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

компилятор прогоняет всю программу без её исполнения, а интерпретатор по командно выполняет и обрабатывает запросы . В этом вся суть.

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

Цикл с предусловием начинается с проверки условия выхода из цикла. Это логическое выражение, например I 6. Если условие выхода ложно, то цикл с постусловием прекращает свою работу, в противном случае — происходит повторение действий, указанных в цикле. Повторяющиеся действия в цикле называются «телом цикла».

Источник