Галилей Модуль 2. Основы теории алгоритмов (1,5 кредита) Комплексная цель и задачи изучения модуля
Цель Модуля 2 – дать представление о фундаментальных понятиях, базовых принципах и законах таких важных разделов дискретной математики как теория алгоритмов и алгебра логики, рассмотреть постановку основных задач и проблем, изучить вопросы методологии решаемой проблемы.
В результате освоения Модуля 2 студент должен быть готов продемонстрировать следующие компетенции и уровень подготовки:
знание основных понятий теории алгоритмов;
умение оценивать и определять временную сложность алгоритмов;
знание основных алгоритмических моделей и умение их самостоятельно строить;
навыки решения практических задач оптимизации, умение представить решаемую конкретную практическую задачу в виде алгоритмической модели, пригодной для дальнейшего формального решения на основе существующих языков программирования средствами вычислительной техники.
Самостоятельная работа предусматривает проработку лекций (1,2 часа в неделю), тестирование, а также изучение литературы, формулировку цели работы, объекта и задач исследования, методов, источников и средств библиографического поиска, использованных для достижения поставленной цели.
Модуль включает в себя формулировку цели, проблемное изложение программного лекционного материала, тестовые вопросы для самоконтроля и список литературы. В процессе самостоятельного изучения представленных методических материалов происходит формирование указанных компетенций.
Глава 9. Введение в теорию алгоритмов
Алгоритмы, определение и основные понятия алгоритмов, свойства алгоритмов, классификация алгоритмов
ЦЕЛИ
Освоив эту главу, учащиеся должны уметь и знать:
определение и основные понятия алгоритмов;
основные свойства алгоритмов;
основные виды алгоритмов;
строить схемы алгоритмов.
9.1. Понятие алгоритма
Понятие «алгоритм» давно стало привычным для специалистов различных отраслей науки и техники. Оно является концептуальной основой разнообразных процессов обработки информации. Наличие соответствующих алгоритмов обеспечивает возможность автоматизации любой деятельности человека. Термин «алгоритм» обязан своим происхождением ученому средневекового Востока, который жил приблизительно с 783 по 850 гг., чье имя – Мухаммад ибн Мусса аль-Хорезми, причем «аль-Хорезми», означает «происхождением из Хорезма». В латинских названиях, составленных в XVII веке, при изложении трудов аль-Хорезми его имя переводилось как алхоритм или алгоритм. Отсюда и пошло понятие «алгоритм», которое сначала использовалось для обозначения десятичной позиционной арифметики и алгоритмов цифровых вычислений (т.е. первых алгоритмических процедур, имеющих дело с символами), а затем для обозначения произвольных алгоритмов.
Дональд Эрвин Кнут в первой главе своей многотомной монографии «Искусство программирования» писал: «Понятие алгоритма является основным при составлении любого вида программ для ЭВМ… Современное значение слова «алгоритм» во многом аналогично таким понятиям, как рецепт, процесс, метод, способ, процедура, программа, но все-таки слово алгоритм имеет дополнительный смысловой оттенок. Алгоритм - это не просто набор конечного числа правил, задающих последовательность выполнения операций для решения задачи определенного типа. Помимо этого он имеет пять важных особенностей:
1) Конечность. Алгоритм всегда должен заканчиваться после выполнения конечного числа шагов.
2) Определенность. Каждый шаг алгоритма должен быть точно определен.
3) Ввод. Алгоритм имеет некоторое число входных данных, т.е. величин, которые задаются до начала его работы.
4) Вывод. У алгоритма есть одно или несколько выходных данных, т.е. величин, имеющих вполне определенную связь с входными данными.
5) Эффективность. Алгоритм считается эффективным, если все его операции можно точно выполнить в течение конечного промежутка времени».
Понятие алгоритма является не только центральным понятием теории алгоритмов, не только одним из главных понятий математики вообще, но одним из главных понятий современной науки.
Однозначного и точного определения алгоритма не существует. В связи с этим приведем несколько наиболее распространенных определений понятия алгоритм.
Алгоритм (algorithm) – это формально описанная вычислительная процедура, получающая исходные данные, называемые также входом алгоритма или его аргументом и выдающая результат вычисления на выход.
Алгоритм - это набор правил, указывающих определенные действия, в результате которых входные данные преобразуются в выходные. Последовательность действий в алгоритме называется алгоритмическим процессом, а каждое отдельное действие - шагом алгоритма.
Понятие алгоритма также можно интуитивно определить как конечную последовательность точно заданных правил решения произвольного класса задач.
Интуиция — это знание, полученное на основе опыта, но не подвергнутое научному анализу.
К алгоритмам не относятся запрещающие и разрешающие правила. Например: “Не курить! Не сорить!”
Особенность алгоритмов — это дискретный характер процесса, определяемого самим алгоритмом.
Алгоритмы строятся для решения тех или иных вычислительных задач. Формулировка задачи описывает, каким требованиям должно удовлетворять решение задачи, а алгоритм, решающий эту задачу, находит объект, удовлетворяющий этим требованиям. Алгоритм обычно имеет дело с тремя типами данных:
входные (исходные) данные;
промежуточные данные;
выходные данные.
Алгоритмы, в которых решения поставленных задач сводятся к арифметическим действиям, называются численными алгоритмами.
В некоторых случаях алгоритмы представляют в виде виртуального устройства, называемого “черным ящиком” (рис. 9.1).
Рис. 9.1. Представление алгоритма
Особенность «черного ящика» в том, что он осуществляет переработку информации, но при этом неизвестно, каким способом. Другими словами, на одинаковый набор исходных данных «черный ящик» должен выдавать одинаковые выходные результаты.
Для размещения данных алгоритма требуется память. В теоретическом плане считают, что память состоит из одинаковых ячеек, причем каждая ячейка памяти может содержать один или несколько символов данных.
В существующих в настоящее время алгоритмах последовательность выполняемых элементарных шагов детерминирована, т.е. после каждого шага алгоритма указывается номер следующего шага. От каждого алгоритма требуется остановка после конечного числа шагов, дающих требуемый результат. Различают описание алгоритмов и процесс их реализации.
Алгоритм считают правильным, если на любом допустимом (для данной задачи) входе он заканчивает работу и выдает результат, удовлетворяющий требованиям задачи. В этом случае говорят, что алгоритм решает данную вычислительную задачу. Неправильный алгоритм может (для некоторого входа) не остановиться или дать неправильный результат.
Алгоритм может быть записан на любом естественном или формальном языке, а также в виде компьютерной программы или в машинных кодах. При этом важно, чтобы процедура вычислений была четко описана. Алгоритмы также могут записываться с помощью псевдокода, который представляет симбиоз из основных операторов различных языков программирования. Разница в том, что в псевдокоде могут использоваться не только эти операторы, но и словесное описание действий алгоритма, а также отсутствуют технологические подробности (например, процедура обработки ошибок), имеющиеся в реальной программе. Примером алгоритма может являться книга кулинарных рецептов, инструкция по эксплуатации прибора, стандарты проектирования космических кораблей и др.