5.1. Определение и свойства алгоритмов
Понятие алгоритма относится к числу основных понятий информатики. В течение длительного времени его употребляли только математики, понимая под алгоритмом правило решения задач некоторого класса.
С появлением ЭВМ оно получило очень широкую известность. Постоянное расширение области применения вычислительной техники, великие перспективы использования компьютеров для решения самых разнообразных проблем привели к становлению новой самостоятельной науки – теории алгоритмов. Разумеется, приведенная формулировка не претендует на роль точного определения понятия алгоритм, она лишь поясняет его смысл, выражая то интуитивное воззрение, которое сложилось еще в древности.
Термин «алгоритм» содержит преобразованное географическое название древнего государства в Средней Азии – Хорезм, родины человека по имени Мухаммед ибн Муса аль-Хорезми, ориентировочные годы жизни которого – 783-850. Его труды, переведенные в XII в. с арабского на латинский язык, познакомили европейцев с десятичной позиционной системой счисления и с правилами выполнения четырех арифметических действий над многозначными числами. Формальный характер этих элементарных операций, которые всеми и всегда выполняются одинаково при полном отвлечении от содержательного смысла операндов, означает, что они могут быть автоматизированы. А имя самого ученого в латинизированной транскрипции Algorithmi со временем превратилось в общее название однозначно трактуемой процедуры решения задачи, достижения поставленной цели.
Формирование строгого научного определения алгоритма не закончено и в настоящее время. Современное интуитивное представление алгоритма рассматривается ниже.
Алгоритм – это конечная последовательность понятных и точных предписаний исполнителю выполнить конечную цепочку действий, приводящих от допустимых исходных данных к искомому результату.
Такая цепочка действий называется алгоритмическим процессом, а каждое действие – шагом или операцией.
Нестрогость интуитивного понятия алгоритма заключена, прежде всего, в научной неточности тех терминов, в которых оно выражено, в частности таких слов, как «понятность» и «точность».
Отметим основные свойства, присущие любому алгоритму.
1. Дискретность алгоритма. Описываемый алгоритмом процесс должен быть разбит на конечное число отдельных указаний, четко отделенных друг от друга конечным ненулевым промежутком времени. Только выполнив требования одной инструкции, можно перейти к следующей.
2. Понятность алгоритма. Алгоритм составляется с ориентацией на определенного исполнителя. У каждого исполнителя имеется свой перечень допустимых предписаний, которые этот исполнитель понимает и может выполнить. Этот перечень называется системой команд исполнителя (СКИ). Алгоритм должен включать в себя только те предписания, которые входят в СКИ.
3. Элементарность шагов алгоритма. Простейшие (основные, натуральные) операции, выполняемые в соответствии с требованиями алгоритма, зависят лишь от характеристик исполнителя, но не от исходных данных и промежуточных результатов. Например, сравнение в ЭВМ двух чисел, выполнение арифметических операций и т.п., но не сравнение двух файлов, потенциальная длина которых не ограничена.
4. Точность (однозначность, определенность, детерминированность) алгоритма. Формулировка алгоритма полностью определяет все действия исполнителя, у которого никогда не должна возникать потребность в принятии самостоятельных решений, не предусмотренных составителем алгоритма. Применяя алгоритм к одним и тем же исходным данным несколько раз, исполнитель получает одну и ту же цепочку промежуточных результатов на каждом шаге и, соответственно, один и тот же окончательный результат. Результаты не должны зависеть ни от каких случайных факторов.
5. Массовость алгоритма. Для каждого алгоритма существует некоторый класс объектов (предметов, чисел и т.д.) и все они (а не какое–то их количество, конечное, бесконечное или равное нулю) допустимы в качестве исходных данных. Точное выполнение алгоритма возможно лишь при условии, что исходные данные поддаются исчерпывающему описанию на некотором языке.
6. Конечность (сходимость, результативность, финитность) алгоритма. Алгоритмический процесс должен оканчиваться через конечное число шагов, на каждом шаге не должно возникать препятствий для его выполнения, и после остановки можно получить искомый результат. Это требование не учитывает реальных ограничений, связанных с затратами времени и расходованием других ресурсов до завершения алгоритмического процесса за конечное (но заранее неизвестное) число шагов. Поэтому конечность означает лишь потенциальную осуществимость алгоритма, хотя на практике, конечно, всегда требуется реальная его выполнимость.
О некоторой ограниченности приведенного интуитивного понятия алгоритма свидетельствует тот факт, что существуют программы для ЭВМ, которые могут заканчиваться без получения результата или даже не заканчиваться при некоторых исходных данных. Пример – функционирование операционной системы компьютера: алгоритмы работы каждого ее компонента, их взаимодействия четко определены, включают конечное число действий, но операционная система не предполагает «самостоятельной» остановки и выдачи результатов. Еще одним примером «бесконечных» алгоритмов являются алгоритмы работы встроенных вычислительных систем, управляющих технологическими процессами с непрерывным циклом. Однако ограниченная трактовка – это как раз то, что требуется для ознакомления с основами алгоритмизации.
Алгоритмы, в соответствии с которыми решение поставленной задачи сводится к четырем арифметическим действиям, называются численными алгоритмами. Они задаются обычно в виде различных формул и схем: нахождение наибольшего общего делителя, наименьшего общего кратного, корней алгебраического уравнения невысокой степени и многого другого.
Кроме того, существует множество предписаний, относящихся не к цифровым объектам: обработка текстовой информации и изображений, поиск информации в базах данных по заданным критериям.
- Основы информатики и информационных технологий
- Оглавление
- Глава 8. Сети и сетевые технологии 112
- Глава 9. Ащита информации 129
- Предисловие
- Раздел 1. Введение в информатику
- Глава 1. Информатика и предмет ее исследования
- Глава 2. Понятие информации
- 2.1. Определение и свойства информации
- 2.2. Особенности экономической информации
- Глава 3. Роль информации в управлении
- 3.1. Одноконтурная схема управления экономическими системами
- 3.2. Информация и информационные системы в управлении
- Глава 4. Кодирование и представление информации
- 4.1. Основные определения
- 4.2. Связь между системами счисления
- 4.3. Системы счисления, используемые в эвм
- 4.4. Внутреннее представление данных в памяти компьютера
- 4.4.1. Представление чисел
- 4.4.2. Представление текстовых данных
- 4.4.3. Представление мультимедийной информации
- 4.5. Представление данных во внешней памяти компьютера
- Глава 5. Основы алгоритмизации
- 5.1. Определение и свойства алгоритмов
- 5.2. Основные этапы и методы разработки алгоритмов
- 5.3. Основные способы описания алгоритмов
- Раздел 2. Основы информационных технологий
- Глава 6. Аппаратное обеспечение вычислительных систем
- 6.1. Понятие архитектуры и принципы устройства вычислительных систем
- 6.2. Устройство персонального компьютера
- 6.2.1. Конфигурация персонального компьютера
- 6.2.2. Характеристики процессора
- 6.2.3. Организация памяти персонального компьютера
- 6.2.4. Устройства ввода/вывода
- 6.2.5. Внешние запоминающие устройства
- 6.3. Тенденции совершенствования архитектуры
- Глава 7. Программное обеспечение
- 7.1. Понятие программы
- 7.2. Классификация программного обеспечения
- 7.3. Системное программное обеспечение
- 7.3.1. Операционные системы
- Определение и функции операционных систем
- Классификация операционных систем
- Функция управления процессами
- Управление основными ресурсами
- Управление данными. Файловая система
- Управление внешними устройствами и организация ввода/вывода
- Интерфейс с пользователем
- 7.3.2. Операционные оболочки
- 7.3.3. Средства контроля и диагностики
- 7.3.4. Системы программирования
- 7.4. Системы управления базами данных
- 7.4.1. Основные понятия
- 7.4.2. Реляционный подход к управлению бд
- «Магазины»
- «Владельцы»
- «Магазины-Владельцы»
- «Поставки»
- «Товар»
- «Поставки»
- 7.4.3. Назначение и классификация субд
- 7.4.4. Средства описания и манипулирования данными в субд
- 7.4.5. Объектно-ориентированные субд
- 7.4.6. Категории пользователей
- 7.5. Прикладное программное обеспечение
- Глава 8. Сети и сетевые технологии
- 8.1. Определение, назначение и классификация сетей
- 8.2. Способы передачи информации, коммутация и маршрутизация в сетях
- 8.3. Организация взаимодействия в сетях
- 8.4. Топология сетей и методы доступа
- 8.5. Глобальная сеть Internet
- 8.5.1. Идентификация компьютеров в сети
- 8.5.2. Услуги Internet
- 8.5.3. Всемирная паутина World Wide Web
- 8.5.4. Электронная почта
- 8.5.5. Навигационные средства для Internet
- 8.6. Корпоративные сети на основе технологий Internet
- Глава 9. Защита информации
- 9.1. Информация как продукт
- 9.2. Концепция защищенной вс
- 9.2.1. Основные понятия
- 9.2.2. Этапы разработки системы защиты
- 9.2.3. Общая классификация вторжений и характеристика угроз
- 9.2.4. Система защиты
- 9.2.5. Защита объектов на регистрационном уровне и контроль доступа
- 9.3. Криптографические средства защиты информации
- 9.3.1. Основные понятия
- 9.3.2. Криптографические протоколы
- 9.3.3. Электронно-цифровые подписи и открытые сделки
- 9.3.4. Использование криптографической защиты в программных продуктах
- 9.3.5. Условия и ограничения использования криптографической защиты
- 9.4. Программные закладки и вирусы
- 9.5. Хакеры и проблема безопасности информационных систем
- 9.6. Защита информации от потери в результате сбоев
- 9.7. Правовая защита информации и программного обеспечения
- Глава 10. Интегрированные пакеты прикладных программ офисного назначения
- 10.1. Общая характеристика офисных пакетов
- 10.2. Основы редактирования текстовых документов
- 10.3. Использование электронных таблиц
- 10.4. Системы электронного перевода
- 10.5. Системы оптического распознавания текстов
- 10.6. Интеграция систем распознавания текстов, компьютерного перевода и офисных пакетов
- 10.7. Электронные презентации
- 10.8. Графические редакторы
- 10.9. Правовые системы
- 10.10. Учетные системы
- Глава 11. Системы аналитической обработки данных и искусственного интеллекта
- 11.1. Средства анализа данных математических пакетов
- 11.2. Введение в системы искусственного интеллекта
- 11.2.1. Основы экспертных систем
- 11.2.2. Представление и использование нечетких знаний
- 11.2.3. Нейронные системы и сети
- 11.2.4. Системы извлечения знаний
- 11.2.5. Инструментальные средства создания интеллектуальных приложений
- Раздел 3. Современные информационные технологии в экономике и управлении
- Глава 12. Основные понятия
- Глава 13. Эволюция информационных технологий
- Глава 14. Классификация информационных систем
- Глава 15. Корпоративные системы
- 15.1. Типовые технические решения
- 15.2. Корпоративные информационные порталы
- 15.3. Серверы BizTalk как основа средств интеграции информационных систем
- Глава 16. Методы и средства разработки информационных систем
- 16.1. Жизненный цикл информационных систем
- 16.1.1. Процессы жизненного цикла ис
- 16.1.2. Модели жизненного цикла
- 16.2. Методы и средства структурного анализа
- 16.3. Объектно-ориентированный подход к разработке информационных систем
- 16.4. Компонентно-ориентированные средства разработки ис
- Глава 17. Стандарты создания информационных систем
- 17.1. Стандарты кодирования и представления информации
- 17.1.1. Единая система классификации и кодирования технико-экономической и социальной информации
- 17.1.2. Нормативная база системы классификации и кодирования
- 17.2. Унификация и стандартизация документов
- 17.3. Поддержка стандартов управления бизнес-системами
- 17.3.1. Информационные технологии и реинжиниринг
- 17.3.2 Описание стандарта mrp II
- Стратегическое планирование
- Бизнес-планирование
- Планирование объемов продаж и производства
- Планирование ресурсов
- Главный план-график производства
- Общее планирование мощностей
- Mrp, или планирование потребностей в материалах
- Crp, или планирование потребностей в мощностях
- Drp, или планирование потребностей в распределении
- Глава 18. Основы электронной коммерции
- 18.1. Этапы развития электронной коммерции
- 18.2. Секторы рынка электронной коммерции
- 18.3. Инструментарий электронной коммерции
- 18.4. Электронные платежные системы
- Глава 19. Введение в мобильный бизнес
- 19.1. Возможности мобильного бизнеса
- 19.2. Обзор существующих технологий мобильного бизнеса
- 19.2.1. Терминальные устройства
- 19.2.2. Современные технологии построения цифровых каналов связи
- 19.2.3. Стандарты мобильного Internet
- 19.2.4. Проблемы мобильного Internet
- 19.2.5. Операционные системы для мобильных устройств
- 19.2.6. Средства разработки приложений мобильного бизнеса
- Библиографический список