Введение. Определения алгоритма

Лекция 1. ВВЕДЕНИЕ. ОПРЕДЕЛЕНИЯ АЛГОРИТМА

План:

Цели и задачи дисициплины «Алгоритмы и их сложность». Предмет дисциплины. Определения алгоритма и основные требования к алгоритмам.  Понятие о сложности и эффективности алгоритма. Методы анализа алгоритмов.  (1 час).

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

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

Некоторые определения алгоритма:

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

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

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

1.2. Основные требования, предъявляемые к алгоритмам. Алгоритм должен удовлетворять следующим требованиям:

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

2. Данные для своего размещения требуют память. Память обычно считается дискретной. Единицы измерения памяти и данных должны быть согласованы между собой.

3. Алгоритм состоит из отдельных элементарных шагов (действий). Множество шагов  алгоритма конечно.

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

5, Каждый алгоритм должен быть результативным, т.е. после конечного числа  шагов выдавать результат.

6. Необходимо различать: описание алгоритма (инструкция или программа), механизм реализации – устройство (ЭВМ), процесс реализации алгоритма.

Для исследования понятия алгоритма используются алгоритмические модели, такие как машина Тьюринга, частично-рекурсивные функции, машина Колмогорова, нормальные алгорифмы Марков, канонические системы Поста и другие.

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