Известнейшие алгоритмы в истории математики реферат по информатике

Обновлено: 05.07.2024

Собрала для вас похожие темы рефератов, посмотрите, почитайте:

Введение

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

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

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

Такие качества:

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

Во-первых, неправильно связывать алгоритм с решением проблемы. Алгоритм может вообще не решить проблему.

Типы алгоритмов

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

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

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

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

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

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

На всех этапах подготовки к алгоритмизации задачи часто используется структурное представление алгоритма.

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

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

Требования к алгоритму

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

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

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

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

Заключение

Список литературы

Образовательный сайт для студентов и школьников

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

Содержание

4.2. Разветвленные алгоритмы………………………………………….…6

4.3. Циклические алгоритмы………………………………………………7

5. Способы описания алгоритма………………………………………. ……10

5.1. Словесное описание алгоритма……………………………..……….10

5.2. Графическое описание алгоритма……………………. …………. 10

5.3. Описание алгоритма на алгоритмическом языке……………..…. 12

Работа содержит 1 файл

Реферат.docx

1. Содержание

4.2. Разветвленные алгоритмы………………… ……………………….…6

4.3. Циклические алгоритмы……………………… ………………………7

5. Способы описания алгоритма……………………………… ………. ……10

5.1. Словесное описание алгоритма…… ………………………..……….10

5.2. Графическое описание алгоритма……………………. …………. 10

5.3. Описание алгоритма на алгоритмическом языке……………..…. 12

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

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

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

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

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

Дальше я более подробно расскажу о видах алгоритма в информатике.

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

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

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

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

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

линейные алгоритмы;
разветвленные алгоритмы;
циклические алгоритмы.

4.1. Линейные алгоритмы

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

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

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

Пример . Зная длины трех сторон треугольника, вычислить площадь и периметр треугольника. Пусть a, b, c – длины сторон треугольнике. Необходимо найти S –площадь треугольника и P – периметр.

Для нахождения площади можно воспользоваться формулой Герона:

Выходные данные: S, P.

4.2. Разветвленные алгоритмы

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

Фрагмент алгоритма Пример разветвления

Пример. Составить программу нахождения действительных и комплексных корней квадратного уравнения.

Блок-схема решения задачи. Блок 1 предназначен для ввода коэффициентов квадратного уравнения. В блоке 2 осуществляется вычисление дискриминанта. Блок 3 осуществляет проверку знака дискриминанта, если дискриминант отрицателен, то корни комплексные, их расчет происходит в блоке 4 (действительная часть корня записывается в переменную x₁, модуль мнимой - в переменную x₂), а вывод - в блоке 5 (первый корень x₁ + i x₂, второй - x₁- i x₂). Если дискриминант положителен, то вычисляются действительные корни уравнения (блок 6) и выводятся на экран (блок 7).

4.3. Циклические алгоритмы

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

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

в цикле с предусловием условие проверяется до тела цикла, в цикле с постусловием - после тела цикла;
в цикле с постусловием тело цикла выполняется хотя бы один раз, в цикле с предусловием тело цикла может не выполниться ни разу;
в цикле с предусловием проверяется условие продолжения цикла, в цикле с постусловием - условие выхода из цикла.

Алгоритм циклической структ уры с предусловием

Алгоритм циклической стру ктуры с постусловием

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

Пример. Найти наибольший общий делитель (НОД) двух натуральных чисел А и В.

В блок-схеме решения задачи, представленной на рис. 2.5, для решения поставленной задачи используется цикл с предусловием, то есть тело цикла повторяется до тех пор, пока А не равно В.

5. Способы описания алгоритма

На практике наиболее распространены следующие формы представления алгоритмов:

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

5.1. Словесное описание алгоритма

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

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

Содержание

Введение 3
1. История 4
2. Понятие алгоритма. Сущность алгоритмизации 8
3. Свойства алгоритма 9
5. Типовые структуры алгоритмов 13
5.1. Линейная структура 13
5.2. Разветвляющаяся структура 13
5.3. Циклическая структура 13
Заключение 15
Литература 16

Прикрепленные файлы: 1 файл

Реферат.docx

