Информатика
Алгоритмы и способы их описания.
Алгоритм — это система точных и понятных предписаний о содержании и последовательности выполнения конечного числа действий, необходимых для решения любой задачи данного типа.
Примеры: правила сложения, умножения, решения алгебраических уравнений и т.п.
1.Универсальность (массовость) — применимость алгоритма к различным наборам исходных данных.
2.Дискретность — процесс решения задачи по алгоритму разбит на отдельные действия.
3.Конечность — каждое из действий и весь алгоритм в целом обязательно завершаются.
4.Результативность — по завершении выполнения алгоритма обязательно получается конечный результат.
5.Выполнимость (эффективность) — результата алгоритма достигается за конечное число шагов.
6.Детерминированность (определенность) — алгоритм не должен содержать предписаний, смысл которых может восприниматься неоднозначно. Т.е. одно и то же предписание после исполнения должно давать один и тот же результат.
7.Последовательность – порядок исполнения команд должен быть понятен исполнителю и не должен допускать неоднозначности.
1. вычислительные алгоритмы , работающие со сравнительно простыми видами данных, такими как числа и матрицы, хотя сам процесс вычисления может быть долгим и сложным;
2. информационные алгоритмы , представляющие собой набор сравнительно простых процедур, работающих с большими объемами информации (алгоритмы баз данных);
3. управляющие алгоритмы , генерирующие различные управляющие воздействия на основе данных, полученных от внешних процессов, которыми алгоритмы управляют.
По типу передачи управления алгоритмы бывают: основные (главные выполняемые программы) и вспомогательные (подпрограммы).
Для задания алгоритма необходимо описать следующие его элементы:
1.набор объектов, составляющих совокупность возможных исходных данных, промежуточных и конечных результатов;
3.правило непосредственной переработки информации (описание последовательности действий);
5.правило извлечения результатов.
Способы описания алгоритмов.
Символьный, когда алгоритм описывается с помощью специального набора символов (специального языка).
Словесная форма записи алгоритмов обычно используется для алгоритмов, ориентированных на исполнителя-человека. Команды такого алгоритма выполняются в естественной последовательности, если не оговорено противного.
Графическая запись с помощью блок-схем осуществляется рисованием последовательности геометрических фигур, каждая из которых подразумевает выполнение определенного действия алгоритма. Порядок выполнения действий указывается стрелками. Графическая запись алгоритма имеет ряд преимуществ: каждая операция вычислительного процесса изображается отдельной геометрической фигурой и графическое изображение алгоритма наглядно показывает разветвления путей решения задачи в зависимости от различных условий, повторение отдельных этапов вычислительного процесса и другие детали.
Правила создания блок – схем:
1.Линии, соединяющие блоки и указывающие последовательность связей между ними, должны проводится параллельно линиям рамки.
2.Стрелка в конце линии может не ставиться, если линия направлена слева направо или сверху вниз.
3.В блок может входить несколько линий, то есть блок может являться преемником любого числа блоков.
4.Из блока (кроме логического) может выходить только одна линия.
5.Логический блок может иметь в качестве продолжения один из двух блоков, и из него выходят две линии.
6.Если на схеме имеет место слияние линий, то место пересечения выделяется точкой. В случае, когда одна линия подходит к другой и слияние их явно выражено, точку можно не ставить.
7.Схему алгоритма следует выполнять как единое целое, однако в случае необходимости допускается обрывать линии, соединяющие блоки.
В линейном алгоритме операции выполняются последовательно, в порядке их записи. Каждая операция является самостоятельной, независимой от каких-либо условий. На схеме блоки, отображающие эти операции, располагаются в линейной последовательности.
В алгоритме с ветвлением предусмотрено несколько направлений (ветвей). Каждое отдельное направление алгоритма обработки данных является отдельной ветвью вычислений. Направление ветвления выбирается логической проверкой, в результате которой возможны два ответа:
1.«да» — условие выполнено.
2.«нет» — условие не выполнено.
Циклические алгоритмы содержат цикл – это многократно повторяемый участок алгоритма.Различают циклы с предусловием и постусловием.Также циклы бывают детерминированные и итерационные.Цикл называется детерминированным, если число повторений тела цикла заранее известно или определено. Цикл называется итерационным, если число повторений тела цикла заранее неизвестно, а зависит от значений параметров (некоторых переменных), участвующих в вычислениях.
Источник
Каковы основные способы описания алгоритма
Различают следующие виды алгоритмов :
линейный – список команд (указаний), выполняемых последовательно друг за другом;
разветвляющийся – алгоритм, содержащий хотя бы одну проверку условия, в результате которой обеспечивается переход на один из возможных вариантов решения;
циклический – алгоритм, предусматривающий многократное повторение одной и той же последовательности действий. Количество повторений обусловливается исходными данными или условием задачи.
Любая алгоритмическая конструкция может содержать в себе другую конструкцию того же или иного вида, т. е. алгоритмические конструкции могут быть вложенными. Рассмотрим следующие способы описания алгоритма: словесное описание, псевдокод, блок-схема, программа.
Словесное описание представляет структуру алгоритма на естественном языке. Например, любой прибор бытовой техники (утюг,электропила, дрель и т.п.) имеет инструкцию по эксплуатации, т.е.словесное описания алгоритма, в соответствии которому данный прибор должен использоваться. Никаких правил составления словесного описания не существует. Запись алгоритма осуществляется в произвольной форме на естественном, например, русском языке. Этот способ описания не имеет широкого распространения, так как строго не формализуем (под «формальным» понимается то, что описание абсолютно полное и учитывает все возможные ситуации, которые могут возникнуть в ходе решения); допускает неоднозначность толкования при описании некоторых действий; страдает многословностью.
1. определить температуру воздуха
2. если температура ниже 0, то надеть шубу, иначе надеть куртку
Псевдокод — описание структуры алгоритма на естественном, частично формализованном языке, позволяющее выявить основныеэтапы решения задачи, перед точной его записью на языке программирования. В псевдокоде используются некоторые формальные конструкции и общепринятая математическая символика. Строгих синтаксических правил для записи псевдокода не существует. Это облегчает запись алгоритма при проектировании и позволяет описать алгоритм, используя любой набор команд. Однако в псевдокоде обычно используются некоторые конструкции, присущие формальным языкам, что облегчает переход от псевдокода к записи алгоритма на языке программирования. Единого или формального определения псевдокода не существует, поэтому возможны различные псевдокоды, отличающиеся набором используемых слов и конструкций.
Блок-схема — описание структуры алгоритма с помощью геометрических фигур с линиями-связями, показывающими порядок выполнения отдельных инструкций. Этот способ имеет ряд преимуществ. Благодаря наглядности, он обеспечивает «читаемость»алгоритма и явно отображает порядок выполнения отдельных команд. В блок-схеме каждой формальной конструкции соответствует определенная геометрическая фигура или связанная линиями совокупность фигур.
Описания алгоритма в словесной форме, на псевдокоде или в виде блок-схемы допускают некоторый произвол при изображении команд. Вместе с тем они настолько достаточны, что позволяет человеку понять суть дела и исполнить алгоритм. На практике исполнителями алгоритмов выступают компьютеры. Поэтому алгоритм, предназначенный для исполнения на компьютере, должен быть записан на «понятном» ему языке, такой формализованный язык называют языком программирования .
Источник
Конспект Способы описания алгоритмов
Информатика и ИКТ. 9 класс. Основы алгоритмизации.
Свойства алгоритмов. Способы записи алгоритмов.
Цель урока: описать свойства алгоритмов, представить алгоритмы с помощью конкретных изобразительных средств, состав и правила употребления которых образуют конкретные способы или формы записи.
Актуализация опорных знаний (опрос по теме прошлого урока)
Дайте определение «алгоритм»?
Происхождение понятия «алгоритм»?
Какие виды алгоритмов существуют?
Изучение нового материала:
Значение слова «алгоритм» является синонимом таких понятий, как «набор инструкций», «последовательность действий», «метод». Однако, в отличие от них, алгоритм характеризуется определенными свойствами.
Свойства алгоритма – это набор свойств, отличающих алгоритм от любых предписаний и обеспечивающих его автоматическое исполнение. Алгоритм обладает следующим набором основных свойств: дискретностью, массовостью, формальностью, результативностью, определенностью.
Дискретность (разрывность) – это свойство алгоритма, характеризующее его структуру: каждый алгоритм состоит из отдельных законченных действий, т. е. «делится на шаги».
Массовость – применимость алгоритма ко всем задачам рассматриваемого типа, при любых исходных данных.
Определенность (детерминированность, точность) – свойство алгоритма, указывающее на то, что каждый шаг алгоритма должен быть строго определен и не допускать различных толкований; также строго должен быть определен порядок выполнения отдельных шагов.
Результативность – свойство, состоящее в том, что любой алгоритм должен завершаться за конечное (пусть даже очень большое) число шагов.
Формальность – это свойство указывает на то, что любой исполнитель, способный воспринимать и выполнять инструкции алгоритма, действует формально, т. е. отвлекается от содержания поставленной задачи и лишь строго выполняет инструкции. Другими словами, механически выполняя все указанные в алгоритме этапы в требуемом порядке, исполнитель может всегда правильно решить задачу.
Процесс разработки алгоритма называется алгоритмизацией и требует четкого и полного понимания задачи. Сущность алгоритмизации вычислительного процесса проявляется в следующих действиях, отражающих его свойства:
выделении законченных частей вычислительного процесса;
формальной записи каждого из них;
назначении определенного порядка выполнения выделенных частей;
проверки правильности выбранного алгоритма по реализации заданного метода вычислений.
Способы записи алгоритмов
На любой стадии существования алгоритмы представляют с помощью конкретных изобразительных средств, состав и правила употребления которых образуют конкретные способы или формы записи. К настоящему времени сложились пять наиболее употребительных способов записи:
графический способ (блок-схема);
программа (способ описания с помощью языков программирования).
Словесное описание представляет алгоритм – инструкцию о выполнении действий в определенной последовательности с помощью слов и предложений естественного языка. Форма изложения произвольна и устанавливается разработчиком.
Этот способ описания не имеет широкого распространения, т. к. строго не формализуем (под «формальным» понимается то, что описание абсолютно полное и учитывает все возможные ситуации, которые могут возникнуть в ходе решения), допускает неоднозначность толкования при описании некоторых действий, страдает многословностью.
Алгоритм нахождения наибольшего общего делителя (НОД) двух натуральных чисел.
задать два числа;
если числа равны, то взять любое из них в качестве ответа и остановиться, в противном случае продолжить выполнение алгоритма;
определить большее из чисел;
заменить большее из чисел разностью большего и меньшего из чисел;
повторить алгоритм с п. 2.
Алгоритм выполнения домашнего задания по математике.
посмотреть, что задано;
взять учебник и тетрадь по предмету;
прочитать параграф и выполнить письменные упражнения;
сравнить полученные результаты с ответами в конце учебника;
если ответы совпадают, закрыть тетрадь и учебник, если нет – повторить алгоритм с п. 4.
Формульно-словесный способ записи действий содержит формальные символы и выражения (формулы) в сочетании со словесными пояснениями. Т.е. алгоритм записывается в виде текста с формулами по пунктам, определяющим последовательность действий. Этот способ описания нагляден, лаконичен, но не является строго формальным.
Алгоритм вычисления следующего выражения: у=2∙а–(х+6).
ввести значения а и х;
найти произведение (2∙а);
вычислить y как разность y=2∙a–(x+6);
вывести у как результат вычисления выражения.
Алгоритм решения задачи по геометрии.
Дано: высота треугольника AH=2 см, основание треугольника BC= 5 см.
Найти: площадь S ∆ABC.
Решение: Площадь треугольника находится по формуле 
Подставим данные задачи: 
Результат: 
Псевдокод представляет собой описание структуры алгоритма на естественном, частично-формализованном языке, позволяющее выявить основные этапы решения задачи перед точной его записью на языке программирования.
В псевдокоде используются некоторые формальные конструкции и общепринятая математическая символика. Данный способ тесно связан со структурным подходом к программированию. Псевдокод занимает промежуточное положение между естественным языком и языком программирования. Его применяют преимущественно для того, чтобы подробнее объяснить работу программы, что облегчает проверку правильности программы.
Алгоритм сложения двух чисел.
Ввод двух чисел a и b.
Вычисление суммы S=a+b.
Алгоритм заполнения зачетной ведомости группы из 20 студентов (i – номер студента).
i от 1 до 20 с шагом 1
1.1. ввести фамилию студента
1.2. поставить оценку.
Графическая запись, или блок-схема, – описание структуры алгоритма с помощью геометрических фигур с линиями связями, показывающими порядок выполнения отдельных инструкций. Описание алгоритмов с помощью схем – один из наиболее наглядных и компактных способов. Этот способ имеет ряд преимуществ перед остальными:
наглядное отображение базовых конструкций алгоритма;
концентрация внимания на структуре алгоритма;
использование принципа блочности при коллективном решении сложной задачи;
преобразование алгоритма методом укрупнения (сведения к единому блоку) или детализации (разбиения на ряд блоков);
быстрая проверка разработанного алгоритма.
В блок-схеме каждому типу действий (вводу исходных данных, вычислению значений выражений, проверке условий, управлению повторением действий, окончанию обработки и т. п.) соответствует геометрическая фигура, называемая блоком. Блочные символы соединяются линиями переходов (стрелками), определяющими очередность выполнения действий.
Условные графические изображения, используемые при построении схем, называются символами. Система символов и правила построения алгоритмов определены соответствующими стандартами: блок-схема выстраивается в одном направлении: либо сверху вниз, либо слева направо, в порядке выполнения действий.
Для наглядности операции разного вида изображаются в схеме различными геометрическими фигурами (таблица).
Средства графического изображения алгоритмов
Обозначает начало и конец алгоритма
Ввод и вывод данных
Наличие условия в алгоритме
Наличие цикла в алгоритме
Разрыв алгоритма (соединительные блоки)
——— 
Терминатор (пуск-остановка). Элемент отображает вход из внешней среды или выход из нее (наиболее частое применение − начало и конец алгоритма). Внутри фигуры записывается соответствующее действие − начало/конец.
Данные (ввод-вывод). Преобразование данных в форму, пригодную для обработки (ввод) или отображения результатов обработки (вывод). Данный символ не определяет типа носителя данных.
Процесс. Выполнение одной или нескольких операций, обработка данных любого вида (изменение значения данных, формы представления, расположения). Внутри фигуры записывают непосредственно сами операции. В этом блоке знак «=» означает не математическое равенство, а операцию присваивания.
Решение. Отображает решение или функцию переключательного типа с одним входом и двумя или более альтернативными выходами, из которых только один может быть выбран после вычисления условий, определенных внутри этого элемента. Вход в элемент обозначается линией, входящей обычно в верхнюю вершину элемента. Если выходов два или три, то обычно каждый выход обозначается линией, выходящей из оставшихся вершин (боковых и нижней). Если выходов больше трех, то их следует показывать одной линией, выходящей из вершины (чаще нижней) элемента, которая затем разветвляется.
Соответствующие результаты вычислений могут записываться рядом с линиями, отображающими эти пути.
Граница цикла. Условия цикла и приращения записываются внутри символа цикла − в зависимости от типа организации цикла. Для изображения итерационного цикла на блок-схеме вместо данного символа используют символ решения, указывая в нем условие, а одну из линий выхода замыкают выше в блок-схеме (перед операциями цикла).
Предопределенный процесс. Символ отображает выполнение процесса, состоящего из одной или нескольких операций, который определен в другом месте программы (в подпрограмме, модуле). Внутри символа записывается название процесса и передаваемые в него данные.
Соединитель. Используется для обрыва линии и продолжения ее в другом месте (пример: разделение блок-схемы, не помещающейся на листе).
Соответствующие соединительные символы должны иметь одно (при том уникальное) обозначение.
Комментарий. Позволяет включать в схемы алгоритмов пояснения к функциональным блокам. Частое использование комментариев нежелательно, т. к. это усложняет (загромождает) схему, делает ее менее наглядной.
Алгоритм сложения двух чисел.
Алгоритм совершения покупок в магазине.
Составление блок-схемы алгоритма является важным и необходимым этапом решения задачи. Но, т. к. в таком виде алгоритм не может быть выполнен непосредственно ЭВМ, этот этап является промежуточным, значительно облегчающим процесс составления программы.
Программа − это алгоритм, записанный в виде последовательности команд, понятных ЭВМ (машинных команд). При записи алгоритмов в виде программ для ЭВМ используются языки программирования — системы кодирования предписаний и правила их использования. Такие языки являются искусственными языками со строго определенными синтаксисом и пунктуацией. Они не допускают свободного толкования для своих конструкций, как это характерно для естественного языка. Существует большое количество языков программирования, предназначенных для решения прикладных задач.
Для записи алгоритмов в виде программ характерна высокая степень формализации. Перед составлением программ чаще всего используются словесно-формульный или графический способы.
Алгоритм сложения двух чисел. Программа, записанная на языке Qbasic:
Rem Вычисление суммы двух чисел
Input «Введите число a»; a
Input «Введите число b»; b
Print « Сумма a+b=»; a+b
Составить алгоритм вычисления значения функции y=7x+5 при любом значении x.
Составить алгоритм вычисления периметра квадрата, если известна его сторона.
Составить алгоритм вычисления длины окружности, если известен ее радиус.
Составить алгоритм вычисления площади окружности, если известен ее диаметр.
Записи в тетради, повторить понятие «алгоритма».
Беляев Д. М. МАОУ лицей № 21 г. Тамбов
Источник
