5.2. Основные этапы и методы разработки алгоритмов
Процесс решения любой задачи можно разбить на несколько этапов. Первыми шагами решения всегда являются анализ задачи и разработка (проектирование) алгоритма ее решения.
На этапе анализа задачи уточняется постановка задачи, исходные данные для ее решения и предъявляемые к решению требования и условия, при которых задача должна быть решена.
После того как получена четкая предметная постановка задачи, нужно сформулировать для нее математическую модель. Невозможно предложить набор правил, автоматизирующих этот этап математического моделирования. Большинство задач должны рассматриваться индивидуально. Но разрабатывая модель, необходимо ответить на вопросы:
Существуют ли решенные аналогичные задачи?
Какие математические структуры больше всего подходят для описания того, что известно и что надо найти, какие отношения выявлены между объектами модели?
Как только задача четко сформулирована и для нее построена теоретическая модель, приступают к разработке алгоритма ее решения. Первое, что требуется от алгоритма, – это правильно реализовать функцию, которая каждому элементу из множества исходных данных ставит в соответствие возможный результат. Во-вторых, от алгоритма требуется такая реализация этой функции, чтобы время решения и затрачиваемые усилия были, по возможности, минимальными.
На сегодняшний день, по-видимому, самой популярной методикой проектирования алгоритмов, уменьшающей вероятность ошибок, упрощающей понимание и облегчающей их модификацию, считается технология нисходящего структурного проектирования или проектирования сверху вниз.
Этот метод предусматривает последовательную детализацию решения, сведение поставленной задачи к последовательности более простых задач, которые легче поддаются решению, чем исходная задача, но из их решений может быть получено решение первоначальной задачи.
При использовании этого метода осуществляется декомпозиция общей задачи на точно определенные подзадачи и доказательство того, что если каждая задача решена корректно и полученные решения связаны друг с другом определенным образом, то исходная задача также будет решена корректно. Затем для полученных подзадач также повторяются процессы декомпозиции и доказательства корректности, которые повторяются до получения подзадач настолько простых, что их решение может быть сформулировано в терминах элементарных операций, понятных исполнителю алгоритма.
Алгоритмы решения задач могут реализовывать различные методы. При решении задач на ЭВМ широко используются методы эвристики и имитации.
Эвристический алгоритм позволяет найти некоторое приближенное, необязательно оптимальное решение задачи, его можно быстрее и проще реализовать, чем «точный» алгоритм. Кроме того, следует помнить, что существуют задачи, которые просто не имеют точных решений.
При использовании этих методов все требования, предъявляемые к точному решению, разбиваются на два класса: те, которые должны быть удовлетворены (или могут быть легко удовлетворены), и те, по отношению к которым можно «пойти на компромисс».
Не существует универсальной структуры, описывающей эвристические алгоритмы, но многие из них основываются или на методе частных целей, или на методе подъема.
Итерация – способ получения результата путем последовательных приближений к нему, начиная от некоторого заданного начального значения (или нескольких значений), в процессе которого повторяется заданная в алгоритме последовательность шагов.
Например, для вычисления факториала n! (по определению n! = 12…(n–1)n при n > 0 и 0! = 1) можно повторять операцию умножения, начав со значения 1 (1 умножить на 2, полученный результат умножить на 3 и т.д.: n! = ((…((12)3)…)(n–1))n):
f 1; f f1; f f2; f f3; …; f f(n–1); f fn.
Этот способ решения задач – один из наиболее часто используемых при вычислениях с помощью компьютера (примером являются многие численные методы решения задач).
Некоторые специалисты считают, что инструментом, упрощающим логическую структуру многих алгоритмов, является рекурсия – метод выражения решения задачи через ту же задачу, но имеющую меньшую размерность. Одним из мощных методов решения задач в математике (для доказательства утверждений, описания классов объектов и т.д.) является метод математической индукции. Рекурсия – это по сути та же индукция, применяемая к построению алгоритмов.
Пример простейшего рекурсивного алгоритма решения задачи – вычисление факториала. Эту задачу можно решить, сгруппировав множители следующим образом: n! = (12…(n–1))n, произведение, записанное в скобках, – это (n–1)!, таким образом: n! = (n–1)!n.
При разработке рекурсивного, как и итерационного, алгоритма обязательно указывается условие, при котором рекурсия останавливается. В данном примере значение n уменьшается, пока не достигнет значения 0. Вычислив значение 0! = 1, рекурсия начинает «обратный ход», при выполнении каждого шага которого происходит возврат вычисленного значения и умножение.
Рекурсивные алгоритмы широко используются при решении задач с помощью компьютера (в частности, задач искусственного интеллекта).
По мере того как алгоритмы становятся все более сложными, растет трудность понимания того, как они работают, доказательства их правильности, исправления обнаруженных в них ошибок, внесения изменений. Поэтому очень важно правильно выполнить проектирование алгоритма и выбрать подходящий метод (методы) решения задачи (или подзадач, на которые при проектировании распалась исходная задача).
Для записи алгоритма в процессе решения задачи используются различные способы.
- Основы информатики и информационных технологий
- Оглавление
- Глава 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. Средства разработки приложений мобильного бизнеса
- Библиографический список