9 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Алгори́тм, от имени учёного аль-Хорезми — точный набор инструкций, описывающих порядок действий исполнителя для достижения результата решения задачи за. Алгоритм, виды алгоритмов

Содержание

Алгоритм, виды алгоритмов. Алгоритмизация поиска правовой информации. Алгори́тм, от имени учёного аль-Хорезми — точный набор инструкций, описывающих порядок действий исполнителя для достижения результата решения задачи за

ВНИМАНИЕ! САЙТ ЛЕКЦИИ.ОРГ проводит недельный опрос. ПРИМИТЕ УЧАСТИЕ. ВСЕГО 1 МИНУТА.

Алгори́тм, от имени учёного аль-Хорезми — точный набор инструкций, описывающих порядок действий исполнителя для достижения результата решения задачи за конечное время.

Алгоритмизация — процесс разработки алгоритма (плана действий) для решения задачи.

1. Линейные — не содержат логических условий, имеют одну ветвью обработки и изображаются линейной последовательностью связанных друг с другом блоков.

2. Разветвленный — содержит одно или несколько условий и имеет несколько ветвей обработки.

3. Циклический — содержит один или несколько циклов.

Алгоритмизация поиска правовой информации.

Поддержание информационных банков справочно-правовых систем в актуальном состоянии складывается из трех замкнутых технологических процессов, а именно:

-введение в информационный банк новых документов;

-создание и введение в информационный банк новых редакций документов;

-внесение в информационный банк изменений и дополнений к документам.

Каждый из этих процессов состоит из последовательно выполняемых этапов:

1.1.Регистрация поступившего документа

1.2. Просмотр периодических изданий

2. Обработка документа юристами

3. Подготовка текста документа

3.1 Создание электронного образа документа

3.2 Оформление, проверка на орфографию

3.3.Вычитка текста корректором

4. Проставление гипертекстовых ссылок

5. Заполнение поисковой карточки документа

6. Подготовка документа к загрузке в исходном формате

7. Завершающая проверка автоматизированными средствами поиска ошибок

8. Ввод в информационный банк

9. Что такое архитектура и структура компьютера. Опишите принцип «открытой архитектуры».

Архитектурой компьютера это его описание на некотором общем уровне, включающее описание пользовательских возможностей программирования, системы команд,

Структура компьютера — это совокупность его функциональных элементов и связей между ними.

Принцип открытой архитектуры заключается в следующем:

Регламентируются и стандартизируются только описание принципа действия компьютера и его конфигурация.

Компьютер легко расширяется и модернизируется за счёт наличия внутренних расширительных гнёзд.

Для того чтобы соединить друг с другом различные устройства компьютера они должны иметь одинаковый интерфейс.

Для согласования интерфейсов периферийные устройства подключаются к шине не напрямую, а через свои контроллеры (адаптеры) и порты примерно по такой схеме:

Котроллеры и адаптеры представляют собой наборы электронных цепей, которыми снабжаются устройства компьютера с целью совместимости их интерфейсов.

10. Единицы измерения информации в компьютерных системах: двоичная система исчисления, биты и байты. Методы представления информации.

Система счисления — это способ записи чисел с помощью заданного набора знаков (цифр).

двоичная система исчисления — позиционная система счисления с основанием 2. Для представления чисел используются символы 0 и 1.

Бит — min единица информации.

Байт- единица измерения количества информации равняющаяся 8 битам.

Способы представления информации

1.непрерывный способ все координаты вектора могут принимать любые значения числовой оси.

2.дискретный способ каждая координата вектора может принимать лишь фиксированное число значений.

Слово «Алгоритм» происходит от algorithmi — латинского написания имени аль-Хорезми, под которым в средневековой Европе знали величайшего математика из Хорезма Мухаммеда бен Мусу, жившего в 783-850 гг. В своей книге «Об индийском счете» он сформулировал правила записи натуральных чисел с помощью арабских цифр, правила действий над ними столбиком.

Приведем несколько определений понятия алгоритма:

· Алгоритм — это конечный набор правил, который определяет последовательность операций для решения конкретного множества задач и обладает пятью важными чертами: конечность, определённость, ввод, вывод, эффективность». (Д. Э. Кнут)

· Алгоритм — это всякая система вычислений, выполняемых по строго определённым правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи». (А. Колмогоров)

· Алгоритм — точное предписание о выполнении в определённом порядке некоторой системы операций, ведущих к решению всех задач данного типа». (Философский словарь / Под ред. М. М. Розенталя)

· Алгоритм — строго детерминированная последовательность действий, описывающая процесс преобразования объекта из начального состояния в конечное, записанная с помощью понятных исполнителю команд». (Николай Дмитриевич Угринович, учебник «Информатика и информ. технологии»)