Министерство Образования Российской Федерации
Дальневосточный Федеральный Университет (ДВФУ)
Школа экономики и менеджмента

Выполнила: ст. гр. Б1104

Иванова Ирина Ивановна.

Проверил: Тихоновская Галина Ивановна
– преподаватель, доцент.

Владивосток, 2013 г.

2. Понятие алгоритма. Сущность алгоритмизации 8

3. Свойства алгоритма 9

5. Типовые структуры алгоритмов 13

5.1. Линейная структура 13

5.2. Разветвляющаяся структура 13

5.3. Циклическая структура 13

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

Древнегреческий ученый Эратосфен (II в. до н. э.) предложил способ получения простых чисел (т.н. "решето Эратосфена"). В IX в. узбекский математик Мухаммад Ал-Хорезми разработал правила четырех арифметических действий над числами. В Европе эти правила стали называть алгоритмами (от латинской формы написания имени автора - Alchorismi илиAlgorithmi). Переводы арифметического трактата Ал-Хорезми с арабского содержали описание индийской позиционной системы счисления и искусства счета в этой системе (например, алгоритм сложения "столбиком"). Таким образом, сначала понятие "алгоритм" обозначало десятичную позиционную арифметику и процедуры цифровых вычислений.

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

Суть упомянутого выше алгоритма Евклида состоит в том, чтобы вычитать из большего числа меньшее, подставляя результат на место большего числа, до тех пор, пока числа не станут равны друг другу. Эти равные числа и будут наибольшим общим делителем их разности и любого из чисел. Идея алгоритма понятна, но требует уточнения для использования ее на практике. Более конкретно алгоритм выглядит следующим образом:

А. Сравнить первое и второе числа. Если они равны, перейти к п. Г. Если нет, то перейти к п.Б.

Б. Если первое число меньше второго, то переставить их. Перейти к п.В.

В. Вычесть из первого числа второе и рассмотреть полученную разность как новое первое число. Перейти к п.А.
Г. Считать первое число результатом задачи.

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

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

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

А поскольку объектом алгоритма может оказаться все, что угодно, то начать следовало с формализации понятия объекта. Например, любые объекты реального мира можно обозначать словами в некотором алфавите. Тогда объектами действия алгоритмов могут быть только слова. В этом случае алгоритм может быть определен, как четкая конечная система правил для преобразования слов из некоторого алфавита в слова из этого же алфавита.

В начале ХХ в. алгоритм стал объектом математического изучения.

Общее понятие алгоритма как эффективной вычислительной процедуры и примеры использования такого понятия встречаются в работах француза Э.Бореля (1912 г.) и немца Г.Вейля (1921 г.). Оба они пришли к понятию вычислимой функции (термин "fonction calculable").

Одно из первых формальных определений алгоритма дал английский математик А.Тьюринг [1, 2], который в 1936 году описал схему гипотетической (абстрактной) машины и назвал алгоритмом то, что умеет делать такая машина. А если что-то не может быть сделано машиной Тьюринга, то это уже не алгоритм. Таким образом, Тьюринг формализовал правила выполнения действий при помощи описания работы некоторой конструкции. Вычислительные машины - это тоже конструкции для выполнения алгоритмов, но это реальные устройства, тогда как машина Тьюринга - это математическая модель, она является абстракцией, которая никогда не была реализована, да и вообще не может быть реализована. Польза от машины Тьюринга в том, что, говоря о воображаемой конструкции, можно доказывать существование или несуществование алгоритмов решения различных задач.

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

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

В 1954 г. советский математик А.А. Марков[1] предложил свою алгоритмическую схему преобразования слов, назвав ее нормальным алгоритмом. Он ввел также понятие нормализации как перехода от разных способов описания алгоритмов к эквивалентным нормальным алгоритмам. Основная гипотеза теории алгоритмов в форме Маркова звучит так: "Всякий алгоритм нормализуем". Как и машина Тьюринга, алгоритмическая схема Маркова в общем случае не может быть физически реализована, т.к. она, например, допускает неограниченно большую длину слов. А вот формулировка алгоритма по Маркову: "Алгоритм - это точное предписание, которое задает вычислительный процесс, начинающийся с произвольного (но выбранного из фиксированной для данного алгоритма совокупности) исходного данного и направленный на получение полностью определяемого этим исходным данным результата" [2].

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

