Реферат

по дисциплине «Специальные главы математики»

на тему: «Элементы теории алгоритмов»

Оглавление

Введение. 3

История появления термина «алгоритм». 4

Основные свойства алгоритма. 4

Уточнение понятия алгоритма. Машина Тьюринга. 5

Способы представления алгоритма. 8

Базовые структуры программирования. 10

Заключение. 17

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

Введение

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

История появления термина «алгоритм»

Происхождение термина «алгоритм» связано с математикой. История его возникновения такова. В IX веке в Багдаде жил 4 ученый ал-Хорезми (полное имя – Мухаммед бен Муса ал - Хорезми), математик, астроном, географ. В одном из своих трудов он описал десятичную систему счисления и впервые сформулировал правила выполнения арифметических действий над целыми числами и обыкновенными дробями. Арабский оригинал этой книги был утерян, но остался латинский перевод XII в., по которому Западная Европа ознакомилась с десятичной системой счисления и правилами выполнения арифметических действий. Правила в книгах ал-Хорезми в латинском переводе начинались словами «Алгоризми сказал». В других латинских переводах автор именовался как Алгоритмус. Со временем было забыто, что Алгоризми (Алгоритмус) - это автор правил, и эти правила стали называть алгоритмами. Многие столетия разрабатывались алгоритмы для решения все новых и новых классов задач, но само понятие алгоритма не имело точного математического определения. В настоящее время понятие алгоритма уточнено. Алгоритм - понятное и точное предписание исполнителю совершить последовательность действий, направленных на достижение цели.

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

Значение слова «алгоритм» очень схоже со значением слов «рецепт», «метод», «способ». Однако любой алго­ритм, в отличие от рецепта или способа, обязательно об­ладает следующими свойствами:

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

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

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

·Алгоритм всегда рассчитан на выполнение «нераз­мышляющим» исполнителем.

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

·Свойство результативности содержит в себе свойство конечности - завершение работы алгоритма за конеч­ное число шагов.

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

Уточнение понятия алгоритма. Машина Тьюринга

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

Постепенно математики подходили к постановке и ре­шению все более сложных задач. Так, например, Г. Лейбниц в XVII веке пытался построить общий алго­ритм решения любых математических задач. В XX веке эта идея приобрела более конкретную форму: построить алгоритм проверки правильности любой теоремы при любой системе аксиом. Построить такие алгоритмы не удавалось, и математики выдвинули предположение: а вдруг для того или иного класса задач в принципе невоз­можно построить алгоритм решения? Следовательно, если алгоритма не существует, то они ищут то, чего нет.

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

Попытки выработать формальное определение алго­ритма привели в 20-30-х годах XX века к возникнове­нию теории алгоритмов. В первой половине XX века разные математики (А. Тьюринг, Э. Пост, А. Н. Колмо­горов, А. А. Марков и др.) предложили несколько под­ходов к формальному определению алгоритма: нормаль­ный алгоритм Маркова, машина Тьюринга, машина По­ста и т. д. В дальнейшем было показано, что все эти определения эквивалентны.

Тьюринг признан одним из основателей информатики и теории искусственного интеллекта, его считают первым теоретиком современного программирования. У Алана Тьюринга целью создания такой абстрактной воображаемой машины было получение возможности до­казательства существования или несуществования алго­ритмов решения различных задач. Руководствуясь этой целью, Тьюринг искал как можно более простую, «бед­ную» алгоритмическую схему, лишь бы она была уни­версальной.

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

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

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

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

На машине Тьюринга можно имитироватьПоста, алгоритмы Марковаи любую программу для обычных компьютеров, преобразующую входные данные в выходные по какому-либо алгоритму. В свою очередь, на различных абстрактных исполнителях можно имитировать Машину Тьюринга. Исполнители, для которых это возможно, называютсяполными по Тьюрингу(Turing complete).

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

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

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

·Словесная (вербальная) на неформальном языке.

·На языках программирования.

·Графическая.

Словесная форма представления алгоритма имеет ряд недостатков. Для достаточно сложных алгоритмов описание 6 становится слишком громоздким и не наглядным. Эта форма представления обычно используется лишь на начальных стадиях разработки алгоритма. Пример словесной формы описания алгоритма: Чтобы перейти улицу, нужно посмотреть налево, убедиться в отсутствии приближающегося транспорта, дойти до середины улицы, посмотреть направо, убедиться в отсутствии близко идущего транспорта, продолжить движение через улицу. При наличии движущихся транспортных средств нужно ждать, когда транспорт проедет. Алгоритм, записанный на языке программирования, называется программой. Графическая форма представления алгоритмов является более наглядной и строгой. Алгоритм изображается в виде последовательности связанных между собой блоков, каждый из которых соответствует выполнению одного или нескольких операторов. Такое графическое представление называется блок-схемой алгоритма. Условные графические обозначения символов, используемых для составления блок-схемы алгоритма, стандартизированы. Некоторые, часто используемые обозначения, приведены на рисунке 1.

Рисунок 1 - Условные графические обозначения