Алгоритм может быть предназначен для выполнения его человеком или автоматическим устройством. Создание алгоритма процесс творческий, доступен лишь живым существам, долгое время считалось, что только человеку. Другое дело — реализация уже имеющегося алгоритма, которую можно поручить субъекту или объекту, который не обязан вникать в суть дела, может и не способен его понять — этот субъект (объект) принято называть формальным исполнителем.

Исполнителем алгоритма может быть и человек. Часто приводят примеры “бытовых алгоритмов”: вскипятить воду, открыть дверь ключом, перейти улицу и т. д.: рецепты приготовления какого-либо лекарства или кулинарные рецепты являются алгоритмами. На самом деле алгоритмы для людей никто не составляет. Человек в принципе не может действовать по алгоритму. Выполнение алгоритма — это автоматическое, бездумное выполнение операций. Между тем исполнение алгоритма — это бездумное, автоматическое выполнение предписаний, которое в принципе не требует никаких знаний. Если бы кулинарные рецепты представляли собой алгоритмы, просто не было бы специальности — повар.

В информатике универсальным исполнителем алгоритмов является компьютер.

Исполнитель алгоритма — некоторая абстрактная или реальная (техническая, биологическая или биотехническая) система, способная выполнить действия, предписываемые алгоритмом.

Исполнителя характеризуют: среда; система команд; элементарные действия; отказы.

Среда (или обстановка) — «место обитания» исполнителя. Объекты, над которыми исполнитель может совершать действия. Для алгоритмов, встречающихся в математике, средой того или иного исполнителя могут быть числа разной природы — натуральные, действительные и т.п., буквы, буквенные выражения, уравнения, тождества и т. п.

Система команд — совокупность допустимых действий. Каждый исполнитель может выполнять команды только из некоторого строго заданного списка — системы команд исполнителя. Для каждой команды должны быть заданы условия применимости, описаны результаты выполнения команды.

Элементарное действие — те действия, которые может совершать исполнитель

Отказы исполнителя возникают, если команда вызывается при недопустимом для нее состоянии среды.

Свойства алгоритма:

Обычно формулируют несколько общих свойств алгоритмов, позволяющих отличать алгоритмы от других инструкций :

— дискретность (прерывность, раздельность) — алгоритм должен представлять процесс решения задачи как последовательное выполнение простых (или ранее определенных) шагов. Каждое действие, предусмотренное алгоритмом, исполняется только после того, как закончилось исполнение предыдущего;

— определенность — каждое правило алгоритма должно быть четким, однозначным и не оставлять места для произвола. Благодаря этому свойству выполнение алгоритма носит механический характер и не требует никаких дополнительных указаний или сведений о решаемой задаче;

— результативность (конечность) — алгоритм должен приводить к решению задачи за конечное число шагов;

— массовость — алгоритм решения задачи разрабатывается в общем виде, то есть, он должен быть применим для некоторого класса задач, различающихся только исходными данными. При этом исходные данные могут выбираться из некоторой области, которая называется областью применимости алгоритма.

Чтобы алгоритм выполнил свое предназначение, его необходимо строить по определенным правилам. Поэтому нужно говорить не о свойствах алгоритма, а о правилах построения алгоритма, или о требованиях, предъявляемых к алгоритму.

Читать еще:  Как набирать междугородный номер с городского. Экономсовет

Первое правило — при построении алгоритма, прежде всего, необходимо задать множество объектов, с которыми будет работать алгоритм. Формализованное (закодированное) представление этих объектов носит название данных. Алгоритм приступает к работе с некоторым набором данных, которые называются входными, и в результате своей работы выдает данные, которые называются выходными. Таким образом, алгоритм преобразует входные данные в выходные. Это правило позволяет сразу отделить алгоритмы от «методов» и «способов». Пока мы не имеем формализованных входных данных, мы не можем построить алгоритм.

Второе правило — для работы алгоритма требуется память. В памяти размешаются входные данные, с которыми алгоритм начинает работать, промежуточные данные и выходные данные, которые являются результатом работы алгоритма. Память является дискретной, т.е. состоящей из отдельных ячеек. Поименованная ячейка памяти носит название переменной. В теории алгоритмов размеры памяти не ограничиваются, т.е. считается, что мы можем предоставить алгоритму любой необходимый для работы объем памяти. В школьной «теории алгоритмов» эти два правила не рассматриваются.

Третье правило — дискретность. Алгоритм строится из отдельных шагов (действий, операций, команд). Множество шагов, из которых составлен алгоритм, конечно.

Четвертое правило — детерменированность. После каждого шага необходимо указывать, какой шаг выполняется следующим, либо давать команду остановки.

Пятое правило — сходимость (результативность). Алгоритм должен завершать работу после конечного числа шагов. При этом необходимо указать, что считать результатом работы алгоритма.

2. Графическое представление алгоритмов.