Наиболее общий подход к уточнению понятия алгоритма предложил советский ученый Колмогоров А.Н.[2], который дал и его "наглядное" представление: "Алгоритм, примененный ко всякому "условию" ("начальному состоянию") из некоторого множества ("области применимости" алгоритма), дает "решение" ("заключительное состояние"). Алгоритмический процесс расчленяется на отдельные шаги заранее ограниченной сложности; каждый шаг состоит в "непосредственной переработке"… (одного) состояния в (другое). Процесс переработки… продолжается до тех пор, пока либо не произойдет безрезультатная остановка, либо не появится сигнал о получении "решения". При этом не исключается возможность неограниченного продолжения процесса…" Формулировка Колмогорова содержит два существенных момента: идея итеративности алгоритмиче ского процесса и идея локальности каждого отдельного шага.

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

В настоящее время понятие "алгоритм" вышло за пределы математики. Его стали применять в самых различных областях, понимая под ним точно сформулированные инструкции, назначение которых - достижение необходимого результата.
Формирование научного понятия алгоритма, ставшее важной проблемой, не закончено и в настоящее время. Теория алгоритмов, как любая другая наука, находится в постоянном развитии. Согласно утверждению авторов [2], современная теория алгоритмов может быть разделена на две части.

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

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

2. Понятие алгоритма. Сущность алгоритмизации

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

Алгоритм - это строгая, четкая последовательность математических и логических операций, приводящая к решению задачи.

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

Алгоритмизация процессов в широком смысле - это описание процессов на языке математических символов для получения алгоритма, отображающего элементарные акты процесса, их последовательность и взаимосвязь. Для построения алгоритма управления, например, необходимо к алгоритму, описывающему процесс функционирования системы, присоединить алгоритм определения оптимального решения или оптимальных значений параметров управления. В более узком смысле алгоритмизация - это процедура поиска, разработки и описания алгоритма решения задачи [5].

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

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

Для учеников 1-11 классов и дошкольников
Бесплатные сертификаты учителям и участникам

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

1) на основе понятия рекурсивной функции;

2) на основе описания алгоритмического процесса.

Эти и другие подходы подтвердили целесообразность использования тезиса Черча и тезиса Тьюринга для решения алгоритмических проблем.

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

- изучить историю появления понятия;

- рассмотреть применение алгоритмов в математике;

- рассмотреть применение алгоритмов в информатике;

- рассмотреть свойства алгоритмов;

- рассмотреть машины Поста и Тьюринга.

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

Алгоритм одно из самых основных понятий вычислительной математики. Это понятие возникло в связи с поисками общих методов решения однотипных задач задолго до появления ЭВМ.

1. Сравнить первое и второе числа. Если они равны, перейти к процедуре 4. Если нет, то перейти к процедуре 2.

2. Если первое число меньше второго, то переставить их. Перейти к процедуре 3.

3. Вычесть из первого числа второе и рассмотреть полученную разность как новое первое число. Перейти к процедуре 1 .
4. Считать первое число результатом задачи.

Такой набор правил и является алгоритмом. Следуя ему любой человек может найти НОД.

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

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

В начале ХХ века алгоритм стал объектом математического изучения.

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

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

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

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

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

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

1) указание совокупности возможных исходных данных;

2) правило, по которому процесс признается закончившимся ввиду достижения результата.

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

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

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

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

1) совокупность возможных исходных данных,

2) совокупность возможных результатов,

3) совокупность промежуточных результатов,

4) правило начала,

5) правило непосредственной переработки,

6) правило окончания,

- определенность – в любой момент времени исполнитель должен знать, какое действие нужно сделать;

- дискретность – разбиение алгоритма на некоторые действия, которые следуют друг за другом;

- массовость - по одному и тому же алгоритму могут решаться однотипные задачи и причем решаться они могут неоднократно;

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

- результативность означает, что алгоритм всегда должен приводить к результату.

В настоящее время понятие алгоритма - одно из фундаментальных понятий науки информатика. Широкое применение алгоритмов для решения практических задач не только при использовании ЭВМ позволяет рассматривать эту область информатики как отдельную дисциплину - алгоритмику.

