Полный текст:
Содержание:
1.Введение…………………………………………………………………….2
2. Исторический обзор. ………………………………………………………3
3. Цели и задачи теории
алгоритмов.………………………………………..5
4.Практическое применение
результатов теории алгоритмов. ……………7
5. Формализация понятия алгоритма. ………………………………………8
6.Список литературы. ………………………………………………………..11
1. Введение.
Понятие
“алгоритм” давно является привычным не только для математиков. Оно является
концептуальной основой разнообразных процессов обработки информации.
Возможность автоматизации таких процессов обеспечивается наличием
соответствующих алгоритмов. С алгоритмами первое знакомство происходит в
начальной школе при изучении арифметических действий с натуральными числами. В
упрощенном понимании “алгоритм” – это то, что можно запрограммировать на ЭВМ.
В
настоящее время теория алгоритмов образует теоретический фундамент
вычислительных наук. Применение теории алгоритмов осуществляется как в
использовании самих результатов (особенно это касается использования
разработанных алгоритмов), так и в обнаружении новых понятий и уточнении
старых. С ее помощью проясняются такие понятия как доказуемость, эффективность,
разрешимость и другие.
Понятие
алгоритма занимает одно из центральных
мест в современной математике, прежде всего вычислительной. Алгоритмы в науке
встречаются на каждом шагу; умение решать задачу «в общем виде» всегда
означает, по существу, владение некоторым алгоритмом. [1]
2. Исторический обзор
Первым
дошедшим до нас алгоритмом в его интуитивном понимании – конечной последовательности
элементарных действий, решающих поставленную задачу, считается предложенный
Евклидом в III веке до нашей эры алгоритм нахождения наибольшего общего
делителя двух чисел (алгоритм Евклида). Отметим, что в течение длительного
времени, вплоть до начала XX века само слово «алгоритм» употреблялось в
устойчивом сочетании «алгоритм Евклида». Для описания пошагового решения других
математических задач использовалось слово «метод».
Начальной
точкой отсчета современной теории алгоритмов можно считать работу немецкого
математика Курта Гёделя (1931 год - теорема о неполноте символических логик), в
которой было показано, что некоторые математические проблемы не могут быть
решены алгоритмами из некоторого класса. Общность результата Геделя связана с
тем, совпадает ли использованный им класс алгоритмов с классом всех (в
интуитивном смысле) алгоритмов. Эта работа дала толчок к поиску и анализу
различных формализаций алгоритма.
Первые
фундаментальные работы по теории алгоритмов были опубликованы независимо в 1936
году годы Аланом Тьюрингом, Алоизом Черчем и Эмилем Постом. Предложенные ими
машина Тьюринга, машина Поста и лямбда-исчисление Черча были эквивалентными
формализмами алгоритма. Сформулированные ими тезисы (Поста и Черча-Тьюринга)
постулировали эквивалентность предложенных ими формальных систем и интуитивного
понятия алгоритма. Важным развитием этих работ стала формулировка и
доказательство алгоритмически неразрешимых проблем.
В
1950-е годы существенный вклад в теорию алгоритмов внесли работы Колмогорова и
Маркова.
К
1960-70-ым годам оформились следующие направления в теории алгоритмов:
Классическая
теория алгоритмов (формулировка задач в терминах формальных
языков, понятие задачи разрешения, введение сложностных классов, формулировка в
1965 году Эдмондсом проблемы P=NP, открытие класса NP-полных задач и его
исследование) ;
Теория
асимптотического анализа алгоритмов (понятие сложности и
трудоёмкости алгоритма, критерии оценки алгоритмов, методы получения
асимптотических оценок, в частности для рекурсивных алгоритмов, асимптотический
анализ трудоемкости или времени выполнения), в развитие которой внесли
существенный вклад Кнут, Ахо, Хопкрофт, Ульман, Карп
Теория
практического анализа вычислительных алгоритмов (получение
явных функции трудоёмкости, интервальный анализ функций, практические критерии
качества алгоритмов, методика выбора рациональных алгоритмов), основополагающей
работой в этом направлении, очевидно, следует считать фундаментальный труд Д.
Кнута «Искусство программирования для ЭВМ» [2]
3. Цели и задачи теории алгоритмов.
Обобщая
результаты различных разделов теории алгоритмов можно выделить следующие цели и
соотнесенные с ними задачи, решаемые в теории алгоритмов:
формализация
понятия «алгоритм» и исследование формальных алгоритмических систем;формальное
доказательство алгоритмической неразрешимости ряда задач;классификация
задач, определение и исследование сложностных классов;асимптотический
анализ сложности алгоритмов;исследование
и анализ рекурсивных алгоритмов;получение
явных функций трудоемкости в целях сравнительного анализа алгоритмов;разработка
критериев сравнительной оценки качества алгоритмов;Развивать
алгоритмические и логические стили мышления;Сформулировать
представление о теоретической базе программирования.
Черты,
характерные для интуитивного понятия алгоритма :
Дискретность.
Это свойство заключается в следующем: в начальный момент задается исходная
система величин, а в каждый следующий момент система величин получается из
предыдущей системы величин по определенному закону (программе). Детерминированность.
Система величин, получаемых в любой, отличный от начального, момент времени,
однозначно определяется системой величин в предшествующие моменты времени. Элементарность
шагов. Закон получения последующей системы величин из предыдущей должен быть
простым и локальным. Эффективность
(результативность). Каждый шаг работы алгоритма должен заканчиваться
результатом. Массовость
алгоритма. Начальная система величин может выбираться из некоторого
бесконечного счетного множества Х. Конструктивность.
Объекты из Х, над которым работает алгоритм, должны быть конструктивными.[3]
4. Практическое применение результатов
теории алгоритмов
Полученные
в теории алгоритмов теоретические результаты находят достаточно широкое практическое
применение, при этом можно выделить следующие два аспекта:
Теоретический
аспект: при исследовании некоторой задачи результаты теории
алгоритмов позволяют ответить на вопрос – является ли эта задача в принципе
алгоритмически разрешимой – для алгоритмически неразрешимых задач возможно их
сведение к задаче останова машины Тьюринга. В случае алгоритмической
разрешимости задачи – следующий важный теоретический вопрос – это вопрос о
принадлежности этой задачи к классу NP–полных задач, при утвердительном ответе
на который, можно говорить о существенных временных затратах для получения
точного решения для больших размерностей исходных данных.
Практический
аспект: методы и методики теории алгоритмов (в основном разделов
асимптотического и практического анализа) позволяют осуществить:
рациональный
выбор из известного множества алгоритмов решения данной задачи с учетом
особенностей их применения (например, при ограничениях на размерность исходных
данных или объема дополнительной памяти);получение
временных оценок решения сложных задач;получение
достоверных оценок невозможности решения некоторой задачи за определенное
время, что важно для криптографических методов;разработку
и совершенствование эффективных алгоритмов решения задач в области обработки
информации на основе практического анализа.[4]
5. Формализация понятия алгоритма
Во всех
сферах своей деятельности, и частности в сфере обработки информации, человек
сталкивается с различными способами или методиками решения задач. Они
определяют порядок выполнения действий для получения желаемого результата – мы
можем трактовать это как первоначальное или интуитивное определение алгоритма.
Некоторые дополнительные требования приводят к неформальному определению
алгоритма:
Происхождение
слова "алгоритм" связано с алгоритмами десятичной позиционной
арифметики. Правила действий с натуральными числами, записанными в десятичной
системе счисления, были впервые найдены в средневековой Индии. Европейцы
изучали их по книге великого арабского ученого IX в, которого звали Мухаммед
ибн Муса аль-Хорезми, что буквально означает "Мухаммед, сын Мусы, уроженец
Хорезма" (заметим, что Аральское море тогда называлось "озером
Хорезм", а сам город Хорезм был расположен в бассейне реки Амударьи южнее
этого моря). Книга ученого "Китаб ал-хисаб ал-хинд" ("Книга об
индийском счете") послужила прототипом многих рукописей, составленных
европейцами уже на латинском языке. В них имя ученого- аль-Хорезми -
латинизировалось и стало звучать как "алхоризм",
"алгорифм" или "алгоритм". Этим словом стали называть сами
рукописи о десятичной арифметике и алгоритмы цифровых вычислений, а лишь затем
его стали использовать для обозначения произвольных алгоритмов.
Определение
1: Алгоритм - это заданное на некотором языке конечное предписание, задающее
конечную последовательность выполнимых элементарных операций для решения
задачи, общее для класса возможных исходных данных.
Пусть D
– область (множество) исходных данных задачи, а R – множество возможных
результатов, тогда мы можем говорить, что алгоритм осуществляет отображение D >
R. Поскольку такое отображение может быть не полным, то вводятся следующие
понятия:
Алгоритм
называется частичным алгоритмом, если мы получаем результат только для
некоторых d є D и полным алгоритмом, если алгоритм получает правильный
результат для всех d є D.
Несмотря
на усилия исследователей отсутствует одно исчерпывающе строгое определение
понятия алгоритм, в теории алгоритмов были введены различные формальные
определения алгоритма и удивительным научным результатом является
доказательство эквивалентности этих формальных определений в смысле их
равномощности.
Варианты
словесного определения алгоритма принадлежат российским ученым А.Н. Колмогорову
и А.А. Маркову :
Определение 2 (Колмогоров): Алгоритм – это
всякая система вычислений, выполняемых по строго определенным правилам, которая
после какого-либо числа шагов заведомо приводит к решению поставленной задачи.
Определение 3 (Марков): Алгоритм – это
точное предписание, определяющее вычислительный процесс, идущий от варьируемых
исходных данных к искомому результату.
Отметим,
что различные определения алгоритма, в явной или неявной форме, постулируют
следующий ряд требований:
алгоритм
должен содержать конечное количество элементарно выполнимых предписаний, т.е.
удовлетворять требованию конечности записи;алгоритм
должен выполнять конечное количество шагов при решении задачи, т.е.
удовлетворять требованию конечности действий;алгоритм
должен быть единым для всех допустимых исходных данных, т.е. удовлетворять
требованию универсальности;алгоритм
должен приводить к правильному по отношению к поставленной задаче решению, т.е.
удовлетворять требованию правильности.
Другие
формальные определения понятия алгоритма связаны с введением специальных
математических конструкций (машина Поста, машина Тьюринга,
рекурсивно-вычислимые функции Черча) и постулированием тезиса об эквивалентности
такого формализма и понятия «алгоритм». [5]
Список литературы:
1.http://do.gendocs.ru/docs/index-146244.html
2. http://studentick.com/docs/index-7057.html
3. http://turboreferat.ru/sport/celi-i-zadachi-teorii-algoritma/121309-623043-page1.html
4. http://th-algoritmov.narod.ru/1.htm
5.http://kafinf.pi.sfedu.ru/stud_materials/Tolstonozhenko_2011/формализация.html