Уважаемый подписчик! Сразу же вынужден извиниться за некорректную ссылку, указанную в материалах предыдущего занятия. С сылка http://a-morgun.narod.ru/a08-01/a0008-0001-0001-0001.html – правильная.
Нам уже известно, что написанию программы решения задачи предшествует разработка соответствующего алгоритма. Поэтому сегодня мы с вами приступаем к рассмотрению достаточно эффективного современного способа представления алгоритмов в виде словесных описаний на, так называемом, алгоритмическом языке (АЯ).
Зап омните! Только алгоритмы на АЯ допускают практически формальное (понятное, простое и удобное) своё преобразование в подпрограммы на языке Паскаль.
ОСНОВНЫЕ ПОНЯТИЯ АЛГОРИТМИЧЕСКОГО ЯЗЫКА
К основным понятиям алгоритмического языка относятся алгоритм, команда, служебный объект, величина и имя.
Алгоритмом на АЯ будем называть определённый текст, представляющий с использованием формальных правил условие и процесс решения некоторой задачи, и состоящий из заголовка и основной части .
Информатика 8 класс: Способы записи алгоритмов
Говорят, что заголовок алгоритма определяет его с внешней стороны. Для этого заголовок содержит имя алгоритма, перечень параметров, распределённых на аргументы и результаты, указание типа каждого из параметров, а также произвольный комментарий к решаемой задаче.
Команда алгоритма – это указание исполнителю на выполнение некоторых действий. Различают простые и структурные команды. Разные команды отличаются между собой правилом записи и правилом выполнения.
Последовательность нескольких команд алгоритма, начало и конец которой отмечены служебными словами нс и кс, называют серией . Серию можно рассматривать как единую составную команду.
Служебные объекты алгоритмического языка предназначены для записи команд и для оформления алгоритмов. Основная особенность любого служебного объекта состоит в том, что его смысл и способ употребления в алгоритме однозначно определён заранее. Среди служебных объектов различают служебные слова и служебные знаки .
Величиной называется любой объект алгоритма, несущий информацию об определённом значении. Если величина принимает участие в выполнении команд, то это может сопровождаться преобразованием формы её представления, а также образованием нового значения для этой величины.
Важнейшей характеристикой величины является её тип . В общем случае тип величины определяет количество и характер отдельных элементарных значений в её составе, а также порядок доступа к ним. Различают простые и структурированные типы. Величина простого типа представляет собой элементарное (единственное, отдельное и неделимое) значение. Величина структурированного типа представляет собой совокупность значений.
Все величины могут быть распределены на постоянные и переменные. Постоянной величиной называется та, значение которой не может быть изменено посредством выполнения какой-то из команд алгоритма и всегда остаётся одним и тем же. Переменной величиной называется такая величина, значение которой может измениться вследствие выполнения определённой команды алгоритма.
Способы записи алгоритмов
Среди постоянных величин выделяют константы . Константа обладает тем свойством, что её значение указывается в тексте алгоритма непосредственно. При этом тип константы можно определить по её внешнему виду.
Среди переменных величин особо выделяют переменные (термин употребляется как имя существительное). Для переменных в алгоритме используют обозначения, которые называют именами переменных. Типы переменных в алгоритме указывают с помощью стандартных имён типов.
Выше упоминались некоторые объекты алгоритма, с которыми должны быть связаны определённые имена . Такие объекты алгоритма называются именованными. К ним относятся сами алгоритмы, а также типы, переменные и константы. Имена могут быть стандартными или выбранными произвольно.
Слишком много новых терминов! Не правда ли? А ведь это пока только алгоритмический язык. В реальном Паскале их ещё больше. Кстати, АЯ тем и хорош, что позволяет нам, в отличие от Паскаля, ограничиться самым главным.
Теперь приведём пример алгоритма, в котором можно было бы обнаружить всё вышеупомянутое.
алг Проверка ( арг x , y: цел ; рез z : цел , s : лит )
дано произвольные значения уровней x и y
надо значение суммы уровней z и сообщение s об их допустимости
нач p: вещ
p := Ln ( x ) + Ln ( y )
если ( p < 5 ) или ( p > 5 + 5 )
то s := ”выход уровней за допустимые пределы”
иначе нс z := x + y ; s := ”уровни в норме” кс
кон
1. Три первые строки приведённого алгоритма являются его заголовком . Алгоритм имеет имя Проверка. Параметрами алгоритма являются переменные x, y, z и s. Из них переменные x и y являются его аргументами (исходными данными), а переменные z и s – результатами. Параметры x, y и z имеют целочисленный тип, параметр s – литерный (текстовый). Произвольный комментарий после слов дано и надо кратко формулирует общее назначение алгоритма. Считается, что заголовок определяет, как выглядит алгоритм извне.
3. Команда присваивания является простой командой, а команда ветвления – структурной , поскольку содержит в своём составе простые команды присваивания после слов то и иначе, а также условие их выполнения ( p < 5 ) или ( p > 5 + 5 ) после слова если.
4. В составе команды ветвления имеется последовательность двух команд присваивания z := x + y ; s := “уровни в норме”, начало и конец которой отмечены служебными словами нс и кс. Такая последовательность, рассматриваемая как единая составная команда, называется серией .
5. Служебными объектами алгоритма являются служебные слова алг, арг, рез, цел, лит, вещ, дано, надо, нач, кон, предназначенные для оформления алгоритма, служебные слова если, то, иначе, :=, нс, кс, предназначенные для записи команд, а также служебное слово или, предназначенное для указания операции. Кроме того, служебными объектами данного алгоритма являются следующие служебные знаки : знаки препинания точка с запятой и двойные кавычки ; ” >, знаки операций сложения и сравнения < + >, а также круглые скобки < ( ) >.
6. В выполнении команд нашего алгоритма принимают участие величины , несущие информацию о тех или иных значениях. К ним относятся величины p , x , y , Ln ( x ) + Ln ( y ), 5, x + y , z , принимающие числовые значения, величины p < 5, p >5 + 5, принимающие логические (вида “да – нет”) значения и величины s , ”выход уровней за допустимые пределы”, ”уровни в норме”, принимающие литерные значения. Обратите внимание, что в результате выполнения команды присваивания величина, представленная первоначально только в форме выражения Ln ( x ) + Ln ( y ), оказалась представленной ещё и в форме переменной p. С другой стороны, для ранее неопределённой величины p было образовано новое значение, равное значению выражения Ln ( x ) + Ln ( y ).
7. В нашем алгоритме использованы величины трёх типов : числовые целые и числовые вещественные, литерные, а также логические. При этом для переменных x , y , z , p , s их тип указан явно с помощью служебных слов цел, вещ и лит. Оба числовых типа цел и вещ считаются простыми , поскольку любое числовое значение элементарно (единственно, отдельно и неделимо). Литерный тип лит считается структурированным , поскольку текстовое значение в целом представляет собой совокупность значений отдельных знаков (букв).
8. В нашем алгоритме использованы постоянные величины 5, 5 + 5, ”выход уровней за допустимые пределы” и ”уровни в норме”. Их значения соответствуют тому, что написано, и считать их иными невозможно. Все остальные являются переменными величинами .
Например, значение величины x + y может быть разным в зависимости от значений величин x и y. Постоянная величина 5 является константой . По её внешнему виду мы легко определяем, что она имеет целочисленный тип. Постоянные величины ”выход уровней за допустимые пределы” и ”уровни в норме” – тоже константы . Вполне очевидно, что они имеют литерный тип.
9. В нашем алгоритме есть также, так называемые, переменные (термин употребляется как имя существительное). К ним относятся переменные величины, обозначенные x , y , z , s и p.
10. В заключение нашего комментария перечислим именованные объекты нашего алгоритма. Именованный объект алгоритм имеет произвольно выбранное имя Проверка. Именованные объекты переменные имеют произвольно выбранные имена x , y , z , s и p. А такие именованные объекты, как типы переменных, имеют стандартные имена цел, вещ и лит.
Обратите внимание, что необходимость истолковать основные понятия АЯ повлекла за собой использование целой группы других новых понятий. Это значит, что между всеми ними существует чрезвычайно тесная взаимосвязь. Невозможно понять что-то одно, не затрагивая при этом другое.
Чтобы получить более подробное изложение материала занятия №3 “Основные понятия алгоритмического языка”, перейдите по ссылке http://a-morgun.narod.ru/a06-01/a0006-0001-0002.html
При необходимости задать вопрос, проконсультироваться или обсудить что-либо обращайтесь через Гостевую книгу моего персонального сайта http :// a — morgun . narod . ru
Источник: subscribe.ru
Информатика для СПО
Алгоритмом называется точная инструкция исполнителю в понятной для него форме, определяющая процесс достижения поставленной цели на основе имеющихся исходных данных за конечное число шагов.
Основными свойствами алгоритмов являются:
1. Универсальность (массовость) — применимость алгоритма к различным наборам исходных данных.
2. Дискретность — процесс решения задачи по алгоритму разбит на отдельные действия.
3. Однозначность — правила и порядок выполнения действий алгоритма имеют единственное толкование.
4. Конечность — каждое из действий и весь алгоритм в целом обязательно завершаются.
5. Результативность — по завершении выполнения алгоритма обязательно получается конечный результат.
6. Выполнимость — результата алгоритма достигается за конечное число шагов.
Алгоритм считается правильным, если его выполнение дает правильный результат. Соответственно алгоритм содержит ошибки, если можно указать такие допустимые исходные данные или условия, при которых выполнение алгоритма либо не завершится вообще, либо не будет получено никаких результатов, либо полученные результаты окажутся неправильными.
Выделяют три крупных класса алгоритмов:
— вычислительные алгоритмы, работающие со сравнительно простыми видами данных, такими как числа и матрицы, хотя сам процесс вычисления может быть долгим и сложным;
— информационные алгоритмы, представляющие собой набор сравнительно простых процедур, работающих с большими объемами информации (алгоритмы баз данных);
— управляющие алгоритмы, генерирующие различные управляющие воздействия на основе данных, полученных от внешних процессов, которыми алгоритмы управляют.
Алгоритм может быть записан различными способами:
Словесное описание (на естественном языке) алгоритма представляет собой описание структуры алгоритма на естественном языке. Например, к приборам бытовой техники, как правило, прилагается инструкция по эксплуатации, т. е. словесное описание алгоритма, в соответствии с которым данный прибор должен использоваться.
Формальное описание — на формализованном языке, например на языке программирования.
Графическое описание алгоритма в виде блок-схемы – это описание структуры алгоритма с помощью геометрических фигур с линиями связи.
Блок схема алгоритма – это графическое представление метода решения задачи, в котором используются специальные символы для отображения операций.
Основные элементы блок-схем:
Каждый из перечисленных способов изображения алгоритмов имеет и достоинства и недостатки. Например, словесный способ отличается многословностью и отсутствием наглядности, но дает возможность лучше описать отдельные операции. Графический способ более наглядный, но часто возникает необходимость описать некоторые операции в словесной форме.
Существует несколько типов алгоритмов: линейные, разветвляющие, циклические.
Линейный алгоритм
Имеет простую линейную структуру, в которой все шаги выполняются друг за другом один раз в порядке их следования.
Графическое изображение
Разветвляющийся алгоритм
Разветвляющийся алгоритм — последовательность выполнения шагов алгоритма изменяется в зависимости от некоторых условий. Осуществляется выбор одного из двух/нескольких возможных вариантов. Словесно эта конструкция записывается так:
ЕСЛИ условие справедливо, ТО выполнить действия 1,
ИНАЧЕ выполнить действия 2.
Разветвляющийся алгоритм содержит блок проверки некоторого условия, и в зависимости от результата проверки выполняется та или иная последовательность шагов (действий).
Если есть «действия 1» и «действия 2», то говорят о полной альтернативе
Полная альтернатива неполная альтернатива
Графическое изображение разветвленного алгоритма
Циклический алгоритм
Для обозначения многократно повторяющихся действий используются специальные циклические структуры. Такая структура содержит условие, которое необходимо для определения количества повторений для некоторой последовательности действий.
Основной блок цикла — тело цикла — производит требуемые вычисления. Вспомогательные блоки цикла организуют циклический процесс: устанавливают начальное значение и новые значения данных, проверяют условие окончания циклического процесса.
Циклический алгоритм позволяет компактно описать большое число одинаковых вычислений над разными данными для получения необходимого результата. Различают циклические структуры с предварительным условием циклы с предусловием и циклические структуры с последующим условием -циклы с постусловием.
Известно, что первым программистом была женщина — леди Ада Лавлейс, дочь лорда Байрона. Она разрабатывала программы для одного из первых механических компьютеров, созданного в начале прошлого века английским ученым Чарльзом Беббиджом. Однако настоящее программирование в современном понимании началось с момента создания первой электронной вычислительной машины. Но тем не менее, имя этой замечательной женщины — Ada — присвоено одному из самых мощных современных ЯП, который является базовым для министерства обороны США.
2. История развития ЯП. Этапы развития языков программирования. Классификация ЯП.
Первые ЭВМ, созданные человеком, имели небольшой набор команд и встроенных типов данных, но позволяли выполнять программы на машинном языке. Машинный язык (МЯ) — единственный язык, понятный ЭВМ. Он реализуется аппаратно: каждую команду выполняет некоторое электронное устройство. Программа на МЯ представляет собой последовательность команд и данных, заданных в цифровом виде. Например, команда вида 1А12 в 16-ричном виде или 0001101000010010 в двоичном виде означает операцию сложения (1А) содержимого регистров 1 и 2.
Данные на МЯ представлены числами и символами. Операции являются элементарными и из них строится вся программа. Ввод программы в цифровом виде производился непосредственно в память с пульта ЭВМ либо с примитивных устройств ввода.
Естественно, что процесс программирования был очень трудоемким, разобраться в программе даже автору было довольно сложно, а эффект от применения ЭВМ был довольно низким. Этот этап в развитии ЯП показал, что программирование является сложной проблемой, трудно поддающейся автоматизации, но именно программное обеспечение определяет в конечном счете эффективность применения ЭВМ. Поэтому на всех последующих этапах усилия направлялись на совершенствование интерфейса между программистом и ЭВМ — языка программирования.
Стремление программистов оперировать не цифрами, а символами, привело к созданию мнемонического языка программирования, который называют ассемблером, мнемокодом, автокодом. Этот язык имеет определенный синтаксис записи программ, в котором, в частности, цифровой код операции заменен мнемоническим кодом.
Например, команда сложения записывается в виде AR 1,2 и означает сложение ( Addition ) типа регистр-регистр ( Register ) для регистров 1 и 2. Теперь программа имеет более удобночитаемую форму, но ее не понимает ЭВМ. Поэтому понадобилось создать специальную программу транслятор, который преобразует программу с языка ассемблера на МЯ. Эта проблема потребовала, в свою очередь, глубоких научных исследований и разработки различных теорий, например теорию формальных языков, которые легли в основу создания трансляторов. Практически любой класс ЭВМ имеет свой язык ассемблера. На сегодняшний день язык ассемблера используется для создания системных программ, использующих специфические аппаратные возможности данного класса ЭВМ.
Следующий этап характеризуется созданием языков высокого уровня (ЯВУ). Эти языки являются универсальными (на них можно создавать любые прикладные программы) и алгоритмически полными, имеют более широкий спектр типов данных и операций, поддерживают технологии программирования. На этих языках создается неисчислимое множество различных прикладных программ.
Принципиальными отличиями ЯВУ от языков низкого уровня являются:
· возможность записи сложных выражений;
· расширяемость типов данных за счет конструирования новых типов из базовых;
· расширяемость набора операций за счет подключения библиотек подпрограмм;
· слабая зависимость от типа ЭВМ.
С усложнением ЯП усложняются и трансляторы для них. Теперь в набор инструментов программиста, кроме транслятора, входит текстовый редактор для ввода текста программ, отладчик для устранения ошибок, библиотекарь для создания библиотек программных модулей и множество других служебных программ. Все вместе это называется системой программирования. Наиболее яркими представителями ЯВУ являются FORTRAN , PL /1, Pascal , C , Basic , Ada .
Может возникнуть вопрос: почему создано столько различных языков одного класса? Почему нельзя создать один язык на все случаи жизни? Ответ на этот вопрос может быть таким же, как и на вопрос о различных языках народов мира: так уж получилось.
Каждый из разработчиков ЯВУ стремился создать самый лучший и самый универсальный язык, который позволял бы быстро получать самые эффективные, надежные и безошибочные программы. Однако в процессе этого поиска выяснилось, что дело не в самом языке, а в технологии его использования. Поэтому дальнейшее развитие языков стало определяться новыми технологиями программирования.
Одновременно с развитием универсальных ЯВУ стали развиваться проблемно-ориентированные ЯП, которые решали экономические задачи ( COBOL ), задачи реального времени ( Modula -2, Ada ), символьной обработки ( Snobol ), моделирования ( GPSS , Simula , SmallTalk ), численно-аналитические задачи ( Analitic ) и другие. Эти специализированные языки позволяли более адекватно описывать объекты и явления реального мира, приближая язык программирования к языку специалиста в проблемной области.
Другим направлением развития ЯП является создание языков сверхвысокого уровня (ЯСВУ).
На языке высокого уровня программист задает процедуру (алгоритм) получения результата по известным исходным данным, поэтому они называются процедурными ЯП.
На ЯСВУ программист задает отношения между объектами в программе, например систему линейных уравнений, и определяет, что нужно найти, но не задает как получить результат. Такие языки еще называют непроцедурными, т.к. сама процедура поиска решения встроена в язык (в его интерпретатор). Такие языки используются, например, для решения задач искусственного интеллекта ( Lisp , Prolog ) и позволяют моделировать мыслительную деятельность человека в процессе поиска решений.
К непроцедурным языкам относят и языки запросов систем управления базами данных ( QBE , SQL ).
Источник: shamsutdinovauma.blogspot.com
ЦП Автоматизированные системы управления и промышленная безопасность
25. Алгоритм и его свойства. Способы записи алгоритмов
26.08.2014 14:18 Александр
Понятие алгоритма — одно из самых фундаментальных понятий информатики. Алгоритмизация наряду с моделированием выступает в качестве общего метода информатики. К реализации определенных алгоритмов сводятся процессы управления в различных системах, что делает понятие алгоритма близким к кибернетике.
Алгоритмы являются объектом систематического исследования пограничной между математикой и информатикой научной дисциплины, примыкающей к математической логике — теории алгоритмов. Особенность положения, однако, состоит в том, что при решении практических задач, предполагающих разработку алгоритмов для реализации на ЭВМ, и тем более при использовании на практике информационных технологий, можно, как правило, не опираться на высокую формализацию данного понятия, и поэтому представляется целесообразным познакомиться с алгоритмами и алгоритмизацией на основе содержательного толкования сущности понятия алгоритма и рассмотрения основных его свойств. При таком подходе алгоритмизация более выступает в основном как набор определенных практических приемов, особых специфических навыков рационального мышления в рамках заданных языковых средств. Можно провести аналогию между этим обстоятельством и рассмотренным выше подходом к измерению информации: тонкие математические построения при «кибернетическом» подходе не очень нужны при использовании гораздо более простого «объемного» подхода при практической работе с компьютером.
Само слово «алгоритм» происходит от algorithmi — латинской формы написания имени великого математика IX века аль-Хорезми, который сформулировал правила выполнения арифметических действий. Первоначально под алгоритмами и понимали только правила выполнения четырех арифметических действий над многозначными числами.
Алгоритм — это определенным образом организованная последовательность действий, за конечное число шагов приводящая к решению задачи.
Алгоритм должен быть составлен таким образом, чтобы исполнитель, в расчете на которого он создается, мог однозначно и точно следовать командам алгоритма и эффективно получать определенный результат. Это накладывает на записи алгоритмов целый ряд обязательных требований, суть которых вытекает, вообще говоря, уже из приведенного выше неформального толкования понятия алгоритма. Сформируем эти требования в виде перечня свойств, которым должны удовлетворять алгоритмы, адресуемые заданному исполнителю.
1. Одно из первоначальных требований, которое предъявляется к алгоритму, состоит в том, что описываемый процесс должен быть разбит на последовательность отдельных шагов. Возникающая в результате такого разбиения запись представляет собой упорядоченную совокупность четко отделенных друг от друга предписаний (директив, команд, операторов), образующих прерывную (или, как говорят, дискретную) структуру алгоритма. Только выполнив требования одного предписания, можно приступить к выполнению следующего. Дискретная структура алгоритмической записи может, например, подчеркиваться сквозной нумерацией отдельных команд алгоритма, хотя это требование не является обязательным. Рассмотренное свойство алгоритмов называют дискретность.
2. Используемые на практике алгоритмы составляются с ориентацией на определенного исполнителя. Чтобы составить для него алгоритм, нужно знать, какие команды этот исполнитель может понять и исполнить, а какие не может. Известно, что у каждого исполнителя имеется своя система команд. Очевидно, что, составляя запись алгоритма для определенного исполнителя, можно использовать лишь те команды, которые имеются в его СКИ. Это свойство алгоритмов будем называть понятностью.
3. Будучи понятным, алгоритм не должен все же содержать предписаний, смысл которых может восприниматься неоднозначно. Это означает, что одна и та же команда, будучи понятна разным исполнителям, после исполнения каждым из них должна давать одинаковый результат.
В данном случае речь фактически идет о том, что запись алгоритма должна быть настолько четкой, полной и продуманной в деталях, чтобы у исполнителя никогда не могло возникнуть потребности в принятии каких-либо самостоятельных решений, не предусмотренных составителем алгоритма. Говоря иначе, алгоритм не должен оставлять места для произвола исполнителя. Кроме того, в алгоритмах недопустимы также ситуации, когда после выполнения очередной команды алгоритма исполнителю неясно, какая из команд алгоритма должна выполняться на следующем шаге. Отмеченное свойства алгоритмов называют определенностью или детерминированностью.
4. Обязательное требование к алгоритмам — результативность. Смысл этого требования состоит в том, что при точном исполнении всех предписаний алгоритма процесс должен прекратиться за конечное число шагов и при этом должен получиться определенный ответ на вопрос задачи (либо вывод о том, что решения не существует).
5. Наиболее распространены алгоритмы, обеспечивающие решение не одной исключительной задачи, а некоторого класса задач данного типа. Это свойство алгоритма называют массовостью. В простейшем случае массовость обеспечивает возможность использования различных значений исходных данных.
Способы записи алгоритма
Основными изобразительными средствами алгоритмов являются следующие способы их записи:
Формульно-словесный способ — это задание инструкций с использованием математических символов и выражений в сочетании со словесными пояснениями.
Блок-схемный способ — это графическое изображение логической структуры алгоритма, в котором каждый этап процесса переработки данных представляется в виде геометрических фигур (блоков), имеющих определенную конфигурацию в зависимости от характера выполняемых операций.
В приведенной ниже табл.16 представлены основные блоки, используемые при построении алгоритма в блок-схемной форме.
Таблица 16. Графические изображения блок-схем
Доказано, что любую программу можно написать, используя комбинации трех управляющих структур:
— следования, или последовательности операторов;
— развилки, или условного оператора;
— повторения или оператора цикла.
Программа, составленная из канонических структур, будет называться регулярной программой, т.е. иметь 1 вход и 1 выход, каждый оператор в программе может быть достигнут при входе через ее начало (нет недостижимых операторов и бесконечных циклов). Управление в такой программе передается сверху вниз. Снабженные комментариями, такие программы хорошо читабельны.
Источник: www.automationlab.ru