Динамическое программирование
Динамическое программирование — это табличный метод, при котором используется одна и та же схема вычисления всех подзадач данной задачи. При использовании этого метода однажды найденный результат записывается в таблицу и далее повторно не вычисляется. Динамическое программирование (ДП) втеории вычислительных систем— способ решения сложных задач путём разбиения их на более простые подзадачи. Он применим к задачам соптимальной подструктурой, выглядящим как набор перекрывающихся подзадач, сложность которых чуть меньше исходной. В этом случае время вычислений, по сравнению с «наивными» методами, можно значительно сократить.
Поиск. Поиск в списках Деревья поиска
Если данные организованы как структура дерева, алгоритм поиска сводится к алгоритму, просматривающему все узлы дерева. Для ведения поиска существуют два основных алгоритма поиска: поиск в глубину и поиск в ширину.
Поиск в глубину. При поиске в глубину каждая ветвь дерева просматривается слева направо.Для двоичных деревьев алгоритм поиска имеет простую рекурсивную структуру(7.1). Поиск в ширину. Это алгоритм поиска, при котором просматривается каждый уровень в направлении сверху вниз (рис. 7.2).
Стратегия распределения памяти Сопрограммы
Одним из типов поиска являются задачи по распределению памяти (наиболее характерны они при создании ОС), однако во многих прикладных алгоритмах эти задачи возникают при создании прикладных программ, работающих с большим объемом данных. Если до начала обработки полный объем данных, которые подлежат обработке, неизвестен, то используется общий подход для распределения областей этой памяти согласно заданным требованиям. Дана фиксированная область памяти, задача заключается в том, чтобы занимать и освобождать меньшие области памяти большой областью, без выхода за границы памяти. При распределении памяти проверяются наибольшие свободные области. Обычно эти области малы для размещения в них всех данных, и, следовательно, память становится фрагментной. Имеются следующие способы уменьшения фрагментности.
Возможное размещение. Последовательно просматриваются области памяти, пока не найдется первая, достаточная для размещения. Вся область организована в список и упорядочена по адресам.
Наилучшее размещение. Последовательно просматриваются все области, выбирается наименьшая область, размер которой больше или равен требуемому объему для размещения данных.
Управление проектированием программного изделия
Основная цель управления – организовать и связать действия исполнителя при создании программы. Программное изделие является средством общения между разработчиком и …
Д
екомпозиция
управления. Декомпозиция планов
Принципы декомпозиции планов:
Какая свобода выбора желательная на следующем шаге планирования
Определение ограничений более низкого уровня планирования.
Ошибки декомпозиции:
Упущение существенных аспектов
Изменение детализации
Иерархия планов
Обычно целевые программы редко имеют самостоятельную значимость, они предназначены для других программ, чтобы ответить на вопрос зачем?
Отработка стратегий
Следующий уровень планирования — стратегический план. Он отвечает на вопросы что? И когда? При этом, чем более конкретна цель, тем более своеобразны будут стратегии ее достижения.
Документы обзоров
Документы обзоров
Документы обзоров ЖЦПИ
-
Фаза
Обзор событий
Вопросы
1.исследования
Ресурсы распределения
1,2
Распределение бюджета
Извещение о сроках
Согласование о требованиях
Спецификации
Издание документации
План испытаний
План поддержки
Отчеты
План выпуска
Конфигуратор
2.анализ осуществимости
Требование утверждения
1, 2, 3, 9, 10
3.конструирование
Спецификации утверждения
1, 2, 4, 5, 6
4.программирование
Испытания начаты
1, 2, 8
5.оценка
Распределение начато
2, 8, 9, 10
6.исполнение
Изделие снято с производства
10