АЛГОРИТМ – система правил, сформулированная на понятном исполнителю языке, которая определяет процесс перехода от допустимых исходных данных к некоторому результату и обладает свойствами массовости, конечности, определенности, детерминированности.
Также по теме:
Слово «алгоритм» происходит от имени великого среднеазиатского ученого 8–9 вв. Аль-Хорезми (Хорезм – историческая область на территории современного Узбекистана). Из математических работ Аль-Хорезми до нас дошли только две – алгебраическая (от названия этой книги родилось слово алгебра) и арифметическая.
Вторая книга долгое время считалась потерянной, но в 1857 в библиотеке Кембриджского университета был найден ее перевод на латинский язык. В ней описаны четыре правила арифметических действий, практически те же, что используются и сейчас. Первые строки этой книги были переведены так: «Сказал Алгоритми. Воздадим должную хвалу Богу, нашему вождю и защитнику».
Так имя Аль-Хорезми перешло в Алгоритми, откуда и появилось слово алгоритм. Термин алгоритм употреблялся для обозначения четырех арифметических операций, именно в таком значении он и вошел в некоторые европейские языки. Например, в авторитетном словаре английского языка Webster’s New World Dictionary, изданном в 1957, слово алгоритм снабжено пометкой «устаревшее» и объясняется как выполнение арифметических действий с помощью арабских цифр.
Урок 1. Понятие алгоритма. Свойства и виды
Слово «алгоритм» вновь стало употребительным с появлением электронных вычислительных машин для обозначения совокупности действий, составляющих некоторый процесс. Здесь подразумевается не только процесс решения некоторой математической задачи, но и кулинарный рецепт и инструкция по использованию стиральной машины, и многие другие последовательные правила, не имеющие отношения к математике, – все эти правила являются алгоритмами. Слово «алгоритм» в наши дни известно каждому, оно настолько уверенно шагнуло в разговорную речь, что сейчас нередко на страницах газет, в выступлениях политиков встречаются выражения «алгоритм поведения», «алгоритм успеха» и т.д.
Проблема определения понятия «алгоритм».
Также по теме:
На протяжении многих веков понятие алгоритма связывалось с числами и относительно простыми действиями над ними, да и сама математика была, по большей части, наукой о вычислениях, наукой прикладной. Чаще всего алгоритмы представлялись в виде математических формул.
Порядок элементарных шагов алгоритма задавался расстановкой скобок, а сами шаги заключались в выполнении арифметических операций и операций отношения (проверки равенства, неравенства и т.д.). Часто вычисления были громоздкими, а вычисления вручную – трудоемкими, но суть самого вычислительного процесса оставалась очевидной.
У математиков не возникала потребность в осознании и строгом определении понятия алгоритма, в его обобщении. Но с развитием математики появлялись новые объекты, которыми приходилось оперировать: векторы, графы, матрицы, множества и др. Как определить для них однозначность или как установить конечность алгоритма, какие шаги считать элементарными? В 1920-х задача точного определения понятия алгоритма стала одной из центральных проблем математики. В то время существовало две точки зрения на математические проблемы:
Понятие алгоритма и его свойства. Алгоритмы и структуры данных.
Все проблемы алгоритмически разрешимы, но для некоторых алгоритм еще не найден, поскольку еще не развиты соответствующие разделы математики.
Есть проблемы, для которых алгоритм вообще не может существовать.
Идея о существовании алгоритмически неразрешимых проблем оказалась верной, но для того, чтобы ее обосновать, необходимо было дать точное определение алгоритма. Попытки выработать такое определение привели к возникновению теории алгоритмов, в которую вошли труды многих известных математиков – К.Гедель, К.Черч, С.Клини, А.Тьюринг, Э.Пост, А.Марков, А.Колмогоров и многие другие.
Точное определение понятия алгоритма дало возможность доказать алгоритмическую неразрешимость многих математических проблем.
Появление первых проектов вычислительных машин стимулировало исследование возможностей практического применения алгоритмов, использование которых, ввиду их трудоемкости, было ранее недоступно. Дальнейший процесс развития вычислительной техники определил развитие теоретических и прикладных аспектов изучения алгоритмов.
Понятие «алгоритма».
В повседневной жизни каждый человек сталкивается с необходимостью решения задач самой разной сложности. Некоторые из них трудны и требуют длительных размышлений для поиска решений (а иногда его так и не удается найти), другие же, напротив, столь просты и привычны, что решаются автоматически.
При этом выполнение даже самой простой задачи осуществляется в несколько последовательных этапов (шагов). В виде последовательности шагов можно описать процесс решения многих задач, известных из школьного курса математики: приведение дробей к общему знаменателю, решение системы линейных уравнений путем последовательного исключения неизвестных, построение треугольника по трем сторонам с помощью циркуля и линейки и т.д.
Такая последовательность шагов в решении задачи называется алгоритмом. Каждое отдельное действие – это шаг алгоритма. Последовательность шагов алгоритма строго фиксирована, т.е. шаги должны быть упорядоченными. Правда, существуют параллельные алгоритмы, для которых это требование не соблюдается.
Понятие алгоритма близко к другим понятиям, таким, как метод (метод Гаусса решения систем линейных уравнений), способ (способ построения треугольника по трем сторонам с помощью циркуля и линейки). Можно сформулировать основные особенности именно алгоритмов.
Наличие исходных данных и некоторого результата.
Алгоритм – это точно определенная инструкция, последовательно применяя которую к исходным данным, можно получить решение задачи. Для каждого алгоритма есть некоторое множество объектов, допустимых в качестве исходных данных. Например, в алгоритме деления вещественных чисел делимое может быть любым, а делитель не может быть равен нулю.
Массовость, т.е. возможность применять многократно один и тот же алгоритм. Алгоритм служит, как правило, для решения не одной конкретной задачи, а некоторого класса задач. Так алгоритм сложения применим к любой паре натуральных чисел.
Детерминированность.
При применении алгоритма к одним и тем же исходным данным должен получаться всегда один и тот же результат, поэтому, например, процесс преобразования информации, в котором участвует бросание монеты, не является детерминированным и не может быть назван алгоритмом.
Результативность.
Выполнение алгоритма должно обязательно приводить к его завершению. В то же время можно привести примеры формально бесконечных алгоритмов, широко применяемых на практике. Например, алгоритм работы системы сбора метеорологических данных состоит в непрерывном повторении последовательности действий («измерить температуру воздуха», «определить атмосферное давление»), выполняемых с определенной частотой (через минуту, час) во все время существования данной системы.
Определенность.
На каждом шаге алгоритма у исполнителя должно быть достаточно информации, чтобы его выполнить. Кроме того, исполнителю нужно четко знать, каким образом он выполняется. Шаги инструкции должны быть достаточно простыми, элементарными, а исполнитель должен однозначно понимать смысл каждого шага последовательности действий, составляющих алгоритм (при вычислении площади прямоугольника любому исполнителю нужно уметь умножать и трактовать знак «x» именно как умножение). Поэтому вопрос о выборе формы представления алгоритма очень важен. Фактически речь идет о том, на каком языке записан алгоритм.
Формы представления алгоритмов.
Для записи алгоритмов необходим некоторый язык, при этом очень важно, какой именно язык выбран. Записывать алгоритмы на русском языке (или любом другом естественном языке) громоздко и неудобно.
Например, описание алгоритма Евклида нахождения НОД (наибольшего общего делителя) двух целых положительных чисел может быть представлено в виде трех шагов. Шаг 1: Разделить m на n. Пусть p – остаток от деления.
Шаг 2: Если p равно нулю, то n и есть исходный НОД.
Шаг 3: Если p не равно нулю, то сделаем m равным n, а n равным p. Вернуться к шагу 1.
Приведенная здесь запись алгоритма нахождения НОД очень упрощенная. Запись, данная Евклидом, представляет собой страницу текста, причем последовательность действий существенно сложней.
Одним из распространенных способов записи алгоритмов является запись на языке блок-схем. Запись представляет собой набор элементов (блоков), соединенных стрелками. Каждый элемент – это «шаг» алгоритма. Элементы блок-схемы делятся на два вида.
Элементы, содержащие инструкцию выполнения какого-либо действия, обозначают прямоугольниками, а элементы, содержащие проверку условия – ромбами. Из прямоугольников всегда выходит только одна стрелка (входить может несколько), а из ромбов – две (одна из них помечается словом «да», другая – словом «нет», они показывают, соответственно, выполнено или нет проверяемое условие).
На рисунке представлена блок-схема алгоритма нахождения НОД:
Построение блок-схем из элементов всего лишь нескольких типов дает возможность преобразовать их в компьютерные программы и позволяет формализовать этот процесс.
Формализация понятия алгоритмов. Теория алгоритмов.
Приведенное определение алгоритма нельзя считать представленным в привычном математическом смысле. Математические определения фигур, чисел, уравнений, неравенств и многих других объектов очень четки. Каждый математически определенный объект можно сравнить с другим объектом, соответствующим тому же определению.
Например, прямоугольник можно сравнить с другим прямоугольником по площади или по длине периметра. Возможность сравнения математически определенных объектов – важный момент математического изучения этих объектов. Данное определение алгоритма не позволяет сравнивать какие-либо две таким образом определенные инструкции.
Можно, например, сравнить два алгоритма решения системы уравнений и выбрать более подходящий в данном случае, но невозможно сравнить алгоритм перехода через улицу с алгоритмом извлечения квадратного корня. С этой целью нужно формализовать понятие алгоритма, т.е. отвлечься от существа решаемой данным алгоритмом задачи, и выделить свойства различных алгоритмов, привлекая к рассмотрению только его форму записи.
Задача нахождения единообразной формы записи алгоритмов, решающих различные задачи, является одной из основных задач теории алгоритмов. В теории алгоритмов предполагается, что каждый шаг алгоритма таков, что его может выполнить достаточно простое устройство (машина), Желательно, чтобы это устройство было универсальным, т.е. чтобы на нем можно было выполнять любой алгоритм. Механизм работы машины должен быть максимально простым по логической структуре, но настолько точным, чтобы эта структура могла служить предметом математического исследования. Впервые это было сделано американским математиком Эмилем Постом в 1936 (машина Поста) еще до создания современных вычислительных машин и (практически одновременно) английским математиком Аланом Тьюрингом (машина Тьюринга).
История конечных автоматов: машина Поста и машина Тьюринга.
Машина Поста – абстрактная вычислительная машина, предложенная Постом (Emil L.Post), которая отличается от машины Тьюринга большей простотой. Обе машины «эквивалентны» и были созданы для уточнения понятия «алгоритм».
В 1935 американский математик Пост опубликовал в «Журнале символической логики» статью Финитные комбинаторные процессы, формулировка 1. В этой статье и появившейся одновременно в Трудах Лондонского математического общества статье английского математика Тьюринга О вычислимых числах с приложением к проблеме решения были даны первые уточнения понятия «алгоритм».
Важность идей Поста состоит в том, что был предложен простейший способ преобразования информации, именно он построил алгоритмическую систему (алгоритмическая система Поста). Пост доказал, что его система обладает алгоритмической полнотой. В 1967 профессор В.Успенский пересказал эти статьи с новых позиций. Он ввел термин «машина Поста».
Машина Поста – абстрактная машина, которая работает по алгоритмам, разработанным человеком, она решает следующую проблему: если для решения задачи можно построить машину Поста, то она алгоритмически разрешима. В 1970 машина Поста была разработана в металле в Симферопольском университете. Машина Тьюринга была построена в металле в 1973 в Малой Крымской Академии Наук.
Абстрактная машина Поста представляет собой бесконечную ленту, разделенную на одинаковые клетки, каждая из которых может быть либо пустой, либо заполненной меткой «V». У машины есть головка, которая может перемещаться вдоль ленты на одну клетку вправо или влево, наносить в клетку ленты метку, если этой метки там ранее не было, стирать метку, если она была, либо проверять наличие в клетке метки.
Информация о заполненных метками клетках ленты характеризует состояние ленты, которое может меняться в процессе работы машины. В каждый момент времени головка находится над одной из клеток ленты и, как говорят, обозревает ее. Информация о местоположения головки вместе с состоянием ленты характеризует состояние машины Поста. Работа машины Поста заключается в том, что головка передвигается вдоль ленты (на одну клетку за один шаг) влево или вправо, наносит или стирает метки, а также распознает, есть ли метка в клетке в соответствии с заданной программой, состоящей из отдельных команд.
Машина Тьюринга состоит из счетной ленты (разделенной на ячейки и ограниченной слева, но не справа), читающей и пишущей головки, лентопротяжного механизма и операционного исполнительного устройства, которое может находиться в одном из дискретных состояний q0, q1, …, qs , принадлежащих некоторой конечной совокупности (алфавиту внутренних состояний), при этом q0 называется начальным состоянием. Читающая и пишущая головка может читать буквы рабочего алфавита A = a0, a1, …, at >, стирать их и печатать.
Каждая ячейка ленты в каждый момент времени занята буквой из множества А. Чаще всего встречается буква а0 – «пробел». Головка находится в каждый момент времени над некоторой ячейкой ленты – текущей рабочей ячейкой. Лентопротяжный механизм может перемещать ленту так, что головка оказывается над соседней ячейкой ленты, при этом возможна ситуация выхода за левый край ленты, которая является аварийной (недопустимой), или машинного останова, когда машина выполняет предписание об остановке.
Современный взгляд на алгоритмизацию.
Теория алгоритмов строит и изучает конкретные модели алгоритмов. С развитием вычислительной техники и теории программирования возрастает необходимость построения новых экономичных алгоритмов, изменяются способы их построения, способы записи алгоритмов на языке, понятном исполнителю. Особый тип исполнителя алгоритмов – компьютер, поэтому необходимо создавать специальные средства, позволяющие, с одной стороны, разработчику в удобном виде записывать алгоритмы, а с другой – дающие компьютеру возможность понимать написанное. Такими средствами являются языки программирования или алгоритмические языки.
Источник: www.krugosvet.ru
Понятие алгоритма и его характеристики
Термин алгоритм употреблялся ранее для обозначения четырех арифметических операций, именно в таком значении он и вошел в некоторые европейские языки. Слово «алгоритм» вновь стало употребительным с появлением компьютеров для обозначения совокупности действий, составляющих некоторый процесс. Слово «алгоритм» настолько уверенно шагнуло в разговорную речь, что сейчас нередко говорят «алгоритм поведения», «алгоритм действий» и т.д.
Понятие алгоритма и его характеристики
Алгоритм — это точно определенная инструкция, последовательно применяя которую к исходным данным, можно получить решение задачи. Каждое отдельное действие — это шаг алгоритма. Последовательность шагов алгоритма строго фиксирована, т.е. шаги должны быть упорядоченными. Алгоритм — это четко обозначенная последовательность действий конкретному исполнителю для достижения конкретных целей или решения конкретной задачи.
Алгоритм приступает к работе с некоторым набором данных, которые называются входными, и в результате своей работы выдает данные, которые называются выходными. Таким образом, алгоритм преобразует входные данные в выходные.
Свойства алгоритмов:
· понятность. В алгоритме должны быть лишь те инструкции, которые известны исполнителю;
· массовость. С помощью определенного алгоритма должен решаться целый класс задач, т.е. возможность применять многократно один и тот же алгоритм;
· однозначность. При применении алгоритма к одним и тем же исходным данным должен получаться всегда один и тот же результат;
· правильность. Выполнение алгоритма должно давать правильные результаты;
· конечность. Полное выполнения алгоритма должно происходить за конечное число шагов;
· дискретность. Алгоритм должен состоять из отдельных операций, которые выполняются последовательно;
· эффективность. Алгоритм должен обеспечивать решение задачи за наиболее короткое время и с использованием минимальных ресурсов компьютера.
Алгоритмизация — процесс разработки алгоритма (плана действий) для решения задачи.
Можно назвать две формы написания алгоритмов:
· на естественном языке (словесно-пошаговый);
· на языке блок-схем.
В первом случае текст записывают на бумаге или вводят в память компьютера, используя специальные обозначения. При словесной записи алгоритмы записываются в виде текста с формулами по пунктам, определяющими последовательность действий.
Для записи алгоритмов используются средства обычного языка, но наборы слов и фраз не допускают повторений, синонимов, лишних слов. Принимаются определенные соглашения о форме записи, порядке выполнения действий, допускается использование математических символов.
Во втором случае запись представляет собой набор элементов (блоков), соединенных стрелками. Каждый элемент — это «шаг» алгоритма. Элементы блок-схемы делятся на два вида. Элементы, содержащие инструкцию выполнения какого-либо действия, обозначают прямоугольниками, а элементы, содержащие проверку условия — ромбами.
Из прямоугольников всегда выходит только одна стрелка (входить может несколько), а из ромбов — две (одна из них помечается словом «да», другая — словом «нет», они показывают, соответственно, выполнено или нет проверяемое условие). Построение блок-схем из элементов всего лишь нескольких типов дает возможность преобразовать их в компьютерные программы и позволяет формализовать этот процесс.
Графический способ представления алгоритмов имеет ряд преимуществ, благодаря визуальности и явному отображению процесса решения задачи. Алгоритмы, представленные графическими средствами, получили название визуальные алгоритмы. Текстовое описание алгоритма является достаточно компактным и может быть реализовано на абстрактном или реальном языке программирования в виде программы для компьютера.
Общей же для всех графических форматов является возможность либо помещать текст описания внутрь блоков, либо выносить комментарий за пределы рисунка. Каждая фигура блок-схемы обозначает конкретное действие, текст в середине которой дает объяснение конкретной инструкции, а каждая линия должна иметь в себе стрелку, которая говорит о направлении выполнения команд алгоритма. Способ представления алгоритма в виде блок-схемы упрощает алгоритм, дает визуальное понимание его работы.
Правила выполнения схем определяются следующими документами:
· ГОСТ 19.701-90. Схемы алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения;
· ГОСТ 19.002-80. Схемы алгоритмов и программ. Правила выполнения;
· ГОСТ 19.003-80. Схемы алгоритмов и программ. Обозначения условные графические.
Данные документы регулируют способы построения схем и внешний вид их элементов.
Геометрические фигуры визуального способа представления алгоритмов имеют следующий вид. Они представлены во многих учебниках.
Словесная форма представления алгоритма становится более доступной для составления программы, если она написана на псевдоязыке (псевдокоде). Это полуформализованные описания алгоритмов на условном алгоритмическом языке, включающие в себя как элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и др.
Такой язык не транслируется, но позволяет компактно задавать логику исходного описания, в отличие от языка блок- схем. Хотя псевдоязык похож на язык программирования, но в нем нет такой синтаксической строгости, как, собственно, у языка программирования. Поэтому, на псевдоязыке удобно демонстрировать или разрабатывать алгоритмы, но нельзя написать работающую программу. Он занимает промежуточное место между естественным и формальным языками.
Алгоритмы можно преобразовывать из одной формы в другую и обратно. Формализация блок-схемы — превращение обычного описания в формальное. Это точное описание правил, по которым выполняется задачи. В ходе формализации необходимо разбить задачу на отдельные действия, указать последовательность их выполнения, а также условия, при которых выполняется (или не выполняется) каждое действие. В результате формализации описание задачи превращается в алгоритм.
Эргономизация блок-схем — облегчение и улучшение алгоритма с помощью сокращения лишних процедур, повышения степени наглядности, доходчивости, чтобы минимизировать умственные затраты на процесс познания, понимания и решения задач.
Базовые структуры алгоритмов. Базовые алгоритмические конструкции — это способы управления обработкой информации. На сегодняшний день существует три базовых структуры: линейные алгоритмы; алгоритмы ветвления; циклические алгоритмы.
Структура – линейный алгоритм
Линейный алгоритм — набор команд, выполняемых последовательно во времени друг за другом. Такой алгоритм в любом случае не будет иметь условных и безусловных переходов. Итак, линейный алгоритм — алгоритм, все этапы которого выполняются однократно и строго последовательно.
Разветвляющийся алгоритм — алгоритм, содержащий хотя бы одно условие, в результате проверки которого обеспечивается переход на один из двух возможных шагов.
Признаком разветвляющегося алгоритма является наличие операций условного перехода, когда происходит проверка истинности некоторого логического выражения (проверяемое условие) и в зависимости от истинности или ложности проверяемого условия для выполнения выбирается та или иная ветвь алгоритма.
Алгоритм предполагает выполнение Плечо 1, если записанное условие истинно (выполняется), и выполнение Плечо 2 (если условие ложно (не выполняется). Это полное ветвление.
В частном случае может отсутствовать один из блоков » Плечо 1” или » Плечо 2”. Циклический алгоритм — алгоритм, предусматривающий многократное повторение одного и того же действия (одних и тех же операций) над новыми исходными данными. К циклическим алгоритмам сводится большинство методов вычислений, перебора вариантов. Цикл программы — последовательность команд, которая может выполняться многократно (для новых исходных данных) до удовлетворения некоторого условия.
Последовательность действий, которые повторяются в цикле, называют телом цикла На рисунке показан цикл с предусловием. Оператор тела цикла будет повторяться до тех пор, пока значение условия не станет истинным. Цикл с предусловием часто называют «циклом типа пока» (сначала выполняется условие, потом оператор).
В цикле с постусловием (цикле типа до) сначала выполняется оператор, потом — условие. В этом случае оператор будет выполняться хотя бы один раз. В цикле с предусловием проверяется условие продолжения цикла, в цикле с постусловием — условие выхода из цикла.
Но нужно помнить, что количество повторений цикла должно быть всегда конечное число, иначе произойдет зацикливание и решение задачи не сможет закончиться.
Часто встречаются циклы со счетчиком. Этот вид цикла используется в тех случаях, когда точно известно количество повторений цикла. Для того, чтобы считать эти повторения, вводится специальная переменная — счетчик цикла. Цикл со счетчиком реализуется с помощью рекурсивного увеличения значения счетчика в теле цикла.
Нередко при алгоритмическом решении задачи возникает необходимость создания цикла, содержащего в своем теле другой цикл. Такие вложенные друг в друга циклы относятся к структурам вложенных циклов.
Помимо последовательных алгоритмов часто строится параллельный алгоритм, который может быть реализован по частям на множестве различных вычислительных устройств с последующим объединением полученных результатов и получением корректного результата. Параллельные алгоритмы весьма важны ввиду постоянного совершенствования многопроцессорных систем и увеличения числа ядер в современных процессорах.
Параллельные алгоритмы требуют учета использования еще одного ресурса: подсистемы связей между различными процессорами с использованием общей памяти и системы передачи сообщений. Однако рекурсивные алгоритмы требуют результата предыдущей итерации выполнения алгоритма, поэтому являются сугубо последовательными алгоритмами. Большинство современных языков высокого уровня поддерживают механизм рекурсивного вызова, когда функция, как элемент структуры языка программирования, возвращающая вычисленное значение по своему имени, может вызывать сама себя с другим аргументом.
Вспомогательный алгоритм является аналогом языковой подпрограммы. Он имеет
имя и может иметь параметры, которые называются формальными параметрами. Имя служит для того. чтобы отличить его от других алгоритмов, а формальные параметры, которые напоминают переменные математических функций, выполняют роль входных и выходных параметров.
Алгоритм называется структурным, если он представляет собой комбинацию из трех рассмотренных выше структур (они называются базовыми алгоритмическими
структурами): линейных, ветвления и циклических алгоритмов.
Можно выделить три крупных класса алгоритмов:
· Вычислительные — исходные данные простые и их немного (числа, вектора, матрицы), но процесс вычислений долгий и сложный. Применяются при решении математических и физических задач.
· Информационные — не очень сложные вычисления, объем данных большой. Требуют хорошей организации данных. Применяются при решении экономических задач.
· Управляющие — исходные данные поступают от процесса или объекта, которым управляют. Результат — воздействие на процесс. Алгоритмы должны выдавать результирующие сигналы, управляющие работой тех или иных устройств. Для этого класса алгоритмов очень существенную роль играет их быстродействие, т.к. управляющие сигналы всегда должны появляться в нужный момент времени.
Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:
Источник: studopedia.ru
Понятие алгоритма и его свойства. Блок-схема алгоритма. Основные алгоритмические конструкции
Данное учебное пособие продолжает курс по базовой информатике для бакалавров технических специальностей.
В пособии излагаются разделы современной информатики, связанные с изучением алгоритмизации и основ программирования, а также локальными и глобальными компьютерными сетями. Таким образом, вместе с двумя предыдущими пособиями серии, написанными А.П. Воробьевой и Е.Е. Ершовой, пособие охватывает все основные разделы курса информатики, изучение которых предусмотрено государственными образовательными стандартами.
Для контроля усвоения изучаемого теоретического материала предлагаются тесты, ответы к которым приводятся в конце издания. Более глубокие знания можно получить, воспользовавшись рекомендуемой по изучаемым темам литературой.
Тема 1. Алгоритмизация и программирование. Технологии программирования. Языки программирования высокого уровня
Понятие алгоритма и его свойства. Блок-схема алгоритма. Основные алгоритмические конструкции
Алгоритм – это базовое понятие информатики. На понятии алгоритма построены все основные принципы программирования – составления программ для вычислительных машин. Существуют различные определения алгоритма, приведем одно из них.
Алгоритм — это однозначно определенная последовательность действий, записанная на понятном исполнителю алгоритмическом языке и определяющая процесс перехода от исходных данных к результату.
Принято выделять следующие свойства алгоритма:
· дискретность — алгоритм состоит из отдельных инструкций (шагов), информационный процесс разделен на отдельные команды;
· определенность (детерминированность) — однозначность результатов выполнения алгоритмов в одинаковых начальных условиях, при этом каждый шаг интерпретируется исполнителем единственным образом;
· результативность — за конечное число шагов достигается некоторый результат, иногда конечность алгоритма выделяют как отдельное свойство;
· массовость — алгоритм работает при меняющихся в некоторых пределах входных данных, то есть, может быть применен для решения класса задач, различающихся исходными данными.
Иногда выделяют и другие свойства, например, правильность алгоритма означает правильность результатов, получаемых с его помощью. Алгоритм считается правильным, если он дает правильные результаты для любых допустимых начальных условий. Алгоритм содержит ошибки, если его выполнение приводит к сбоям, неправильным результатам, либо вовсе не дает результатов.
Наряду с понятием алгоритма используют термин алгоритмизация, под которой понимают совокупность приемов и способов составления алгоритмов для решения алгоритмических задач.
На практике получили распространение 2 основных формы записи алгоритмов:
· словесная или текстовая форма представления алгоритма представляет собой описание алгоритма на естественном языке или в виде структурированной записи на псевдокоде – также естественном, но частично формализованном языке;
· графическим представлением алгоритма в виде блок–схемы называют описание структуры алгоритма с помощью геометрических фигур с линиями–связями, показывающими порядок выполнения отдельных инструкций.
Первый из этих способов не имеет строгой формализации и редко используется в учебных целых, второй, напротив, является удобным средством изображения алгоритмов и получил широкое распространение в научной и учебной литературе.
Блок-схема– это последовательность блоков, предписывающих выполнение определенных операций, и связей между этими блоками. Внутри блоков указывается информация об операциях, подлежащих выполнению. Конфигурация и размеры блоков, а также порядок графического оформления блок-схем регламентированы ГОСТ 19002-80 и ГОСТ 19003-80 «Схемы алгоритмов и программ».
В табл. 1 приведены наиболее часто используемые блоки, изображены элементы связей между ними и дано краткое пояснение к ним. Блоки и элементы связей называют элементами блок-схем.
Представленных в табл. 1 элементов, как правило, достаточно для изображения всех алгоритмов, необходимых при выполнении студенческих работ.
При соединении блоков следует использовать только вертикальные и горизонтальные линии потоков.
Горизонтальные потоки, имеющие направление справа налево, и вертикальные потоки, имеющие направление снизу вверх, должны быть помечены стрелками. Прочие потоки могут быть помечены или оставлены непомеченными. Линии потоков должны быть параллельны линиям внешней рамки или границам листа.
Таблица 1. Основные элементы блок-схем
Принято различать всего три базовых алгоритмических структуры:
· следование или линейный алгоритм;
· ветвление или разветвляющийся алгоритм;
Они будут подробно рассмотрены в следующем разделе.
Источник: megaobuchalka.ru