Алгоритм задается в содержательном (вербальном), графическом или операторном (символьном) виде.

Содержательный способ записи алгоритмов представляет собой описание последовательных этапов обработки данных. Алгоритм задается в произвольном изложении на естественном языке.

содержательный способ не имеет широкого распространения, так как такие описания:

  • строго не формализуемы;
  • страдают многословностью записей;
  • допускают неоднозначность толкования отдельных предписаний.

Графический способ представления алгоритмов является более компактным и наглядным по сравнению с содержательным.

При графическом представлении алгоритм изображается в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий. Внутри блока дается описание соответствующего действия.

Такое графическое представление называется схемой алгоритма или блок-схемой.

Графическое изображение алгоритма широко используется перед программированием задачи вследствие его наглядности, т.к. зрительное восприятие обычно облегчает процесс написания программы, ее корректировки при возможных ошибках, осмысливание процесса обработки информации.

Можно встретить даже такое утверждение: “Внешне алгоритм представляет собой схему — набор прямоугольников и других символов, внутри которых записывается, что вычисляется, что вводится в машину и что выдается на печать и другие средства отображения информации“. Здесь форма представления алгоритма смешивается с самим алгоритмом.

Схема — это графическое представление алгоритма, дополненное элементами словесной записи. Каждый пункт алгоритма отображается на схеме некоторой геометрической фигурой-блоком (блочным символом), причем различным по типу выполняемых действий блокам соответствуют различные геометрические фигуры, изображаемые по ГОСТу.

ГОСТ 19.701-90 (обозначение символов соответствует международному стандарту ИСО 5807-85) распространяется на условные обозначения (символы) в схемах алгоритмов, программ, данных и систем и устанавливает правила выполнения схем, используемых для отображения различных видов задач обработки данных и средств их решения.

Графические символы на схеме соединяются линиями потока информации. Основное направление потока информации идет сверху вниз и слева на право (стрелки на линиях могут не указываться). В других случаях применение стрелок обязательно. По отношению к блоку линии потока могут быть входящими или выходящими. Количество входящих линий для блока принципиально не ограничено. Выходящая линия может быть только одна. Исключение оставляют логические блоки, имеющие не менее двух выходящих линий потока, каждая из которых соответствует одному из возможных исходов проверки логического условия, а также блоки модификации.

При записи алгоритма в словесной форме, в виде блок-схемы допускается определенный произвол при изображении команд. Вместе с тем такая запись точна настолько, что позволяет человеку понять суть дела и исполнить алгоритм.

Однако на практике в качестве исполнителей алгоритмов используются специальные автоматы — компьютеры. Поэтому алгоритм, предназначенный для исполнения на компьютере, должен быть записан на понятном ему языке. И здесь на первый план выдвигается необходимость точной записи команд, не оставляющей места для произвольного толкования их исполнителем.

Следовательно, язык для записи алгоритмов должен быть формализован. Такой язык принято называть языком программирования, а запись алгоритма на этом языке — программой для компьютера.

3. Виды вычислительный процессов.

1. Линейные вычислительные процессы

2. Циклические вычислительные процессы

3. Разветвляющиеся вычислительные процессы

4. Многоступенчатые вычислительные процессы

5. Комбинированные вычислительные процессы

Для организации циклических вычислительных процессов выделяется специальная переменная, называемая параметром цикла. По этой переменной ведется управление счетом, то есть, количеством выполнения тела цикла. В каждом цикле происходит изменение параметра цикла по определенной рекурсивной зависимости.

Различают циклические вычислительные процессы (ЦВП) с известным количеством повторения тела цикла и неизвестным количеством повторений тела цикла.

Цикл, в котором известно количество раз, которое выполнится тело цикла, называется детерминированным циклическим вычислительным процессом (ДЦВП).

Цикл, в котором нельзя заранее сказать, сколько раз выполнится тело цикла, называется итерационным циклическим вычислительным процессом (ИЦВП) (итерация – последовательное приближение.). Пример – задачи на вычисление с заданной точностью

Алгоритмы Что такое алгоритм? В старой трактовке алгори́тм это точный набор инструкций, описывающих последовательность действий некоторого исполнителя. — презентация

Презентация была опубликована 6 лет назад пользователемПетр Широбоков

Похожие презентации

Презентация на тему: » Алгоритмы Что такое алгоритм? В старой трактовке алгори́тм это точный набор инструкций, описывающих последовательность действий некоторого исполнителя.» — Транскрипт:

2 Что такое алгоритм? В старой трактовке алгори́тм это точный набор инструкций, описывающих последовательность действий некоторого исполнителя для достижения результата, решения некоторой задачи за конечное время. По мере развития параллельности в работе компьютеров слово «последовательность» стали заменять более общим словом «порядок». Это связано с тем, что какие-то действия алгоритма должны быть выполнены только друг за другом, но какие-то могут быть и независимыми.