В информатике абсолютно любая программа представлена алгоритмом потому, что это последовательность определенных и продуманных действий, которые описаны в виде кода (инструкций компьютеру). К примеру, программа ввести 2 числа m и k и найти их сумму.

Write ln ('Введите через пробел два числа ');

Write ln ('Сумма чисел равна ', h );

Рассмотренный кусочек кода является алгоритмом. Алгоритм данной программы включает в себя такие действия:

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

- Затем находит их сумму.

- В итоге выводит отчет.

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

1. 4 Машина Тьюринга

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

Рисунок 1.1 – Схема машины Тьюринга

Рисунок 1.3 - Пример задачи 1

Этот же пример можно представить так:

Рисунок 1.4 – Пример задачи 2

1.5 Машина Поста

Данная абстрактная машина была предложена Э. Постом в 1937 году. Эта вычислительная машина проста в применении, этим она и отличается от машины Тьюринга.

2) С - стереть метку.

4) -> - сдвинуться вправо.

- если в ячейке нет метки, то перейти к m 2 строке программы,

иначе перейти к m 1 строке программы.

6) Стоп – конец программы (стоп).

Рисунок 1.2 – Абстрактная машина Поста

После запуска программы машина Поста имеет несколько возможных вариантов работы:

- работа может закончиться невыполнимой командой (стирание несуществующей метки или запись в помеченное поле);

- работа никогда не закончится.

Пример: головка стоит слева над начальной ячейкой. Нужно перейти на следующую пустую ячейку и поставить там метку.

Машина Поста также была предложена для формализации понятия алгоритм.

Впл o ть до 30-х годов нашего ст o летия п o нятие алгоритма o ставалось интуитивн o п o нятным, имевшим ск o рее метод o л o гическое значение, а не математическ o е.

Цель работы была достигнута. Поставленные задачи были решены.

Библиографический список

Методика преподавания информатики: учеб. пособие для студ. пед. вузов / М.П. Лапчик, И.Г. Семакин, Е.К. Хеннер; под общей ред.

BOREL E. Le calcul des integrales definies // Journal de Mathematiques pures et appliquees. Ser. 6. — V.8, № 2. 1912. — P.159–210.

Математическая логика и вычислительная математика // Вестник Академии наук СССР. №8. — с.21–25

Википедия — свободная энциклопедия // Алгоритм. –(Рус).

Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов: Пер. с англ.-М.: Мир,1979.

Функция "чтения" служит для ознакомления с работой. Разметка, таблицы и картинки документа могут отображаться неверно или не в полном объёме!

Федеральное агентство по образованию

Тюменский государственный университет

Институт математики и компьютерных наук РЕФЕРАТ

Руководитель: доцент, к.т.н.

Охотников Евгений Сергеевич Тюмень - 2015 Оглавление Введение

.2 Основная версия

. Современное понятие алгоритма

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

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

.4 Требования, предъявляемые к алгоритму

. Алгоритмы в математике

.1 Алгоритм Евклида

.2 Решето Эратосфена

.3 Алгоритм при решении уравнений

.3.1 Алгоритм нахождения неизвестного слагаемого

.3.2 Алгоритм нахождения неизвестного уменьшаемого

.3.3 Алгоритм нахождения неизвестного вычитаемого

.3.4 Алгоритм нахождения неизвестного множителя

.3.5 Алгоритм нахождения неизвестного делимого

.3.6 Алгоритм нахождения неизвестного делителя

.4 Алгоритмические действия с положительными и отрицательными числами

.4.1 Алгоритм сложения двух отрицательных чисел

.4.2 Алгоритм сложения чисел с разными знаками

.4.3 Алгоритм умножения чисел с разными знаками

.4.4 Алгоритм деления отрицательного числа на отрицательное число

.4.5 Алгоритм деления чисел с разными знаками

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

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

Но, греческая версия происхождения этого слова была не единственной. Мифический АлГор (Algor) именовался то королём Кастилии (Rex quodam Castelliae), то индийским королём, то арабским мудрецом (philosophus Algus nomine Arabicus), то

Читайте также: