Интуитивные определения алгоритма и данных.

Вводные замечания

Введение в теорию алгоритмов

Лекция 3

Литература

1. Попов В.Б. Паскаль и Дельфи. Самоучитель - СПб.: Питер, 2004. - 544 с.: ил. ISBN 5-8046-0156-3

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

1. Можно ли решить данную задачу с помощью ЭВМ?
2. Как заставить ЭВМ решать задачу?
3. Как быстро ЭВМ может решить задачу и какие потребуются ресурсы ЭВМ?
4. Как можно ускорить процесс решения задачи?

Чтобы получить точные ответы необходима математика. Чтобы использовать математику необходимо формализовать основные понятия: задачи; решения; построить математическую модель ЭВМ; ввести критерии качества решения.

С решением задачи на ЭВМ связаны два термина:
- программа
- алгоритм.

Определение. Под программой понимается информация конечного объема, которая, будучи введена в ЭВМ, приведет к решению компьютером задачи за конечное время.

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

Далее в лекции было небольшое отступление о языках программирования высокого и низкого уровней.

Если есть программа и математическая модель реальной ЭВМ, то можно провести полный анализ характеристик вычислительного процесса:
- времени работы программы для различных входных данных;

- требуемого объема памяти (оперативной и дисковой);

- доказать, что программа действительно решает поставленную задачу, а не какую-то другую (доказать правильность программы).
- исследовать другие проблемы.

Анализ на основе программы имеет некоторые недостатки:

1. Результат зависит и от задачи, и от конкретного типа ЭВМ. Следовательно, нет переносимости результатов анализа на другие ЭВМ.
2. Анализ избыточен: может интересовать ответ на простой вопрос или с невысокой точностью.

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

Например, при составлении математической модели ЭВМ, очевидно, что не надо учитывать ее цвет и внешний вид, но можно ввести и другие допущения:
- считать одинаковой длительность элементарных операций,

- считать, что память имеет неограниченный объем.

Определение №1. Алгоритм является математической формализацией программы.

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

Термин «алгоритм» близок к словам «процесс», «рецепт», «метод», «способ», но имеет дополнительный смысловой оттенок, уточняемый свойствами алгоритма.