тематических задач использовалось слово метод.html
Работа добавлена на сайт samzan.net:
ВВЕДЕНИЕ В ТЕОРИЮ АЛГОРИТМОВ
- Исторический обзор
Первым дошедшим до нас алгоритмом в его интуитивном понимании –конечной последовательности элементарных действий, решающих поставлен-ную задачу, считается предложенный Евклидом в III веке до нашей эры алгоритм нахождения наибольшего общего делителя двух чисел (алгоритм Евклида). Отметим, что в течение длительного времени, вплоть до начала XX века само слово «алгоритм» употреблялось в устойчивом сочетании «алгоритм Евклида». Для описания пошагового решения других математических задач использовалось слово «метод».
Начальной точкой отсчета современной теории алгоритмов можно считать работу немецкого математика Курта Гёделя (1931 год - теорема о неполноте символических логик), в которой было показано, что некоторые математические проблемы не могут быть решены алгоритмами из некоторого класса. Общность результата Геделя связана с тем, совпадает ли использованный им класс алгоритмов с классом всех (в интуитивном смысле) алгоритмов. Эта работа дала толчок к поиску и анализу различных формализаций алгоритма.
Первые фундаментальные работы по теории алгоритмов были опубликованы независимо в 1936 году годы Аланом Тьюрингом, Алоизом Черчем и Эмилем Постом. Предложенные ими машина Тьюринга, машина Поста и лямбда-исчисление Черча были эквивалентными формализмами алгоритма. Сформулированные ими тезисы (Поста и Черча-Тьюринга) постулировали эквивалентность предложенных ими формальных систем и интуитивного понятия алгоритма. Важным развитием этих работ стала формулировка и доказательство алгоритмически неразрешимых проблем.
В 1950-е годы существенный вклад в теорию алгоритмов внесли работы Колмогорова и Маркова.
К 1960-70-ым годам оформились следующие направления в теории алго-ритмов:
- Классическая теория алгоритмов (формулировка задач в терминах формальных языков, понятие задачи разрешения, введение сложностных классов, формулировка в 1965 году Эдмондсом проблемы P=NP, открытие класса NP-полных задач и его исследование);
- Теория асимптотического анализа алгоритмов (понятие сложности и трудоёмкости алгоритма, критерии оценки алгоритмов, методы получения асимптотических оценок, в частности для рекурсивных алгоритмов, асимптотический анализ трудоемкости или времени выполнения), в развитие которой внесли существенный вклад Кнут, Ахо, Хопкрофт, Ульман, Карп;
- Теория практического анализа вычислительных алгоритмов (получение явных функции трудоёмкости, интервальный анализ функций, практические критерии качества алгоритмов, методика выбора рациональных алгоритмов), основополагающей работой в этом направлении, очевидно, следует считать фундаментальный труд Д. Кнута «Искусство программирования для ЭВМ».
- Цели и задачи теории алгоритмов
Обобщая результаты различных разделов теории алгоритмов можно выделить следующие цели и соотнесенные с ними задачи, решаемые в теории алгоритмов:
- формализация понятия «алгоритм» и исследование формальных алгоритмических систем;
- формальное доказательство алгоритмической неразрешимости ряда задач;
- классификация задач, определение и исследование сложностных классов;
- асимптотический анализ сложности алгоритмов;
- исследование и анализ рекурсивных алгоритмов;
- получение явных функций трудоемкости в целях сравнительного анализа алгоритмов;
- разработка критериев сравнительной оценки качества алгоритмов.
- Практическое применение результатов теории алгоритмов
Полученные в теории алгоритмов теоретические результаты находят достаточно широкое практическое применение, при этом можно выделить следующие два аспекта:
Теоретический аспект: при исследовании некоторой задачи результаты теории алгоритмов позволяют ответить на вопрос –является ли эта задача в принципе алгоритмически разрешимой –для алгоритмически неразрешимых задач возможно их сведение к задаче останова машины Тьюринга. В случае алгоритмической разрешимости задачи –следующий важный теоретический вопрос –это вопрос о принадлежности этой задачи к классу NP–полных задач, при утвердительном ответе на который, можно говорить о существенных временных затратах для получения точного решения для больших размерностей исходных данных.
Практический аспект: методы и методики теории алгоритмов (в основ-ном разделов асимптотического и практического анализа) позволяют осуществить:
- рациональный выбор из известного множества алгоритмов решения данной задачи с учетом особенностей их применения (например, при ограничениях на размерность исходных данных или объема дополнительной памяти);
- получение временных оценок решения сложных задач;
- получение достоверных оценок невозможности решения некоторой задачи за определенное время, что важно для криптографических методов;
- разработку и совершенствование эффективных алгоритмов решения задач в области обработки информации на основе практического анализа.
- Формализация понятия алгоритма
Во всех сферах своей деятельности, и частности в сфере обработки информации, человек сталкивается с различными способами или методиками решения задач. Они определяют порядок выполнения действий для получения желаемого результата –мы можем трактовать это как первоначальное или интуитивное определение алгоритма. Некоторые дополнительные требования приводят к неформальному определению алгоритма:
Определение 1.1 Алгоритм - это заданное на некотором языке конечное предписание, задающее конечную последовательность выполнимых элементарных операций для решения задачи, общее для класса возможных исходных данных.
Пусть D –область (множество) исходных данных задачи, а R –множест-во возможных результатов, тогда мы можем говорить, что алгоритм осуществ-ляет отображение D --> R. Поскольку такое отображение может быть не полным, то вводятся следующие понятия:
Алгоритм называется частичным алгоритмом, если мы получаем результат только для некоторых d є D и полным алгоритмом, если алгоритм получает правильный результат для всех d є D.
Несмотря на усилия исследователей отсутствует одно исчерпывающе строгое определение понятия алгоритм, в теории алгоритмов были введены различные формальные определения алгоритма и удивительным научным результатом является доказательство эквивалентности этих формальных определений в смысле их равномощности.
Варианты словесного определения алгоритма принадлежат российским ученым А.Н. Колмогорову и А.А. Маркову
Определение 1.2 (Колмогоров): Алгоритм –это всякая система вычис-лений, выполняемых по строго определенным правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи.
Определение 1.3 (Марков): Алгоритм –это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату.
Отметим, что различные определения алгоритма, в явной или неявной форме, постулируют следующий ряд требований:
- алгоритм должен содержать конечное количество элементарно выполнимых предписаний, т.е. удовлетворять требованию конечности записи;
- алгоритм должен выполнять конечное количество шагов при решении задачи, т.е. удовлетворять требованию конечности действий;
- алгоритм должен быть единым для всех допустимых исходных данных, т.е. удовлетворять требованию универсальности;
- алгоритм должен приводить к правильному по отношению к поставленной задаче решению, т.е. удовлетворять требованию правильности.
Другие формальные определения понятия алгоритма связаны с введением специальных математических конструкций (машина Поста, машина Тьюринга, рекурсивно-вычислимые функции Черча) и постулированием тезиса об эквивалентности такого формализма и понятия «алгоритм».
2. бешенная пчелка и т
3. Строительство и наладка системы обеззараживания питьевой воды
4. на тему- Модели имиджа организации и лидера Подготовила студентка 4 курса 1 группы очнозаочного
5. ТЕМА Массовые праздники как форма организации досуга населения на примере Масленицы
6. Российская система образования
7. . Паевые инвестиционные фонды понятие и сущность4 1
8. Тема- ВАЛЮТНІ КУРСИ
9. Язык телодвижений как читать мысли по жестам
10. Педагогические условия формирования умений учебной деятельности младших школьников
11. ТЕМА 2. ФІНАНСОВЕ ПРАВО ЯК ГАЛУЗЬ ПРАВА лекції 2 години практичні заняття 1 година самостійна робота 2 го
12. Сельский батюшка Обычно хотя бы несколько дней своего долгожданного отпуска я провожу на своей малой
13. темах конкуренции образа объекта идеи товара услуги персоналии организации фирмы бренда в ценностный
14. Реферат- Информационное общество и право
15. РЕФЕРАТ дисертації на здобуття наукового ступеня кандидата географічних наук Одеса ~ Дисерт
16. Кубань
17. Применение методов нейро-лингвистического программирования в обучении
18. ТЕМА 6. ФИЛОСОФСКОЕ ПОНИМАНИЕ СОЗНАНИЯ Понятие и структура сознания.html
19. Анализ актуального употребления категорий вежливости японского языка
20. Ионный обмен