Свойства алгоритма
Определение алгоритма
Информационные модели.
Информационная модель- это совокупность информации об объекте, описывающая свойства и состояние объекта, процесса или явления, а также связи и отношения с окружающим миром.
Информационные модели представляют объекты в виде словесных описаний, текстов, рисунков, таблиц, схем, чертежей, формул и т.д. Информационную модель нельзя потрогать, у нее нет материального воплощения, она строится только на информации. Ее можно выразить на языке описания (знаковая модель) или языке представления (наглядная модель). Информационные модели во многих случаях опираются на математические модели, так как при решении задач математическая модель исследуемого объекта, процесса или явления неизбежно преобразуется в информационную для её реализации на компьютере.
Информационным объектом называется описание реального объекта, процесса или явления в виде совокупности его характеристик (информационных элементов), называемых реквизитами.
Информационный объект определённой структуры (реквизитного состава) образует тип (класс), которому присваивают уникальное имя.
Информационный объект с конкретными характеристиками называют экземпляром. Каждый экземпляр идентифицируется заданием ключевого реквизита (ключа). Одни и те же реквизиты в различных информационных объектах могут быть как ключевыми, так и описательными. Информационный объект может иметь несколько ключей.
Единого «истинного» определения понятия «алгоритм» нет.
«Алгоритм —это последовательность действий, направленных на получение определённого результата за конечное число шагов».
«Алгоритм— точное предписание о выполнении в определённом порядке некоторой системы операций, ведущих к решению всех задач данного типа».
«Алгоритм— это последовательность действий, либо приводящая к решению задачи, либо поясняющая почему это решение получить нельзя».
«Алгоритм— это точное предписание, которое задаёт вычислительный (алгоритмический) процесс, начинающийся с произвольного исходного данного и направленный на получение полностью определяемым этим исходным данным результата».
Различные определения алгоритма в явной или неявной форме содержат следующий ряд общих требований:
1. Дискретность— алгоритм должен представлять процесс решения задачи как последовательное выполнение некоторых простых шагов. При этом для выполнения каждого шага алгоритма требуется конечный отрезок времени, то есть преобразование исходных данных в результат осуществляется во времени дискретно.
2. Детерминированность— определённость. В каждый момент времени следующий шаг работы однозначно определяется состоянием системы. Таким образом, алгоритм выдаёт один и тот же результат (ответ) для одних и тех же исходных данных. В современной трактовке у разных реализаций одного и того же алгоритма должен быть изоморфный граф. С другой стороны, существуют вероятностные алгоритмы, в которых следующий шаг работы зависит от текущего состояния системы и генерируемого случайного числа. Однако при включении метода генерации случайных чисел в список «исходных данных», вероятностный алгоритм становится подвидом обычного.
3. Понятность— алгоритм для исполнителя должен включать только те команды, которые ему (исполнителю) доступны, которые входят в его систему команд.
4. Конечность— при корректно заданных исходных данных алгоритм должен завершать работу и выдавать результат за конечное число шагов. С другой стороны, вероятностный алгоритм может и никогда не выдать результат, но вероятность этого равна 0.
5. Массовость— алгоритм должен быть применим к разным наборам исходных данных.
6. Результативность— завершение алгоритма определёнными результатами.
7. Алгоритм содержит ошибки, если приводит к получению неправильных результатов либо не даёт результатов вовсе.
8. Алгоритм не содержит ошибок, если он даёт правильные результаты для любых допустимых исходных данных