Отметим, что алгоритм может пониматься как некоторая функция со специальными свойствами, которые были описаны ранее. Эта функция существует как абстракция. Мы же всегда воспринимаем алгоритм в его некоторой записи, или, как говорят, в его представлении.
Очевидно также, что любой исполнитель может воспринимать алгоритм, исполнять его, только в том случае, когда алгоритм представлен в том виде, в каком он понятен исполнителю. Это означает, что любое представление алгоритма является некоторым информационным блоком, то есть представление алгоритма является информацией, и она расположена на некотором носителе информации.
Таким образом, сам алгоритм есть некоторая абстракция, но реальная его реализация возможна только в виде его представления. Очевидно также, что у любого алгоритма могут быть различные представления. Они могут быть похожими, однако могут и не иметь ничего общего, кроме как реализации одного алгоритма.
Представление алгоритма можно понимать как отображение множества алгоритмов для фиксированного исполнителя во множество некоторых данных, например, символов или рисунков.
Императивное (процедурное) программирование
Существует три основных способа представления алгоритмов:
1) графический;
2) неформальная языковая (алгоритмическая) нотация (запись);
3) запись на алгоритмическом языке.
Любая форма записи (представления) алгоритма должна обеспечивать свойства алгоритма: дискретности, конечности, определенности, массовости.
В графической форме алгоритм представлен в виде геометрических фигур. Обычно они связываются линиями, которые показывают направление передачи информации при исполнении алгоритма. Существует несколько вариантов графического представления алгоритмов, но широкую известность получило (и стало фактическим стандартом графического представления) представление в виде блок-схем. Метод блок-схем был предложен самим Фон Нейманом – одним из первых разработчиков вычислительной техники.
Алгоритм может быть представлен в виде записей литературного языка, например, русского. В этом случае последовательностью предложений описывается последовательность действий исполнителя, которым может быть в большинстве случаев только человек. Никаких специальных правил и требований к таким записям алгоритмов не предъявляется.
Главное, что бы выполнялись требования, предъявляемые к алгоритмам, о которых указывалось выше. В литературе, посвященной алгоритмам, иногда используется такой способ записи алгоритмов. В качестве примера можно привести трехтомную монографию известного специалиста по информатике Д.Кнута «Искусство программирования для ЭВМ». Такие записи на естественном языке называют иногда неформальной алгоритмической нотацией.
В неформальной алгоритмической нотации может использоваться так называемый псевдокод. Псевдокод – это запись алгоритма с использованием языковых конструкций известных алгоритмических языков, либо языков программирования. Например, Паскаль, Алгол, Си, Бейсик и др. При этом нет никаких специальных требований к оформлению таких записей, за исключением требования однозначности при реализации записанных действий.
УРОК 21. Составление алгоритмов для работы с графикой (8 класс)
Третий способ представления алгоритмов – это способ записи алгоритмов с использованием алгоритмических языков, либо языков программирования. Алгоритмический язык – это система правил и обозначений для точной и однозначной записи алгоритмов. Такая запись является формализованной. Это означает, что запись подчиняется строгим требованиям синтаксиса языка.
Язык программирования – это система обозначений и правил для записи алгоритмов, предназначенная для использования на ЭВМ. На практике языки программирования привязаны к конкретным классам ЭВМ, операционным системам и т.д. В языках программирования существенными являются технические и технологические аспекты, что не характерно для алгоритмических языков, которые обычно машинно-независимы.
Программой будем называть любую запись серии исполняемых команд на заданном языке программирования.
Очевидно, способ представления алгоритмов на алгоритмических языках/языках программирования играет ведущую роль. Существует большое количество языков программирования. Одни из них широко распространены: Basic, Pascal, C/C++, Modula, Fortran. Другие же имеют специальное назначение: Prolog, Forth, Lisp. Некоторые языки сыграли заметную роль в программирования, но сейчас не используются.
Примером является язык Algol. Именно этот язык послужил основой для разработки более совершенных языков, таких как Паскаль, Си и других. Алгол использовался также как алгоритмический язык для записи алгоритмов, в том числе в качестве автокода. Можно также отметить такой важный язык программирования для научно-технических расчетов: Фортран.
Существуют языки декларативного (логического) программирования, например Пролог. Здесь нет алгоритмических инструкций, а есть описания данных и связей между ними. Исполняющая система производит поиск наилучшего способа решения поставленной задачи. На других принципах построены функциональные языки, например, Лисп.
Основные управляющие структуры таких языков есть последовательность вызовов так называемых рекурсивных функций. Это означает, что нет необходимости выполнять проверку логических условий, а выполнять только вычисления. Чтобы понять суть таких подходов, необходимо получить специальные знания по теории алгоритмов и математической логике. Это касается глубинного понимания сути алгоритма, связанного с рекурсивными функциями и различными моделями машины Тьюринга.
В 1985 году основатель школьной информатики академик А.П.Ершов предложил для за-писи алгоритмов новый алгоритмический язык, который назвали школьным алгоритмическим языком. Иногда этот язык называют Е-языком, в честь его создателя. Но это называние является неформальным.
Алгоритмические структуры.
Характерной особенностью базовых структур является наличие в них одного входа и одного выхода.
Базовая структура следование. Образуется из последовательности действий, следующих одно за другим.
Базовая структура ветвление. Обеспечивает в зависимости от результата проверки условия (да или нет) выбор одного из альтернативных путей работы алгоритма. Каждый из путей ведет к общему выходу, так что работа алгоритма будет продолжаться независимо от того, какой путь будет выбран.
Структура ветвление существует в четырех основных вариантах:
• если-то; если-то-иначе; выбор; выбор-иначе.
Базовая структура цикл. Обеспечивает многократное выполнение некоторой совокупности действий, которая называется телом цикла. Основные разновидности циклов представлены в таблице:
Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰).
Общие условия выбора системы дренажа: Система дренажа выбирается в зависимости от характера защищаемого.
Опора деревянной одностоечной и способы укрепление угловых опор: Опоры ВЛ — конструкции, предназначенные для поддерживания проводов на необходимой высоте над землей, водой.
Источник: cyberpedia.su
2.2. Графический способ описания алгоритма.
Является достаточно наглядным и простым способом описания алгоритма.
Графический способ описания алгоритма — это способ представления алгоритма с помощью общепринятых графических фигур, называемых блок-схемами, каждая из которых описывает один или несколько шагов алгоритма.
Внутри блока записывается описание команд или условий.
Для указания последовательности выполнения блоков используют линии связи ( линии соединения ).
Последовательность блоков и линий образуют блок-схему алгоритма .
ПРАВИЛА ИЗОБРАЖЕНИЯ БЛОК- СХЕМ АЛГОРИТМА.
1. В блок-схеме можно использовать строго определённые типы блоков.
2. Стрелки на линиях связи можно не ставить при направлении сверху вниз и слева направо; противоположные направления обязательно указывают стрелкой на линии.
3. Для удобства блоки могут помечаться метками(буквами или цифрами).
4. Внутри блока ввода/вывода пишется ВВОД или ВЫВОД и перечисляются имена данных, подлежащих вводу/выводу.
5. Внутри блока действия для присваивания переменных значений используется знак присваивания.
Пример нахождения максимума трех чисел.
2.3. Описание алгоритмов с помощью программ.
Алгоритм, записанный на языке программирования называется программой.
Словесная и графическая форма записи алгоритма предназначены для человека. Алгоритм, предназначенный для исполнителя на компьютере записывается на языке программирования (языке, понятном ЭВМ). Сейчас известно несколько сот языков программирования. Наиболее популярные: Бейсик, Си, Паскаль, Пролог, ПЛ, Ада и т.д.
Пример программы на языке программирования Паскаль:
VAR A,B,C, max: INTEGER;
WRITE(‘ ВВЕДИТЕ A, B, C’);
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. Если условие выхода ложно, то цикл с постусловием прекращает свою работу, в противном случае — происходит повторение действий, указанных в цикле. Повторяющиеся действия в цикле называются «телом цикла».
Источник: studfile.net
Формы представления алгоритмов
1.Пошагово-словесная. Алгоритм представляется на языке человека.
2.Словесно-формульная. Алгоритм представляется на языке человека с использованием математической символики (формул).
3.Графическая. Алгоритм представляется в виде графической схемы.
4.Формальные языки. Для представления алгоритма используются различные псевдокоды и алгоритмические языки.
Пошагово-словесная форма представляет собой пронумерованную последовательность строк, каждая из которых содержит описания конкретных действий на естественном языке. Данная форма применяется в том случае, если исполнителем является человек. Примерами данной формы представления могут служить алгоритмы математических вычислений над конечными числами. Рассмотрим хорошо известный со школы алгоритм Евклида нахождения наибольшего общего делителя двух натуральных чисел (a и b); его пошагово-словесное описание выглядит следующим образом:
1. Если a = b, результатом считать a; закончить вычисления.
2. Если a > b, найти разность a – b; новым значением a считать значение разности; перейти к п.1;
3. Если b > a, найти разность b – a; новым значением b считать значение разности; перейти к п.1;
Удобство пошагово-словесной формы – в ее универсальности (по отношению к классам описываемых алгоритмов), использовании естественного национального языка для записи конструкций, отсутствии строгой формализации. Эта форма записи алгоритмов широко используется для представления различных учебных алгоритмов.
Словесно-формульная форма представления алгоритмов является логическим развитием пошагово-словесной формы. Такая форма записи предполагает использование различных математических соотношений, записанных в виде формул.
Формула – строчная запись действий, обеспечивающих обработку числовых, символьных или логических данных. Формулы, предназначенные для исполнителя «человек», не обязательно могут быть строчными – это приводит к некоторой неоднозначности порядка действий, не сказывающейся, однако, на результате вычислений вследствие дистрибутивного и сочетательного законов.
Графическая форма записи алгоритмаполучила наиболее широкое распространение в информатике. Графическое изображение алгоритма, предназначенного для выполнения на ЭВМ, называется схемой программы. Поэтому, другое распространенное название данной формы – блок-схема. В данной форме для представления отдельных блоков алгоритма используются определенный набор геометрических фигур.
Форма символов действий, их назначение и правила выполнения схем алгоритмов и программ определены соответствующими стандартами (ГОСТ 19.701-90. СХЕМЫ АЛГОРИТМОВ, ПРОГРАММ, ДАННЫХ И СИСТЕМ. УСЛОВНЫЕ ОБОЗНАЧЕНИЯ И ПРАВИЛА ВЫПОЛНЕНИЯ)
Приняты следующие обозначения:
Графическая форма предназначена, безусловно, только для исполнителя «человек» – в этом ее основной недостаток. Главное достоинство такой формы представления – наглядность; блок-схема позволяет охватить весь алгоритм сразу, отследить различные варианты его выполнения. На стадии разработки в блоках можно делать записи как на естественном, так и на формальном языке. Именно по этой причине блок-схема считается весьма полезной формой при обучении алгоритмизации, а также при разработке сложных алгоритмов. Однако в блок-схеме, как правило, отсутствует подробное описание конкретных действий – их существование лишь обозначено.
По блок-схеме гораздо проще осуществляется запись алгоритма на каком-либо формальном языке. Правда, следует заметить, что синтаксическое богатство языков программирования выше языка блок-схем – по этой причине не все языковые конструкции имеют простое графическое представление – примером может служить конструкция цикла с параметром, не имеющая собственного представления в языке блок-схем.
В качестве примера рассмотрим блок-схему обсуждавшегося выше алгоритма Евклида.
Блок-схемы являются не единственной формой графического представления алгоритмов. В качестве альтернативного примера представления алгоритма с помощью графических средств можно привести весьма компактные диаграммы Насси-Шнейдермана.
| Диаграмма Насси-Шнейдермана |
Псевдокод – ориентированный на исполнителя «человек» частично формализованный язык, позволяющий записывать алгоритмы в форме, весьма близкой к алголоподобным языкам программирования. Термин «частично формализованный» в данном случае означает, что в псевдокоде строго определены только правила записи управляющих структур, а описание самих действий остается естественным. Псевдокод имеет русскоязычную основу и используется, в основном, при обучении азам программирования.
Алгоритм представленный с помощью автокода, представляет собой последовательность строк, в каждой из которых содержится описание действий либо по обработке данных, либо по управлению процессом обработки. Для записи управляющих структур приняты следующие обозначения:
· внешнее оформление: АЛГ – начало алгоритма, ПРОЦ – начало процедуры, КНЦ; – конец процедуры, КНЦ. – конец алгоритма;
· ветвление: ЕСЛИ …ТО…ИНАЧЕ…ВСЕ; после ЕСЛИ ставится описание логического условия, по которому происходит ветвление, после ТО – описание действий (их может быть несколько), которые исполняются при значении условия TRUE, если ветвление полное – после ИНАЧЕ описываются альтернативные действия, в любом случае в конце ставится слово ВСЕ, которое служит признаком окончания данной конструкции;
· цикл: ПОКА…ПОВТОРЯТЬ…КЦ; после ПОКА ставится описание логического условия выполнения команд цикла, после ПОВТОРЯТЬ – описание действий (тела цикла), КЦ – признак конца циклической конструкции.
Часто при записи алгоритма отдельные действия заканчиваются разделителем (например, «;») – это позволяет избежать ошибок в случае, если описание действия занимает не одну строку. Помимо этого, для удобочитаемости и наглядности применяется так называемая «структурная запись», при которой запись отдельных элементов структур производится не с начала строки, а с отступом, показывающим вложенность и подчиненность этих элементов.
В качестве примера алгоритма, записанного с помощью псевдокода, приведем рассмотренный выше алгоритм Евклида нахождения НОД двух целых чисел (a и b).
Удобство использования псевдокода – в сочетании относительной строгости синтаксических конструкций и их русскоязычной основы. Близость конструкций псевдокода языкам программирования позволяет легко перейти от одного к другому. Однако отсутствие формальных правил записи действий не позволяет использовать псевдокод для составления алгоритмов, исполнителями которых являются технические устройства.
Источник: studopedia.su