3 Понятие алгоритма необязательно относится к компьютерным программам, так, например, чётко описанный рецепт приготовления блюда также является алгоритмом, в таком случае исполнителем является человек. Однако чаще всего в качестве исполнителя выступает компьютер.

4 Определения алгоритма Единого «истинного» определения понятия «алгоритм» нет. «Алгоритм это конечный набор правил, который определяет последовательность операций для решения конкретного множества задач и обладает пятью важными чертами: конечность, определённость, ввод, вывод, эффективность». (Д. Э. Кнут) «Алгоритм это всякая система вычислений, выполняемых по строго определённым правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи». (А. Колмогоров) «Алгоритм это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату». (А. Марков) «Алгоритм строго детерминированная последовательность действий, описывающая процесс преобразования объекта из начального состояния в конечное, записанная с помощью понятных исполнителю команд». (Николай Дмитриевич Угринович) «Алгоритм это последовательность действий, направленных на получение определённого результата за конечное число шагов». (ROXANstudio) «Алгоритм это строго определённая последовательность действий, направленная на достижение определённых целей за конечное число шагов». (Привалов Егор Николаевич) «Алгоритм есть формализованная последовательность действий (событий). Алгоритм может быть записан словами и изображён схематически. Практически любое неслучайное повторяемое действие поддаётся описанию через алгоритм». ([grey_olli]) «Алгоритм однозначно, доступно и кратко (условные понятия названия этапа) описанная последовательность процедур для воспроизводства процесса с обусловленным задачей алгоритма результатом при заданных начальных условиях. Универсальность (или специализация) алгоритма определяется применимостью и надёжностью данного алгоритма для решения нестандартных задач».

5 Признаки алгоритмов ДетерминированностьПонятностьКонечностьМассовость

6 Детерминированность Детерминированность определённость. В каждый момент времени следующий шаг работы однозначно определяется состоянием системы. Таким образом, алгоритм выдаёт один и тот же результат (ответ) для одних и тех же исходных данных. В современной трактовке у разных реализаций одного и того же алгоритма должен быть изоморфный граф. С другой стороны, существуют вероятностные алгоритмы, в которых следующий шаг работы зависит от текущего состояния системы и генерируемого случайного числа.

Читать еще:  Что такое документ в формате rtf. Что такое расширение файла RTF? Чем открыть RTF файл

7 Понятность Понятность алгоритм для исполнителя должен включать только те команды, которые ему (исполнителю) доступны, которые входят в его систему команд.

8 Завершаемость (конечность) Завершаемость (конечность) при корректно заданных исходных данных алгоритм должен завершать работу и выдавать результат за конечное число шагов. С другой стороны, вероятностный алгоритм может и никогда не выдать результат, но вероятность этого равна 0.

9 Массовость Массовость алгоритм должен быть применим к разным наборам исходных данных.

10 История термина «Алгоритм» Само слово «алгоритм» происходит от имени учёного Абу Абдуллах Мухаммеда ибн Муса аль-Хорезми. Около 825 года он написал сочинение, в котором впервые дал описание придуманной в Индии позиционной десятичной системы счисления. Абу Абдулла (или Абу Джафар) Мухаммед ибн Муса аль-Хорезми

11 Алгоритмы ЛинейныеРазветвляющиесяЦиклические Основные виды алгоритмов

12 Основные способы записи алгоритма На формальном языке (языке программирования) В виде блок-схемы

13 Запись алгоритма на формальном языке называется программой. Иногда само понятие алгоритма отождествляется с его записью, так что слова «алгоритм» и «программа» почти синонимы. Небольшое различие заключается в том, что под алгоритмом, как правило, понимают основную идею его построения. Программа же всегда связана с записью алгоритма на конкретном формальном языке.

14 Алгоритм действия пешехода, который позволит ему безопасно перейти улицу 1. Подойти к дороге. 2. Дождаться зелёного сигнала светофора. 3. Перейти дорогу. 4. Если впереди есть ещё одна дорога, то перейти к шагу 1.

15 Запись алгоритма в виде блок- схемы Запись алгоритма в виде блок схемы позволяет увидеть структуру алгоритма наглядно, без использования специфического языка. Часто такая запись позволяет выявить ошибки в алгоритме

16 Основные блоки алгоритмов Блок операции Начало и конец алгоритма Блок ввода/вывода Алтернативный блок (блок условия)

17 Разбить яйцо на сковороду Линейный алгоритм приготовления яичницы Начало Разогреть сковороду Налить масло на сковороду Взять яйцо Посолить яйцо Подождать 5 минут Конец

18 Подойти к дороге. Дождаться зелёного сигнала светофора. Перейти дорогу. Начало Впереди есть ещё одна дорога? Конец нет да Циклический алгоритм действия пешехода, который позволит ему безопасно перейти улицу

19 Условный алгоритм похода в магазин Начало Есть продукты? Взять деньги, одеться, выйти из дома, дойти до магазина Конец да Магазин работает? нет Идти к другому магазину Купить продукты Конец да нет

20 С развитием вычислительной техники и теории программирования возрастает необходимость построения новых экономичных алгоритмов, изменяются способы их построения, способы записи алгоритмов на языке, понятном исполнителю. Особый тип исполнителя алгоритмов – компьютер, поэтому необходимо создавать специальные средства, позволяющие, с одной стороны, разработчику в удобном виде записывать алгоритмы, а с другой – дающие компьютеру возможность понимать написанное. Такими средствами являются языки программирования или алгоритмические языки.

Алгоритм

Алгори́тм — набор инструкций, описывающих порядок действий исполнителя для достижения результата решения задачи за конечное число действий.
В старой трактовке вместо слова «порядок» использовалось слово «последовательность», но по мере развития параллельности в работе компьютеров слово «последовательность» стали заменять более общим словом «порядок». Это связано с тем, что работа каких-то инструкций алгоритма может быть зависима от других инструкций или результатов их работы. Таким образом, некоторые инструкции должны выполняться строго после завершения работы инструкций, от которых они зависят. Независимые инструкции или инструкции, ставшие независимыми из-за завершения работы инструкций, от которых они зависят, могут выполняться в произвольном порядке, параллельно или одновременно, если это позволяют используемые процессор и операционная система.

Часто в качестве исполнителя выступает некоторый механизм (компьютер, токарный станок, швейная машина), но понятие алгоритма необязательно относится к компьютерным программам, так, например, чётко описанный рецепт приготовления блюда также является алгоритмом, в таком случае исполнителем является человек.

Понятие алгоритма относится к первоначальным, основным, базисным понятиям математики. Вычислительные процессы алгоритмического характера (арифметические действия над целыми числами, нахождение наибольшего общего делителя двух чисел и т. д.) известны человечеству с глубокой древности. Однако, в явном виде понятие алгоритма сформировалось лишь в начале XX века.

Современное формальное определение алгоритма было дано в 30—50-е годы XX века в работах Тьюринга, Поста, Чёрча (тезис Чёрча — Тьюринга), Н. Винера, А. А. Маркова.

Само слово «алгоритм» происходит от имени хорезмского учёного Абу Абдуллах Мухаммеда ибн Муса аль-Хорезми (алгоритм — аль-Хорезми). Около 825 года он написал сочинение, в котором впервые дал описание придуманной в Индии позиционной десятичной системы счисления. К сожалению, персидский оригинал книги не сохранился. Аль-Хорезми сформулировал правила вычислений в новой системе и, вероятно, впервые использовал цифру 0 для обозначения пропущенной позиции в записи числа (её индийское название арабы перевели как as-sifr или просто sifr, отсюда такие слова, как «цифра» и «шифр»). Приблизительно в это же время индийские цифры начали применять и другие арабские учёные. В первой половине XII века книга аль-Хорезми в латинском переводе проникла в Европу. Переводчик, имя которого до нас не дошло, дал ей название Algoritmi de numero Indorum («Алгоритмы о счёте индийском»). По-арабски же книга именовалась Китаб аль-джебр валь-мукабала («Книга о сложении и вычитании»). Из оригинального названия книги происходит слово Алгебра (алгебра — аль-джебр — восполнение).

Таким образом, мы видим, что латинизированное имя среднеазиатского учёного было вынесено в заглавие книги, и сегодня считается, что слово «алгоритм» попало в европейские языки именно благодаря этому сочинению. Однако вопрос о его смысле длительное время вызывал ожесточённые споры. На протяжении многих веков происхождению слова давались самые разные объяснения.

Одни выводили algorism из греческих algiros (больной) и arithmos (число). Из такого объяснения не очень ясно, почему числа именно «больные». Или же лингвистам больными казались люди, имеющие несчастье заниматься вычислениями? Своё объяснение предлагал и энциклопедический словарь Брокгауза и Ефрона. В нём алгорифм (кстати, до революции использовалось написание алгориѳм, через фиту) производится «от арабского слова Аль-Горетм, то есть корень». Разумеется, эти объяснения вряд ли можно счесть убедительными.

Упомянутый выше перевод сочинения аль-Хорезми стал первой ласточкой, и в течение нескольких следующих столетий появилось множество других трудов, посвящённых всё тому же вопросу — обучению искусству счёта с помощью цифр. И все они в названии имели слово algoritmi или algorismi.

Около 1250 года английский астроном и математик Иоанн Сакробоско написал труд по арифметике Algorismus vulgaris, на столетия ставший основным учебником по вычислениям в десятичной позиционной системе счисления во многих европейских университетах. Во введении Сакробоско назвал автором науки о счёте мудреца по имени Алгус (Algus).

