Языки и методы программирования Преподаватель – доцент каф. ИТиМПИ Кузнецова Е.М. Лекция 8

Содержание Построение модели Разработка и анализ алгоритмов

проектирование и разработка программ состоит из этапов: 1)постановка задачи; 2) проектирование программы; 3) построение модели; 4) разработка алгоритма; 5) реализация алгоритма; 6) анализ алгоритма и его сложности; 7) тестирование программы; 8)документирование.

Построение модели 1. Какие математические структуры больше всего подходят для решения задачи? 2. Существуют ли решенные аналогичные задачи?

Задача коммивояжера Джек – агент по продаже компьютеров (коммивояжер). На его территории 20 городов, разбросанных по всему штату. Компания возмещает ему только 50% стоимости деловых поездок. Джек вычислил, сколько ему будет стоить переезд на машине между каждыми двумя городами на его территории. Ему, естественно, хотелось бы снизить свои дорожные расходы. Дано: двумерный массив с элементами cij, равными стоимости переезда из города i в город j. Дополнительная информация: маршрут должен начинаться и заканчиваться в одном городе, каждый город посещается один раз. Найти: самый выгодный маршрут!

Задача коммивояжера с 5 городами: граф это совокупность объектов со связями между ними. Сеть - множество точек на плоскости вместе с линиями, соединяющими некоторые или все пары точек; над линиями могут быть проставлены веса.

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

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

Технология построения модели при индуктивном способе: эмпирический этап умозаключение; интуиция; предположение; гипотеза. постановка задачи для моделирования; оценки; количественное и качественное описание; построение модели.

Разработка алгоритма Выбор метода разработки зависит от постановки задачи, ее модели. необходимо провести анализ правильности алгоритма, что очень непросто и трудоемко (прогон его на множестве различных тестов). методика доказательства правильности алгоритма : алгоритм описан в виде последовательности шагов. Для каждого шага предлагается некое обоснование его правильности для всех подходящих входных (условиях до данного шага) и выходных данных (условиях после этого шага). Затем предлагается доказательство конечности алгоритма с окончательными исходными входными и выходными данными.

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

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

ПРИНЦИПЫ РАЗРАБОТКИ И АНАЛИЗА АЛГОРИТМОВ При построении алгоритма для сложной задачи используют системный подход с использованием декомпозиции (нисходящее проектирование сверху-вниз) и синтеза (программирование снизу-вверх). При формировании алгоритма используют дедуктивный и индуктивный методы.

Дедуктивный подход рассматривается частный случай общеизвестных алгоритмических моделей. при заданных предположениях известный алгоритм приспосабливается к условиям решаемой задачи. В настоящее время получили распространение специализированные пакеты, позволяющие решать многие задачи (Mathcad, Eureka, Reduce Autocad и т.п.).

Индуктивный подход предполагает эвристический системный подход (декомпозиция - анализ - синтез). общих и наиболее удачных методов не существует, возможны некоторые подходы, позволяющие в каждом конкретном случае находить и строить алгоритмы.

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

управляющие структуры композиция, альтернатива, итерация.

Композиция - это линейная конструкция алгоритма, составленная из последовательно следующих друг за другом функциональных вершин. begin S1;S2; end Структура «композиция»

Альтернатива - это конструкция ветвления, имеющая предикатную вершину. Конструкция ветвления в алгоритмах может быть представлена в виде развилки (а), неполной развилки (б) и выбора (в) Структура «альтернатива».

Итерация - это циклическая конструкция алгоритма, которая, вообще говоря, является составной структурой, состоящей из композиции и альтернативы. Структура «итерация»

Идея структурного программирования сверху-вниз - если для некоторой функции f существует ее композиция через две другие функции g и h, т.е. f=h(g(х)), то проблема разработки алгоритма для f сводится к проблемам разработки алгоритмов для h и g. В структурном программировании сверху- вниз на каждом шаге пытаются текущую функцию выразить как композицию двух (или более) других функций, которые представимы в виде рассмотренных выше управляющих структур.

Пошаговая детализация построения алгоритма

С. Гудман, С. Хидетниеми Введение в разработку и анализ алгоритмов., 1981, Изд- во «Мир» Левитин Ананий В. Алгоритмы: введение в разработку и анализ, 2006, Изд- во: Диалектика-Вильямс