Калайда В.Т., Романенко В.В. Технология разработки программного обеспечения (2007) (1095890), страница 27
Текст из файла (страница 27)
7.3 — Схема распределения памятиПоиск в этом списке осуществляется последовательно дотех пор, пока не будет найдена достаточно большая область дляразмещения данных. Тогда эта область изымается из списка, ана это место помещается меньшая свободная область — оставшаяся незанятая часть исключенной области. С помощью этогометода легко освобождать ранее занятые области памяти.
Сэтой целью просматривается список, как только он будет упорядочен по адресам, то нетрудно найти место, чтобы пометитьосвобожденную область памяти. Соседние адреса — смежные всписке, поэтому легко объединить две свободные области водну, большую по размеру.Данный способ самый простой, однако поскольку занятиеобласти памяти осуществляется после нахождения первой области, достаточной для размещения данных, память становитсяфрагментной.Наилучшее размещение.
Последовательно просматриваются все области, выбирается наименьшая область, размер ко-178торой больше или равен требуемому объему для размещенияданных. В этом случае области связываются друг с другом поразмеру, а не по адресам. Алгоритм размещения-освобожденияаналогичен первому возможному размещению.
Однако в этомслучае стратегия размещения приводит к меньшей фрагментности, потому что используется область наименьшего размерадля размещения данных. Однако так как свободная область неупорядочена по адресам, алгоритм объединения двух свободныхобластей в область большего объема довольно сложен.Сопрягаемые области памяти. Областями памяти являются N цепочек размером 2N каждая. Если область размером 2K отсутствует, а имеется свободная область размером 2K+1, то она разбивается на две сопрягаемые области размером 2K. После того какобласти освободятся, они рассматриваются как области размером2K, которые можно объединить в область размером 2K+1.7.5 СортировкаСортировка — это процесс размещения элементов всписке в некоторой числовой или лексикографической последовательности (порядке). Различаются следующие виды сортировки.Обменная сортировка.
При этом способе наименьший элемент выдвигается в начало списка, следующий по величине — навторую позицию и т.д. Для списка N элементов производитсяN(N – 1)/2, т.е. O(N2) операций. Естественно, что для большихзначений N использование этой сортировки нецелесообразно.Алгоритм:EXCHANGE_SORT procedure(LIST,N);declare LIST(N); /* массив сортировки */do I=1 to N-1;do J=I+1 to N;if LIST(J)< LIST(I) thenReverse(LIST(J), LIST(I));end;end;179end EXCHANGE_SORT;Сортировка слиянием.
Данный способ сортировки схож сметодом разбиения на подзадачи. Вначале неотсортированныйсписок делится на две части, затем каждая часть сортируетсянезависимо. После этого списки объединяются.Алгоритм:MERGE_SORT procedure(LIST,N);declare LIST(N); /* массив сортировки */call MERGE_SORT(LIST(1:N/2),N/2,(LIST(N/2+1:N),N/2));/* объединение отсортированных списков */end MERGE_SORT;Процедура слияния отсортированных списков размером Kвыполняется за 2×K операций путем просмотра первого элемента в каждом списке и перенесения меньшего из двух в новыйсписок.
Эти два действия повторяются для каждого из 2×K элементов списка, получается 4×K операций. Так как каждый изсписков уже отсортирован, нужно проверить только первыеэлементы. Хотя для реализации этого способа нужна памятьбольшого объема, время сортировки путем последовательногоразбиения каждого из подсписков на два можно уменьшить довеличиныN log 2 N .7.6 Алгоритм выбора из конечного состоянияЧасто задача может быть сведена к множеству действий,зависящих от текущего состояния программы. Такой способ решения задачи называется выбором из конечного состояния иобычно включает таблицу, описывающую выполняемые действия. Строки таблицы определяют состояние программы, астолбцы — возможные действия.
Элементы таблицы описывают выполнение возможных действий, в частности имя вызываемой подпрограммы для обработки действий.180Переменными в этом случае являются текущее состояниепрограммы и допустимое воздействие, определяемое внешнейсредой. Пересечение этих значений в матрице решений определяет ответное действие и новое состояние программы. Такие состояния (алгоритмы) наиболее характерны для лексическогоанализатора трансляторов.
Решение подобных задач строитсяпо типу модели конечного автомата.Таблица состояний:ABC…IJK…YZ12…N–1NN+1…M7.7 СопрограммыВ некоторых системах две или более задач должны обрабатываться посегментно, причем каждый сегмент выполняетсяс различной скоростью (рис. 7.4).A1A2B1B2A3A4B3B4181Рис. 7.4 — Организация сопрограммИспользование сопрограмм может быть полезной управляющей структурой.Сопрограмма — это такой вид программы, которыйсохраняет текущее состояние счетчика команд.
Когда программа вызывается повторно, выполнение продолжается с адреса,записанного в счетчике программ, а не с начала программы.Сопрограмма, возвращающая управление в процедуру X,определяется как resume X. Использование такого оператораязыка PDL можно представить следующим образом:call DATA;goto Next_Statement;/* Для элементов данных */DATA: procedure;declare FS, DV;DV = значение данных 1;resume FORMAT(FS);call I/O – process(DV, FS);DV = значение данных 2;resume FORMAT(FS);call I/O – process(DV, FS);...DV = значение данных n;call I/O – process(DV, FS);end DATA;FORMAT: procedure(FS);LOOP: FS = спецификация формата 1;resume DATA(FS);FS = спецификация формата 2;resume DATA(FS);182...FS = спецификация формата n;goto LOOP;end FORMAT;Next_Statement:...Здесь каждая сопрограмма вызывает другую сопрограмму.Таким образом, программа обработки данных вызывает программу обработки формата до следующего элемента формата.К сожалению, сопрограммы отсутствуют в широко распространенных языках программирования.Контрольные вопросы1.2.3.4.5.6.7.8.9.10.11.Стандартные методы проектирования.Разбиение задачи на независимые подзадачи.Разбиение задачи на одинаковые по сложности части.Рекурсия.Динамическое программирование.Моделирование.Поиск.
Поиск в списках. Прямой поиск. Линейный поиск.Поиск с возвратом.Стратегия распределения памяти.Алгоритм выбора из конечного состояния.Сопрограммы.1838 МЕТОДЫ УПРАВЛЕНИЯ ПРОЕКТИРОВАНИЕМПРОГРАММНЫХ ИЗДЕЛИЙОсновная цель управления — организовать и связать взаимодействие исполнителей при создании программного продукта.8.1 Организация управления проектированиемпрограммного изделия8.1.1 Понятие изделия как средства общенияДействия при создании программного изделия по многимпараметрам совпадают с действиями при создании технического изделия.Изделие1. Изучение рынка2.
Планирование3. Анализ окупаемости4. Разработка5. Конфигурационноеуправление6. Обеспечение гарантии качества7. Изготовление8. Контроль качества9. Отправка потребителю10. Ввод в действие11. Гарантийный ремонт12. УсовершенствованиеПрограмма1. Изучение рынка2. Планирование3. Рассмотрение соглашения о требованиях4.
Разработка5. Конфигурационное управление6. Тестирование (автономное)7. Копирование8. Тестирование (системное)9. Передача пользователю10. Ввод в действие11. Сопровождение12. Расширение функциональных возможностейТо есть самые общие действия при создании изделия имеют аналоги при создании программного продукта, таким образом, можно использовать опыт по управлению изготовлением.1848.1.2 Нисходящий анализ процесса управленияпроектированием программного изделияУправление проектированием программного изделиявключает в себя следующие функции: планирование; разработку; обслуживание; выпуск документации; испытания; поддержку; сопровождение;Иерархическая декомпозиция управления разработкойпрограммного изделия может быть представлена следующимобразом (рис. 8.1).Главный разработчикАдминистраторпланированияРуководитель разработкиРуководитель испытанийРуководитель поддержкиРуководитель обслуживанияРуководитель выпускадокументацииРуководительсопровожденияРис.
8.1 — Декомпозиция управленияТакая идеализированная организация требует полной обособленности процессов, связанных с проектированием, от других видов деятельности и изолированности всех функций другот друга. Естественно, что на практике это не реализуемо.Каждая организация должна иметь администратора (директора), именно он несет ответственность за успех и неудачуразработки. В структуре также должно существовать то илииное важное направление деятельности, включая функцию раз-185работки.
Лицо, которое руководит этим направлением, считается ответственным за все аспекты создания изделия, выпускаемого организацией. Чтобы координировать процесс разработки,это лицо имеет право назначать администраторов изделия и руководителей проектов и обеспечивать их взаимодействие.8.1.3 Организация взаимодействияЕсли все взаимодействия хорошо определены, то и управление ими организовано должным образом. Если же взаимодействия плохо организованы, то даже при жесткой линейнойструктуре подчинения трудно будет создать конечное изделие.Важнейшим принципом любого вида управления являетсяразделение целого на части, и многие методы и средства основываются именно на этом принципе.Совокупность точек, в которых две функциональныегруппы взаимодействуют друг с другом, называется организационной границей.
Иногда функция может иметь один каналвзаимодействия со всеми остальными функциями, однако болеевероятно, что она имеет несколько границ соприкосновения.Границы функции определяются множеством зафиксированныхи незафиксированных планов, стратегий, процедур, которыеопределяют функциональные обязанности. Чем больше сведений фиксируется в письменном виде, тем лучше, т.к.
это уменьшает двусмысленность. Основное свойство организационнойграницы состоит в разграничении ответственности (кто и чтоделает, каким образом, для чего и т.д.). Неполное определение,двусмысленность и сложность приводят к невозможности описания, а следовательно, и понимания природы взаимодействия.Но ни сами документы, ни их коллективное обсуждениене могут обеспечить действенных взаимосвязей, если отсутствуют контакты функциональных групп.Общие организационные обязанности могут устанавливаться с помощью должностных инструкций и целевых плановподразделений.
Конкретные обязанности определяются планами выпуска изделия. Пропорциональное распределение ответственности обеспечивается соответствующими стратегиямиуправления. В них обязательно должны предусматриваться возможности невыполнения взятых обязательств и учитываться по-186правки на исключительные случаи, чтобы сделать планы и процедуры жизнеспособными.8.1.4 Установление целей, средства их достиженияПервым шагом процесса установления и достижения целей является подбор необходимого персонала. Когда в организации происходят изменения, соответственно меняется и ее персонал. Некоторые изменения происходят периодически.
Подобные изменения характеризуются экспоненциальным ростомчисла устанавливаемых связей. Чтобы приспособиться к этимколебаниям, нужны руководители, способные к адаптации. Руководителей, продуктивных только в каком-либо одном видедеятельности, нужно заменять. Программирование — областьдеятельности, требующая высокой квалификации, оно привлекает к себе неординарных, эксцентричных людей.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
