Шаповалов / lex_1_1

Тема № 1. ВВЕДЕНИЕ. СТРУКТУРА И ЗАДАЧИ КУРСА. МЕСТО ДИСЦИПЛИНЫ СРЕДИ ИНФОРМАЦИОННЫХ ИССЛЕДОВАНИЙ. АЛГОРИТМЫ И ИХ РОЛЬ В

ИНФОРМАТИКЕ. СВОЙСТВА И ПРИНЦИПЫ АНАЛИЗА

А есть ли алгоритм любви?

( вопрос на засыпку…)

Понятие « Алгоритм » - концептуальная основа разнообразных процессов обработки информации. Именно наличие соответствующих алгоритмов и обеспечивает возможность автоматизации. Вместе с математической логикой теория алгоритмов образует теоретический фундамент современных вычислительных наук. Более того, в значительной степени через теорию алгоритмов происходит ныне проникновение математических методов в биологию, лингвистику, экономику вплоть до философии естествознания [1-12].

Авторы обзора основных достижений теории алгоритмов [4] утверждают:

"Алгоритмические концепции играют в процессе обучения и воспитания современного человека фундаментальную роль, сравнимую лишь с ролью письменности".

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

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

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

На одной из научных конференций ( 1984 г.) по информатике академик Самарский изобразил на слайде информатику в виде красавицы, несущейся на трех китах по научному океану. Имена тех китов : Модель, Алгоритм, Программа.

Мы займемся как раз вторым китом имя которого – Алгоритм! Тем более что агитировать Вас им заняться не вызывает я думаю возражений…Ибо алгоритм, бесспорно, центральное понятие для программирования! С него начинается по сути робота над программой,

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

История у его величества Алгоритма очень длинная, а вот у теории алгоритмов сравнительно короткая. Теория алгоритмов, пожалуй, как раздел научных знаний начал оформляться лишь с конца 30-х годов 20 века и до наших дней…процесс продолжается.

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

Слово Алгоритм, как утверждают историки, математики, появилось 12 веков назад и означало не термин, а имя. Узбекский математик Аль-Хорезми , ученый которому математика обязана многими открытиями, - был известен европейским математикам как Алгоризми. А полное его имя Абу Абд Аллах Мухаммед ибн Мусса аль-Хорезми ( около 825 г. ) – в переводе буквально – Отец Абдуллы, Мухаммед, сын Мусы, уроженец Хорезми. Его книга – «Китаб аль-джебр Валь-мукабала». Именно с трактата Аль-Хорезми по арифметике началось знакомство Европы с алгоритмами – строгими процедурами для выполнения арифметических операций. Т.е. алгоритм…вернее как алгорисм – понимался как руководство к действию для решения задач.

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

Для уточнения понятия алгоритм были распространены 2 точки зрения :

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

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

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

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

В 1950-е годы существенный вклад в теорию алгоритмов внесли работы Колмогорова и Маркова. К 1960-70-ым годам оформились следующие направления в теории алгоритмов:

• Классическая теория алгоритмов (формулировка задач в терминах формальных языков, понятие задачи разрешения, введение сложностных классов, формулировка в 1965 году Эдмондсом проблемы P=NP, открытие класса NP-полных задач и его исследование)[1];

• Теория асимптотического анализа алгоритмов (понятие сложности и трудоёмкости алгоритма, критерии оценки алгоритмов, методы получения асимптотических оценок, в частности для рекурсивных алгоритмов, асимптотический анализ трудоемкости или времени выполнения), в развитие которой внесли существенный вклад Кнут, Ахо, Хопкрофт, Ульман, Карп[2,4];

• Теория практического анализа вычислительных алгоритмов (получение явных функции трудоёмкости, интервальный анализ функций, практические критерии качества алгоритмов, методика выбора рациональных алгоритмов), основополагающими работами в этом направлении, очевидно, следует считать фундаментальные труды[1,2].

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

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

Пусть D – область (множество) исходных данных задачи, а R – множество возможных результатов, тогда мы можем говорить, что алгоритм осуществляет отображение D → R.

Вот еще два определения алгоритма известных ученых:

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

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

Алгоритм – это не роман для чтения… Форма записи – это не выполнение самого алгоритма. Чтобы проверить алгоритм, нужно в нем разобраться, и лучший способ понять, как он работает, - испытать его. Поэтому предлагаю вам взять карандаш, бумажку и проработать от начала и до конца каждый алгоритм сразу же, как встречается…

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

1. Детерминированность ( определенность) – однозначность результата процесса при заданных исходных данных.

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

3. Массовость – алгоритм может быть использован для решения целого класса задач одного типа, например решения квадратного уравнения c различными коэффициентами ( те исходные данные алгоритма можно выбрать из некоторого множества данных ( потенциально бесконечного).

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

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

Развитие теории алгоритмов сталкивается с трудностью, вызванной тем, что алгоритмы сами по себе суть объекты весьма специфичного типа и обладают свойством, нетипичным для математических объектов, а именно семантическим свойством « иметь смысл». В этом отношении теория алгоритмов подобна математической логике, чьи теоремы и формулы также имеют смысл. Смысл терма или формулы «указателен» : терм указывает на (т.е. обозначает ) вещь, а формула – на факт. Смысл алгоритма «повелителен» : алгоритм должен быть исполнен. Таким образом, теория, изучающая алгоритмы, может трактоваться как своего рода лингвистика повелительных предложений. Математики еще не привыкли обращаться надлежащим образом с лингвистическими объектами, несущими на себе смысл. Поэтому при создании адекватной теории алгоритмов направляющую роль должна играть семантика, чисто математических подход для этой цели недостаточен ( если считать, что чисто математический подход не должен использовать – в качестве технического понятия – понятия смысла) . В теорию алгоритмов входит на равных правах с понятием алгоритма, еще и понятие исчисления. Подобно термам, формулам и алгоритмам, исчисления также являются носителями смысла: однако смысл их не указателен и не повелителен, а разрешителен. Поэтому теорию алгоритмов, как дисциплину, что сложилась к настоящему времени было бы правильнее именовать теорией алгоритмов и исчислений [4].

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

Обобщая результаты различных разделов теории алгоритмов можно выделить следующие цели и соотнесенные с ними задачи, решаемые в теории алгоритмов [1-10]:

• формализация понятия «алгоритм» и исследование формальных алгоритмических систем;

• формальное доказательство алгоритмической неразрешимости ряда задач;

• классификация задач, определение и исследование сложностных классов;

• асимптотический анализ сложности алгоритмов;

• исследование и анализ рекурсивных алгоритмов;

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

• разработка критериев сравнительной оценки качества алгоритмов.

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

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

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

• рациональный выбор из известного множества алгоритмов решения данной задачи с учетом особенностей их применения (например, при ограничениях на размерность исходных данных или объема дополнительной памяти);

• получение временных оценок решения сложных задач;

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

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