Понятие алгоритма является одним из основных в современной науке и практике. Еще на самых ранних ступенях развития математики (Древний Египет, Вавилон, Греция) в ней стали рассматриваться различные вычислительные процессы чисто механического характера. С их помощью искомые величины ряда задач вычислялись последовательно из исходных величин по определенным правилам и инструкциям. Со временем все такие процессы в математике получили название алгоритмов (алгорифмов).
Алгоритм есть совокупность четко определенных правил, процедур или команд, обеспечивающих решение поставленной задачи за конечное число шагов.
Термин алгоритм происходит от имени средневекового узбекского математика Аль-Хорезми, который еще в IX в. (825 г.) дал правила выполнения четырех арифметических действий в десятичной системе счисления. Процесс выполнения арифметических действий был назван алгоризмом.
С 1747 г. вместо слова алгоризм стали употреблять алгорисмус, смысл которого состоял в комбинировании четырех операций арифметического исчисления — сложения, вычитания, умножения, деления.
ВСЯ СЛОЖНОСТЬ АЛГОРИТМОВ ЗА 11 МИНУТ | ОСНОВЫ ПРОГРАММИРОВАНИЯ
К 1950 г. алгорисмус стал алгорифмом. Смысл алгорифма чаще всего связывался с алгорифмами Евклида — процессами нахождения наибольшего общего делителя двух многочленов, наибольшей общей меры двух отрезков и т. п.
Способы записи алгоритмов
Алгоритм должен быть понятен (доступен) пользователю и/или машине. Доступность пользователю означает, что он обязан отображаться посредством конкретных формализованных изобразительных средств, понятных пользователю. В качестве таких изобразительных средств используются следующие способы их записи:
- • словесный;
- • формульный;
- • табличный;
- • операторный;
- • графический;
- • язык программирования.
Формульный способ основан на строго формализованном аналитическом задании необходимых для исполнения действий.
Табличный способ подразумевает отображение алгоритма в виде таблиц, использующих аппарат реляционного исчисления и алгебру логики для задания подлежащих исполнению взаимных связей между данными, содержащимися в таблице.
Операторный способ базируется на использовании для отображения алгоритма условного набора специальных операторов: арифметических, логических, печати, ввода данных и т. д.; операторы снабжаются индексами и между ними указываются необходимые переходы, а сами индексированные операторы описываются чаще всего в табличной форме.
Графическое отображение алгоритмов в виде блок-схем — весьма наглядный и распространенный способ. Графические символы, отображающие выполняемые процедуры, стандартизованы. Наряду с основными символами используются и вспомогательные, поясняющие процедуры и связи между ними.
Алгоритмы могут быть записаны и в виде команд какого-либо языка программирования. Если это макрокоманды, то алгоритм читаем и пользователем-программистом, и вычислительной машиной, имеющей транслятор с соответствующего языка.
Приведем пример словесного представления алгоритма на примере нахождения произведения п натуральных чисел (с= п = = 1 х 2 х 3 х 4 х . х п).
Этот процесс может быть записан в виде следующей системы последовательных указаний (пунктов):
- 1. Полагаем с равным единице и переходим к следующему пункту.
- 2. Полагаем / равным единице и переходим к следующему пункту.
- 3. Полагаем с равным с=сх/ и переходим к следующему указанию.
- 4. Проверяем, равно ли /’ числу п. Если / = п, то вычисления прекращаем. Если / 3 + Ьх 2 + сх + с1 = 0, то он должен быть вариативен, т. е. обеспечивать возможность решения для любых допустимых исходных значений коэффициентов а, Ь, с, с1. Про такой алгоритм говорят, что он удовлетворяет требованию массовости. Свойство массовости не является необходимым свойством алгоритма. Оно, скорее, определяет качество алгоритма; в то же время свойства точности, понятности и конечности являются необходимыми (иначе это не алгоритм).
Запись алгоритмов в виде блок-схем
Алгоритмы можно записывать по-разному. Форма записи, состав и количество операций алгоритма зависят от того, кто будет исполнителем этого алгоритма. Если задача решается с помощью ЭВМ, алгоритм решения задачи должен быть записан в понятной для машины форме, т. е. в виде программы.
Схема алгоритма — графическое представление алгоритма, дополняемое элементами словесной записи. Каждый пункт алгоритма отображается на схеме некоторой геометрической фигурой или блоком. При этом правило выполнения схем алгоритмов регламентирует ГОСТ 19.002—80 «Единая система программной документации» (табл. 1.28).
Блоки на схемах соединяются линиями потоков информации. Основное направление потока информации идет сверху вниз и слева направо (стрелки могут не указываться), снизу вверх и справа налево — стрелка обязательна. Количество входящих линий для блока не ограничено. Выходящая линия — одна, за исключением логического блока.
Таблица 1.28. Основные элементы блок-схем
по ГОСТ 19.003—80 (ЕСПД):а = 10,15,20 мм; b = ^, 5а
Вычислительные действия или последовательность действий
Выбор направления выполнения алгоритма в зависимости от некоторого условия
- 1. Общие обозначения ввода (вывода) данных (вне зависимости от физического носителя).
- 2. Вывод данных, носителем которых является документ
Начало или конец алгоритма, вход в программу или выход из нее
г = а/4
Процесс пользователя (подпрограмма)
Вычисление по стандартной программе или подпрограмме
Функция выполняет действия, изменяющие пункты (например, заголовок цикла) алгоритма
Указание связи прерванными линиями между потоками информации в пределах одного листа
Указание связи между информацией на разных листах
Базовые структуры алгоритмов
Это определенный набор блоков и стандартных способов их соединения для выполнения типичных последовательных действий. К основным структурам относятся следующие — линейные, разветвляющиеся, циклические (рис. 1.26).
Рис. 1.26. Примеры структур алгоритмов: а — линейный алгоритм; б — алгоритм с ветвлением; в — алгоритм с циклом
Линейными называются алгоритмы, в которых действия осуществляются последовательно друг за другом. Стандартная блок-схема линейного алгоритма приводится на рис. 1.26, а (вычисление суммы двух чисел — А и В).
Разветвляющимся называется алгоритм, который, в отличие от линейных алгоритмов, содержит условие, в зависимости от истинности или ложности которого выполняется та или иная последовательность команд. Таким образом, команда ветвления состоит из условия и двух последовательностей команд.
Примером может являться разветвляющийся алгоритм, изображенный в виде блок-схемы (рис. 1.26, б). Аргументами этого алгоритма являются две переменные А, В, а результатом — переменная X. Если условие А > В истинно, то выполняется операция X := А х В, в противном случае выполняется X := А + В. В результате печатается то значение переменной X, которое она получает при выполнении одной из серий команд.
Циклическим называется алгоритм, в котором некоторая последовательность операций (тело цикла) выполняется многократно. Однако «многократно» не означает «до бесконечности». Организация циклов, никогда не приводящая к остановке в выполнении алгоритма, является нарушением требования его результативности — получения результата за конечное число шагов.
В цикл в качестве базовых входят — блок проверки условия и тело цикла. Перед операцией цикла осуществляется начальное присвоение значений тем переменным, которые используются в теле цикла. Если тело цикла расположено после проверки условий Р (цикл с предусловием), то может случиться так, что при определенных условиях тело цикла не выполнится ни разу. Такой вариант организации цикла, управляемый предусловием, называется цикл «ПОКА»/«WHILE» (здесь условие — это условие на продолжение цикла).
Возможен другой случай, когда тело цикла выполняется, по крайней мере, один раз и будет повторяться до тех пор, пока не станет истинным условие. Такая организация цикла, когда его тело расположено перед проверкой условия, носит название цикла с постусловием, или цикла «ДО»/«FOR». Истинность условия в этом случае — условие окончания цикла.
Отметим, что возможна ситуация с постусловием и при организации цикла «ПОКА». Итак, цикл «ДО» завершается, когда условие становится истинным, а цикл «ПОКА» — когда становился ложным. Современные языки программирования имеют достаточный набор операторов, реализующих как цикл «ПОКА», так и цикл «ДО».
Рассмотрим пример алгоритма вычисления факториала, изображенный на рис. 1.26 (с циклом «ПОКА»). Переменная N получает значение числа, факториал которого вычисляется. Переменной N, которая в результате выполнения алгоритма должна получить значение факториала, присваивается первоначальное значение 1. Переменной К также присваивается значение 1. Цикл будет выполняться, пока справедливо условие N> К. Тело цикла состоит из двух операций N = N1 х К и К= К + 1.
Циклические алгоритмы, в которых тело цикла выполняется заданное число раз, реализуются с помощью цикла со счетчиком. Цикл со счетчиком реализуется с помощью команды повторения.
Процесс решения сложной задачи довольно часто сводится к решению нескольких более простых подзадач. Соответственно при разработке сложного алгоритма он может разбиваться на отдельные алгоритмы, которые называются вспомогательными. Каждый такой вспомогательный алгоритм описывает решение какой-либо подзадачи.
Процесс построения алгоритма методом последовательной детализации состоит в следующем. Сначала алгоритм формулируется в «крупных» блоках (командах), которые могут быть непонятны исполнителю (не входят в его систему команд) и записываются как вызовы вспомогательных алгоритмов. Затем происходит детализация, и все вспомогательные алгоритмы подробно расписываются с использованием команд, понятных исполнителю.
- 1. Дайте классификацию информации.
- 2. Каковы преимущества цифровой информации по отношению к аналоговой?
- 3. Перечислите методы кодирования символов.
- 4. Перечислите методы кодирования численной информации.
- 5. Переведите число 32 45110 в шестнадцатеричную и восьмеричную системы счисления.
- 6. Переведите число 32 45116 в десятичную и восьмеричную системы счисления.
- 7. В чем заключаются особенности двоичной арифметики?
- 8. Подсчитайте произведение 1ГА16 и 2ВС16 по модулю 8.
- 9. Подсчитайте сумму 4578 и 3758 по модулю 3.
- 10. Перечислите логические элементы ЭВМ.
- 11. Что такое логические узлы ЭВМ?
- 12. Составьте таблицы истинности для левого (-1(А д В)) и правого (-И V -,б) выражений 1-го закона де Моргана. Проверьте их на соответствие.
- 13. Составьте таблицы истинности для левого (-1(А V В)) и правого (-.А V -,б) выражений 2-го закона де Моргана. Проверьте их на соответствие.
- 14. Последний столбец таблицы истинности для двухместных операций, очевидно, может содержать 16 = 2 4 различных сочетаний «1» и «О». Следовательно, всего может быть определено 16 логических операций над двумя переменными, из которых нами рассмотрены только пять. Составьте таблицу истинности для одной из 9 оставшихся вне рассмотрения функций и попытайтесь построить логическое выражение для этой функции.
- 15. Перечислите базовые структуры алгоритмов и программ.
Источник: studref.com
Как стать программистом
Это моя личная ссылка-приглашение на Stepik для вас. Регистрируясь по этой ссылке, записываясь на курсы и решая задачи, Вы помогаете автору данного сайта принять участие в конкурсе платформы Stepik! Подробности конкурса здесь: https://vk.cc/75rKuS
суббота, 17 августа 2013 г.
Алгоритм. Формы записи. Отличие алгоритма от программы.
Добрый день!
Сегодня мы поговорим об алгоритмах и способах их записи.
Что такое алгоритм?
Алгоритм – порядок действий, выполнив который, исполнитель (некоторое устройство или даже человек), получит решение некоторой конкретной задачи.
К алгоритмам предъявляются ряд некоторых требований.
1. Понятность. Алгоритм должен быть понятным, человеку или устройству, которое его будет выполнять. Вспомните инструкции к технике на китайском или корейском языке.
2. Конечность. Алгоритм должен иметь конечное число шагов. Пусть их будет два миллиона, но мы точно знаем, что выполнив все два миллиона шагов по порядку, то обязательно получим результат.
3. Определенность. Алгоритм должен быть точным и не допускать неоднозначности в его понимании. На каждом шаге, исполнитель должен точно знать, какой шаг ему делать следующим, а не додумывать или предполагать.
Естественно есть и другие. Кому интересно, можете поискать информацию в интернете.
Способы записи алгоритмов.
Есть несколько способов записи алгоритмов. Одним из наиболее распространенных, является словесное описание алгоритма. Студентов, иногда просят записывать свой алгоритм в виде блок-схем. Это тоже один наглядных способов записи алгоритмов. Кроме того, для записи алгоритмов, часто используют «формальные языки».
Дело в том, что большинство алгоритмических языков во много схожи между собой. Так, например, в большинстве из них, есть операция присвоения значения переменной, есть сами переменные, циклы, управляющие конструкции и т.д. А раз так, то можно придумать некоторый формальный язык, которым будут описываться эти стандартные действия. Таким образом, они будут понятны всем программистам, пишущим на других языках. Такой формальный язык называют псевдокод.
Программа это, кстати, тоже не алгоритм. Программа, это уже конкретная реализация некоторого алгоритма.
Давайте рассмотрим уже знакомый нам пример, с поиском минимума в одномерном массиве.
Задача: Дан массив целых чисел. Найти минимальный элемент в массиве.
Идея решения: Сравнить между собой все элементы и найти минимальный.
Алгоритм: (словесное описание)
1. Принимаем в качестве минимального первый элемент предложенного массива.
2. Начиная со второго, последовательно сравниваем каждый элемент с минимальным значением, пока не достигнем конца массива.
2.1. Если текущий элемент меньше минимального, принимаем его значение в качестве минимума.
2.2. В противном случае, переходим к следующей итерации.
Теперь представим блок-схему данного алгоритма.
Имеем массив чисел arr [ N ], N – длина массива.
 |