Направления линий потока сверху вниз и слева направо принимаются за основные и, если линии потоков не имеют изломов, стрелками не обозначаются. Обратные направления линий потока помечаются стрелкой. «Процесс» (этап вычисления) изображается прямоугольником, внутри которого записывается набор действий. Ромбом изображается «решение», внутри которого осуществляется проверка условия. Ввод исходных данных и вывод результатов изображаются параллелограммами, внутри которых пишутся слова 8 «ввод» или «вывод» и перечисляются переменные, подлежащие вводу или выводу. Представление алгоритма в виде блок-схемы является промежуточным, так как алгоритм в таком виде не может быть непосредственно выполнен ЭВМ, но помогает пользователю при создании (написании) программы для ПК. Использование блок-схем дает возможность:

·наглядно отобразить базовые конструкции алгоритма;

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

·анализировать логическую структуру алгоритма;

·преобразовывать алгоритм методом укрупнения (сведения к единому блоку) или детализации - разбиения на ряд блоков

·использовать принцип блочности при коллективном решении сложной задачи;

·осуществить быструю проверку разработанного алгоритма (на уровне идеи);

·разобрать большее число учебных задач.

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

Базовые структуры программирования

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

1. Линейная.

2. Разветвляющаяся (альтернатива «если-то-иначе» или «если-то»).

3. Циклическая (повторение).

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

Рисунок 2 - Линейная структура

Прямоугольник, показанный на рисунке, может представлять как одну единственную команду, так и множество операторов, необходимых для выполнения сложной обработки данных, где F1 и F2 - некоторые команды для соответствующего исполнителя. Команды записываются с помощью операции присваивания. Присваивание переменной какого-либо значения или присваивание одной переменной значения другой переменной является наиболее часто выполняемым действием в программе, написанной на любом языке программирования. В языке программирования присваивание является операцией и обозначается как «:=». Это означает, что при выполнении этой операции происходит не только присваивание значения определенной переменной, но и возвращается некоторое значение.

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

Рисунок 3 - Ветвление

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

Рисунок 4 - Неполное ветвление

Также эта структура называется «ЕСЛИ - ТО - ИНАЧЕ». Каждый из путей (ТО или ИНАЧЕ) ведет к общей точке слияния, так что выполнение программы продолжается независимо от того, какой путь был выбран. Циклическая структура (или повторение) предусматривает повторное выполнение некоторого набора действий. Циклы позволяют записать длинные последовательности операций обработки данных с помощью небольшого числа повторяющихся команд.

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

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

1. Вывести список всех файлов, удовлетворяющих критерию запроса.

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

Рисунок 5 - Рекурсия

Различают циклы с предусловием и циклы с постусловием. Цикл начинается с проверки логического выражения «P». Если оно истинно, то выполняется «F», затем все повторяется снова, до тех пор, пока логическое выражение сохраняет значение «истина». Как только оно становится ложным, выполнение операций «F» прекращается и управление передается по программе дальше. Так как выражение, управляющее циклом, проверяется в самом начале, то в случае, если условие сразу окажется ложным, операторы циклической части «F» могут вообще не выполняться. Операторы циклической части «F» должны изменять переменную (или переменные), влияющую на значение логического выражения, иначе программа «зациклится» - будет выполняться бесконечно. Рассмотренная циклическая конструкция называется цикл «пока», или цикл с предусловием (см. рис. 6).

Рисунок 6 – Цикл с предусловием

Существует и иная конструкция цикла, которая предусматривает проверку условия после выполнения команд, встроенных внутрь цикла. Это цикл с постусловием (см. рис. 7).

Рисунок 7 – Цикл с постусловием

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

Рисунок 8 - Алгоритм типа «цикл, вложенный в неполную развилку»

Рисунок 9 - Алгоритм типа «цикл в цикле»

Рисунок 10 - Алгоритм типа «развилка в развилке»

Рисунок 11 - Иллюстрация трехкратного вложения одной базовой структуры в другую

Заключение

Понятие алгоритма всегда неявно присутствовало в математике с самых её начал - арифметики. Однако сколько же лет прошло от изобретения первого алгоритма до формального осмысления понятия «алгоритм»? Два тысячелетия! Такой срок удивляет. Но на данный момент теория алгоритмов настолько быстро и интенсивно развивается, что успела проникнуть в самые основы математики. Также она стала родителем такой области деятельности ныне, как программирование, без которой нельзя даже помыслить дальнейшее развитие человечества.

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

1. Бильгаева Н.Ц. Теория алгоритмов, формальных языков, грамматик и автоматов /Бильгаева Н.Ц. –Улан-Удэ: Издательство ВСГТУ, 2000. – 51 с.

2. Павловский Е.Н. Теория алгоритмов: истоки, открытия: Реферат / Павловский Е.Н; НГУ. – Новосибирск, 2006. – 26 с.

3. С.А. Рогозин. Алгоритмы. Основные алгоритмические конструкции: сб. задач / сост. С.А. Рогозин. – Челябинск: Изд-во Челяб. гос. пед. ун-т, 2008. – 42 с.

4. Информатизация системы образования [Электронный ресурс]. -http://www.ido.rudn.ru/nfpk/inf/inf8.html

5. Пекелис В. Маленькая энциклопедия о большой кибернетике. - М.: Дет. лит., 1970.

6. Угринович Н.Д. Информатика и информационные технологии. Учебник 10-11 класс. М.: Лаборатория Базовых Знаний, 2001.

7. Угринович Н.Д. Информатика и информационные технологии. Учебное пособие для 10-11-х классов. М.: Лаборатория Базовых Знаний, 2000.