Алгоритм — это искусство счёта с помощью цифр, но поначалу слово «цифра» относилось только к нулю. Знаменитый французский трувер Готье де Куанси (Gautier de Coincy, 1177—1236) в одном из стихотворений использовал словаalgorismus-cipher (которые означали цифру 0) как метафору для характеристики абсолютно никчёмного человека. Очевидно, понимание такого образа требовало соответствующей подготовки слушателей, а это означает, что новая система счисления уже была

Аба́к (др.-греч. ἄβαξ, ἀβάκιον, лат. abacus — доска) — счётная доска, применявшаяся для арифметических вычислений приблизительно с V века до н. э. в Древней Греции, Древнем Риме.им достаточно хорошо известна.

Многие века абак был фактически единственным средством для практичных вычислений, им пользовались и купцы, и менялы, и учёные. Достоинства вычислений на счётной доске разъяснял в своих сочинениях такой выдающийся мыслитель, как Герберт Аврилакский (938—1003), ставший в 999 г. папой римским под именем Сильвестра II. Новое с огромным трудом пробивало себе дорогу, и в историю математики вошло упорное противостояние лагерей алгорисмиков и абацистов (иногда называемых гербекистами), которые пропагандировали использование для вычислений абака вместо арабских цифр. Интересно, что известный французский математик Николя Шюке (Nicolas Chuquet, 1445—1488) в реестр налогоплательщиков города Лиона был вписан как алгорисмик (algoriste). Но прошло не одно столетие, прежде чем новый способ счёта окончательно утвердился, столько времени потребовалось, чтобы выработать общепризнанные обозначения, усовершенствовать и приспособить к записи на бумаге методы вычислений. В Западной Европе учителей арифметики вплоть до XVII века продолжали называть «магистрами абака».

Историки датируют 1691 годом один из списков древнерусского учебника арифметики, известного как «Счётная мудрость». Это сочинение известно во многих вариантах (самые ранние из них почти на сто лет старше) и восходит к ещё более древним рукописям XVI в. По ним можно проследить, как знание арабских цифр и правил действий с ними постепенно распространялось на Руси. Полное название этого учебника — «Сия книга, глаголемая по еллински и по гречески арифметика, а по немецки алгоризма, а по русски цифирная счётная мудрость».

Таким образом, слово «алгоритм» понималось первыми русскими математиками так же, как и в Западной Европе. Однако его не было ни в знаменитом словаре В. И. Даля, ни спустя сто лет в «Толковом словаре русского языка» под редакцией Д. Н. Ушакова (1935 г.). Зато слово «алгорифм» можно найти и в популярном дореволюционном Энциклопедическом словаре братьев Гранат, и в первом издании Большой советской энциклопедии (БСЭ), изданном в 1926 г. И там, и там оно трактуется одинаково: как правило, по которому выполняется то или иное из четырёх арифметических действий в десятичной системе счисления. Однако к началу XX в. для математиков слово «алгоритм» уже означало любой арифметический или алгебраический процесс, выполняемый по строго определённым правилам, и это объяснение также даётся в следующих изданиях БСЭ.

Формальные свойства алгоритмов

Различные определения алгоритма в явной или неявной форме содержат следующий ряд общих требований:

  • Дискретность — алгоритм должен представлять процесс решения задачи как последовательное выполнение некоторых простых шагов. При этом для выполнения каждого шага алгоритма требуется конечный отрезок времени, то есть преобразование исходных данных в результат осуществляется во времени дискретно.
  • Детерминированность (определённость). В каждый момент времени следующий шаг работы однозначно определяется состоянием системы. Таким образом, алгоритм выдаёт один и тот же результат (ответ) для одних и тех же исходных данных. В современной трактовке у разных реализаций одного и того же алгоритма должен быть изоморфный граф. С другой стороны, существуют вероятностные алгоритмы, в которых следующий шаг работы зависит от текущего состояния системы и генерируемого случайного числа. Однако при включении метода генерации случайных чисел в список «исходных данных», вероятностный алгоритм становится подвидом обычного.
  • Понятность — алгоритм должен включать только те команды, которые доступны исполнителю и входят в его систему команд.
  • Завершаемость (конечность) — при корректно заданных исходных данных алгоритм должен завершать работу и выдавать результат за конечное число шагов. С другой стороны, вероятностный алгоритм может и никогда не выдать результат, но вероятность этого равна 0.
  • Массовость (универсальность). Алгоритм должен быть применим к разным наборам исходных данных.
  • Результативность — завершение алгоритма определёнными результатами.
  • Алгоритм содержит ошибки, если приводит к получению неправильных результатов либо не даёт результатов вовсе.
  • Алгоритм не содержит ошибок, если он даёт правильные результаты для любых допустимых исходных данных.