|||
| Рис 1. Блок-схема алгоритма поиска |
Все эти квадратики, кружочки и ромбики это не моя прихоть, а специальные обозначения. Существует даже специальный государственный документ, который определяет наклон линий, размеры этих фигур, подписи и т.д. (кому интересно поищите стандарт ЕСПД). Я уже давно не занимался этим, и стандарты давно не читал, поэтому в тонкостях могу и ошибаться, но общий вид блок схемы правильный. К тому же соблюдать эти стандарты требуется только в официальной документации, студентов обычно не просят делать этого. Быть может, я еще подробнее остановлюсь на составлении блок-схем к алгоритмам, но пока рассмотрим основные элементы.
Скругленные квадраты в начале и в конце обозначают начало и конец программы.
Овал – ввод или вывод данных.
В прямоугольнике записывают вычисления и присвоения.
Ромб – это условие, буквально оператор if — else . Из него две ветви одна выполняется, когда условие истинно, другая — когда ложно.
Шестигранник используется для обозначения цикл со счетчиком, хотя это и так понятно. После окончания цикла выполняется правая веточка этого значка (хотя я встречал и другие способы записи циклов).
Запись алгоритма на псевдокоде.
Вы можете встретить различные виды псевдокода, синтаксис некоторых может быть похож на синтаксис языка программирования Pascal . Я привожу здесь тот, что используется в задания типа ЕГЭ.
Источник: www.youngcoder.net
Для чайников, юзеров, ламеров и не только: чем отличается программа от алгоритма?
Среднестатистический пользователь имеет довольно ограниченное представление о программах. Многие люди совершенно ничего не знают о том, как они создаются. Поэтому некоторым трудно понять, в чем отличие алгоритма от программы.
На самом деле это совершенно разные понятия, имеющие немало различий. Чтобы разобраться, чем именно они отличаются, придется заранее ознакомиться с их характерными особенностями.
Что такое алгоритм?
Данное понятие часто используется в современной науке. При этом впервые им начали пользоваться еще в начале развития математики, во времена Древнего Египта. Сейчас его широко используют не только в математике, но и в программировании.
Алгоритм представляет собой совокупность четких правил и команд, позволяющих быстро решить поставленные задачи за определенное количество шагов. Существует несколько способов записи алгоритмических действий:
- Словесный. Все последовательные этапы выполняемых действий описываются словесно.
- Формульный. В этом случае придется самостоятельно разрабатывать аналитические задачи для достижения поставленных целей.
- Операторный. При использовании этого способа применяются специальные арифметические или логические операторы.
- Графический. Это наиболее распространенный метод, пользующийся популярностью среди опытных программистов. Он позволяет наглядно представить все выполняемые действия. При их описании используются графические символы.
- В виде команд. В некоторых случаях для представления алгоритмов используются команды языков программирования. Подобные алгоритмические инструкции разрабатываются программистами.
Все алгоритмы можно разделить на три основные категории:
- Линейные. Главная их особенность заключается в том, что описанные в них действия выполняются строго последовательно.
- Разветвляющиеся. В них содержатся не только последовательные действия, но и условиях. В зависимости от их ложности или истинности будет определено, какие именно команды следует выполнять.
- Циклические. Описанные в них действия выполняются определенное количество раз.
При разработке программ активно используются все виды алгоритмов.
Что такое программа?
Перед тем как разобраться, чем отличается алгоритм от программы в информатике, рекомендуется детальнее ознакомиться с особенностями программных средств.
Программа – программное обеспечение на персональном компьютере, выполняющее поставленные перед ним задачи и функции. Многих пользователей интересует, для чего их создают и какая их цель.
Разработанное ПО дает юзеру возможность выполнять те или иные задачи. Например, чтобы просматривать веб-страницы в интернете придется установить на ПК специальную программу – браузер. Без него нормально пользоваться интернетом не получится.
Поэтому можно сказать, что без программного обеспечения функционал компьютеров был бы очень ограниченным.
Программа и алгоритм: различия
Несмотря на то, что эти понятия имеют немало общего, есть у них и отличия. Главной отличительной особенностью является то, что любое программное обеспечение состоит из нескольких алгоритмов. Ведь именно разработанные на этапе написания ПО алгоритмические инструкции и являются основой любого софта.
Из этого можно сделать вывод, что алгоритм – схематическое представление воплощения определенной идеи, а созданная программа – ее реализация.
Еще одно отличие – вид представления. Как говорилось выше, алгоритмы могут быть представлены в разном виде – от устного до письменного. При этом ПО может быть представлено только в одном виде – на языке программирования.
Источник: kakayaraznica.ru