Алгоритмы и программы

 

    Глава 1. Алгоритмы и программы

    1.1 История развития  теории алгоритмов. 

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

    Математическая логика – это наука о правилах формального логического мышления.

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

    

 
 
 
 
 
 

      Возникновение понятия «алгоритм» связано с именем узбекского математика Маххамада ибн Мусса Аль-Хорезми (IX в.), который сформулировал правила умножения и деления чисел в десятичной системе счисления. В латинских переводах с арабского языка его имя записывалось как algorismi. В дальнейшем термин алгоритм использовался для обозначения произвольных процессов, в которых искомые величины решаемых задач находятся последовательно из исходных данных по определённым правилам.

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

    В 1936 году английский ученый Тьюринг  разработал модель вычислительной машины для решения задач на основе алгоритмов и доказал:

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

    На  основе этой модели («машина Тьюринга») была построена классическая теория алгоритмов, основу которой составляли формальные описания следующих понятий:

1 – алгоритм;

2 – алгоритмический  процесс;

3 – взаимосвязь  между алгоритмом и алгоритмическим процессом и др. 

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

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

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

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

    1.2 Основные понятия, определения и задачи теории алгоритмов.

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

    Таким образом, алгоритмы являются:

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

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

1.2.1. Понятие алгоритма.

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

    1 – интуитивное определение;

    2 – формальное определение.

    1. Алгоритм в интуитивном смысле – это точное предписание о выполнении в определенном порядке некоторой последовательности операций для решения всех задач некоторого заданного типа.

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

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

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

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

    Алгоритм  характеризуется:

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

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

• язык;
• понятность;
• точность

    интуитивные понятия,

    смысл которых ясен, а научные 

    определения не составлены. 

1.2.2 Алгоритмический процесс.

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

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

    Алгоритмический процесс состоит из конечного  числа шагов, каждый из которых является простым и выполняется за конечное время. Число шагов алгоритмического процесса связано с количеством времени S(t), затрачиваемого на их выполнение, а в ряде случаев и расходом других ресурсов.

1.2.3 Основные вопросы теории алгоритмов.

    Основные  вопросы теории алгоритмов можно  сформулировать следующим образом:

1. Что может делать ЭВМ.
2. Каким образом ЭВМ решает задачи.
3. Существует ли для заданной задачи эффективный алгоритм решения.
4. Как сравнить различные алгоритмы решения одной и той же задачи.

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

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

    2) Ответ на второй вопрос требует рассмотрения принципов работы ЭВМ и организации вычислительных процессов для различных структур ЭВМ в рамках их классификации, а также оценки качества алгоритмов, реализуемых в различных ЭВМ.

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

    4) Для сравнения различных алгоритмов по быстродействию необходимо рассмотреть следующие параметры:

• временная функция T(N);
• функция сложности алгоритма O(g(N)), учитывающая зависимость скорости роста числа шагов алгоритма от объема исходных данных.

    1.3 Алгоритмы и языки.

    Как уже отмечалось, алгоритм – это правило, а любое правило должно быть четко сформулировано на каком-либо языке (1).  Это возможно лишь при условии, что исходные данные и искомые результаты могут быть описаны в полном объеме на каком-либо другом языке (2). Т. е. каждому исходному данному, промежуточному и конечному результатам соответствует некоторое предложение на этом языке. Смысл предложения должен быть однозначным.

    Язык (1) – это язык описания алгоритмов (алгоритмический язык).

    Язык (2) – это язык описания данных (язык операндов).

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

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

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

    1.4. Способы записи алгоритмов

     Существуют различные формы (способы)  представления алгоритмов. Основными  среди них являются:

1. Словесное описание алгоритма на естественном языке (вербальная форма).
2. Построчная запись алгоритма (более строгое описание на естественном языке).
3. Представление алгоритма в виде блок-схемы.
4. Способ изображения алгоритма с помощью структурограммы (схема Насси-Шнейдермана).
5. Запись алгоритма на каком-либо языке программирования.

  Пример: Найти наибольший общий делитель (НОД) двух целых положительных чисел методом последовательного вычитания (алгоритм Евклида).

  Вербальное представление  алгоритма. 

     «Чтобы найти НОД двух целых положительных чисел составим таблицу из двух столбцов и назовем их m и n. Запишем первое из заданных чисел в столбец m, а второе - в столбец n. Если данные числа не равны, заменим большее из них результатом вычитания из большего меньшего числа. Повторяем такие замены до тех пор, пока числа не окажутся равными, после чего число из столбца m считаем искомым результатом». Очевидно, такая форма представления алгоритма может тяжело восприниматься читателем и применяется в основном при решении простых задач.

  Построчная запись  алгоритма.

1. Начало.
2. Ввод m, n.
3. Если m¹n, перейти к пункту 4, иначе - к пункту 7.
4. Если m>n, перейти к пункту 5, иначе - к пункту 6.
5. m=m-n; перейти к пункту 3.
6. n=n-m; перейти к пункту 3.
7. НОД=m.
8. Вывод результата.
9. Конец.