Читать еще:  Компьютерный шпион Mipko Personal Monitor — обнаружить и удалить. Как отследить поведение пользователя за компьютером в ваше отсутствие Mipko комбинация клавиш для запуска

Виды алгоритмов

Особую роль выполняют прикладные алгоритмы, предназначенные для решения определённых прикладных задач. Алгоритм считается правильным, если он отвечает требованиям задачи (например, даёт физически правдоподобный результат). Алгоритм (программа) содержит ошибки, если для некоторых исходных данных он даёт неправильные результаты, сбои, отказы или не даёт никаких результатов вообще. Последний тезис используется в олимпиадах по алгоритмическому программированию, чтобы оценить составленные участниками программы.

Виды алгоритмов как логико-математических средств отражают указанные компоненты человеческой деятельности и тенденции, а сами алгоритмы в зависимости от цели, начальных условий задачи, путей ее решения, определения действий исполнителя подразделяются следующим образом:

Механические алгоритмы, или иначе детерминированные, жесткие (например, алгоритм работы машины, двигателя и т. п.) — задают определенные действия, обозначая их в единственной и достоверной последовательности, обеспечивая тем самым однозначный требуемый или искомый результат, если выполняются те условия процесса, задачи, для которых разработан алгоритм.

Гибкие алгоритмы, например стохастические, то есть вероятностные и эвристические.

Вероятностный (стохастический) алгоритм дает программу решения задачи несколькими путями или способами, приводящими к вероятному достижению результата.

Эвристический алгоритм (от греческого слова «эврика») — алгоритм, использующий различные разумные соображения без строгих обоснований[11].

Линейный алгоритм — набор команд (указаний), выполняемых последовательно во времени друг за другом.

Разветвляющийся алгоритм — алгоритм, содержащий хотя бы одно условие, в результате проверки которого может осуществляться разделение на несколько параллельных ветвей алгоритма.

Циклический алгоритм — алгоритм, предусматривающий многократное повторение одного и того же действия (одних и тех же операций) над новыми исходными данными. К циклическим алгоритмам сводится большинство методов вычислений, перебора вариантов. Цикл программы — последовательность команд (серия, тело цикла), которая может выполняться многократно (для новых исходных данных) до удовлетворения некоторого условия.

Вспомогательный (подчиненный) алгоритм (процедура) — алгоритм, ранее разработанный и целиком используемый при алгоритмизации конкретной задачи. В некоторых случаях при наличии одинаковых последовательностей указаний (команд) для различных данных с целью сокращения записи также выделяют вспомогательный алгоритм. На всех этапах подготовки к алгоритмизации задачи широко используется структурное представление алгоритма.

Структурная блок-схема, граф-схема алгоритма — графическое изображение алгоритма в виде схемы связанных между собой с помощью стрелок (линий перехода) блоков — графических символов, каждый из которых соответствует одному шагу алгоритма. Внутри блока дается описание соответствующего действия. Графическое изображение алгоритма широко используется перед программированием задачи вследствие его наглядности, так как зрительное восприятие обычно облегчает процесс написания программы, ее корректировки при возможных ошибках, осмысливание процесса обработки информации.

Можно встретить даже такое утверждение: «Внешне алгоритм представляет собой схему — набор прямоугольников и других символов, внутри которых записывается, что вычисляется, что вводится в машину и что выдается на печать и другие средства отображения информации «.

Представление алгоритмов

Формы записи алгоритма:

  • словесная или вербальная (языковая, формульно-словесная);
  • псевдокод (формальные алгоритмические языки);
  • схематическая:
    • графическая (блок-схемы и ДРАКОН-схемы);
    • структурограммы (диаграммы Насси-Шнейдермана).

Обычно сначала (на уровне идеи) алгоритм описывается словами, но по мере приближения к реализации он обретает всё более формальные очертания и формулировку на языке, понятном исполнителю (например, машинный код).

Пример

В качестве примера можно привести алгоритм Евклида.

Алгоритм Евклида — эффективный метод вычисления наибольшего общего делителя (НОД). Назван в честь греческого математика Евклида; один из древнейших алгоритмов, который используют до сих пор[22].

Описан в «Началах» Евклида (примерно 300 до н. э.), а именно в книгах VII и X. В седьмой книге описан алгоритм для целых чисел, а в десятой — для длин отрезков.

Существует несколько вариантов алгоритма, ниже записанный в псевдокоде рекурсивный вариант:

Алгори́тм, от имени учёного аль-Хорезми — точный набор инструкций, описывающих порядок действий исполнителя для достижения результата решения задачи за. Алгоритм, виды алгоритмов

Вопрос

Понятие алгоритма. Свойства и способы записи алгоритма. Исполнитель алгоритма. Система команд исполнителя.

Ответ

Понятие алгоритма.

Алгори́тм — набор инструкций, описывающих порядок действий исполнителя для достижения результата решения задачи за конечное число действий.

Свойства и способы записи алгоритма

Для записи алгоритмов используют самые разнообразные средства. Выбор средства определяется типом исполняемого алгоритма. Выделяют следующие основные способы записи алгоритмов:

вербальный, когда алгоритм описывается на человеческом языке;

символьный, когда алгоритм описывается с помощью набора символов;

графический, когда алгоритм описывается с помощью набора графических изображений.

Общепринятыми способами записи являются графическая запись с помощью блок-схем и символьная запись с помощью какого-либо алгоритмического языка.

Описание алгоритма с помощью блок схем осуществляется рисованием последовательности геометрических фигур, каждая из которых подразумевает выполнение определенного действия алгоритма. Порядок выполнения действий указывается стрелками. Написание алгоритмов с помощью блок-схем регламентируется ГОСТом. Внешний вид основных блоков, применяемых при написании блок схем, приведен на рисунке:

В зависимости от последовательности выполнения действий в алгоритме выделяют алгоритмы линейной, разветвленной и циклической структуры.

В алгоритмах линейной структуры действия выполняются последовательно одно за другим:

В алгоритмах разветвленной структуры в зависимости от выполнения или невыполнения какого-либо условия производятся различные последовательности действий. Каждая такая последовательность действий называется ветвью алгоритма.

В алгоритмах циклической структуры в зависимости от выполнения или невыполнения какого-либо условия выполняется повторяющаяся последовательность действий, называющаяся телом цикла.Вложенным называется цикл, находящийся внутри тела другого цикла. Различают циклы с предусловиеми послеусловием:

Итерационным называется цикл, число повторений которого не задается, а определяется в ходе выполнения цикла. В этом случае одно повторение цикла называется итерацией.

Алгоритм обладает следующими свойствами:

1. Дискретность. Это свойство состоит в том, что алгоритм должен представлять процесс решения задачи как последовательное выполнение простых шагов. При этом для выполнения каждого шага алгоритма требуется конечный отрезок времени, т.е. преобразование исходных данных в результат осуществляется во времени дискретно.

2. Определенность. Каждое правило алгоритма должно быть четким, однозначным.

3. Результативность. Алгоритм должен приводить к решению за конечное число шагов.

4. Массовость. Алгоритм решения задачи разрабатывается в общем виде, т.е. он должен быть применим для некоторого класса задач, различающихся лишь исходными данными.

5. Правильность. Алгоритм правильный, если его выполнение дает правильные результаты решения поставленной задачи.

Скажите опредиление слову «Алгоритм»!!

АЛГОРИТМ — система правил, сформулированная на понятном исполнителю языке, которая определяет процесс перехода от допустимых исходных данных к некоторому результату и обладает свойствами массовости, конечности, определенности, детерминированности. (Энциклопедия «Кругосвет» )

АЛГОРИТМ (АЛГОРИФМ) [algorithm] — точное предписание относительно последовательности действий (шагов) , преобразующих исходные данные в искомый результат. (Экономико-математический словарь)

АЛГОРИТМ (от лат. формы имени среднеазиатского математика аль-Хорезми) — правило действий, последовательность проведения вычислительных операций, способ нахождения искомого результата. (Современный экономический словарь)

Алгоритм — точное предписание исполнителю совеpшить определенную последовательность действий для достижения поставленной цели за конечное число шагов. (Cловарь по естественным наукам. Глоссарий. ру)

«Алгоритм — это конечный набор правил, который определяет последовательность операций для решения конкретного множества задач и обладает пятью важными чертами: конечность, определённость, ввод, вывод, эффективность» . (Д. Э. Кнут)

«Алгоритм — это всякая система вычислений, выполняемых по строго определённым правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи» . (А. Колмогоров)

«Алгоритм — это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату» . (А. Марков)

«Алгоритм — точное предписание о выполнении в определённом порядке некоторой системы операций, ведущих к решению всех задач данного типа» . (Философский словарь / Под ред. М. М. Розенталя)

«Алгоритм — строго детерминированная последовательность действий, описывающая процесс преобразования объекта из начального состояния в конечное, записанная с помощью понятных исполнителю команд» . (Николай Дмитриевич Угринович, учебник «Информатика и информ. технологии» )

«Алгоритм — это последовательность действий, направленных на получение определённого результата за конечное число шагов» .

«Алгоритм — однозначно, доступно и кратко (условные понятия — названия этапа) описанная последовательность процедур для воспроизводства процесса с обусловленным задачей алгоритма результатом при заданных начальных условиях. Универсальность (или специализация) алгоритма определяется применимостью и надёжностью данного алгоритма для решения нестандартных задач».

Ссылка на основную публикацию
Статьи c упоминанием слов:
Adblock
detector