Поиск делением пополам

Линейный поиск

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

Алгоритм поиска можно представить таким образом:

1. Сравнить первый элемент с требуемым.

2. Если элементы совпадают, то поиск закончен, элемент найден.

3. Если элементы не совпадают, то сравнивается следующий элемент, при этом вновь начинается процесс (2).

4. Этот процесс продолжается до тех пор, пока не будет достигнут конец массива или пока не будет найден требуемый элемент.

Этот алгоритм целесообразно применять для любой неупорядоченой последовательности чисел, или неотсортированного массива.

Совершенно очевидно, что если массив не отсортирован и нет никакой дополнительной информации, то никаких способов убыстрения его работы как с использованием алгоритма линейного поиска не существует. Но если известно, что массив отсортирован, поиск можно сделать более эффективным. Допустим данные отсортированы по возрастанию.

Основная идея состоит в том, что выбранный случайным образом элемент массива, при сравнении с требуемым, если он не равен ему, даст две ветви поиска

- при условии, что выбранный элемент массива больше искомого, из рассмотрения исключаются все элементы большие, чем выбранный;

- при условии, что выбранный элемент массива меньше искомого, из рассмотрения исключаются все элементы меньшие, чем выбранный;

Чтобы сбалансировать поиск, целесообразно каждый раз делить массив на две части, т.е. каждый раз выбирать элемент посередине. В этом случае вероятность нахождения элемента в каждой половине массива одинакова. Такой способ поиска получил название поиск делением пополам.

Поиск в таблице

Иногда поиск в массиве называют поиском в таблице, если это массив символов. Часто массив символов представляет собой строки или слова.

Для того чтобы установить факт совпадения мы должны очевидно убедиться, что все символы сравниваемых строк соответственно равны один другому. Поэтому сравнение сводится к поиску их не совпадающих частей, т.е. поиску на неравенство. Если не равный частей не существует можно говорить о равенстве

Рассмотрим это на примере. Пусть какой-то текст хранится в виде последовательности литер; задача состоит в том, чтобы отыскать в нем первое появление определенного "слова", которое можно определить как последовательность литер не длиннее самого текста. Алгоритмы, основанные на этой модели, имеют важное значение во многих областях информатики, что особенно заметно в программах символьной обработки.

При построении данного алгоритма надо точно сформулировать, что считать требуемым результатом.

1. Результатом будет совпадение букв между искомым словом и текстом. Если слово имеет индекс i от 1 до n, то начиная с некоторого j (где j индекс текста) до j=j+n наблюдается совпадение с символами i= 1...n.

2. Для всех значений символов, которые меньше символа j (символа с которого начинается совпадение) в тексте не будет наблюдаться совпадение с искомым словом.

3. Нельзя не учитывать еще одну возможность: в заданном тексте нужного слова может вообще не оказаться. Подобного типа недосмотр часто является причиной неверной работы программы. Это упущение можно исправить, если договориться, что в случае неудачного поиска слова выходное значение j следует сделать большим максимального значения, допустимого для начала сравниваемых цепочек.

Перечисленные три условия являются схемой для установления самого алгоритма Один очевидный метод - итерационный. Первое и третье условия устанавливаются в цикле while в качестве пароля, второе условие выступает как инвариант цикла. Начальное значение j задается равным О, т. е. поиск начинается с начала текста. При каждом прохождении цикла осуществляется проверка конт­рольных условий; если слово совпадает с текстом или j превышает размер букв в стоке т, то программа выходит из цикла, в противном случае j увеличивается на 1 и цикл повторяется.

Остается определить, как устанавливается само совпадение, т. е. как сравниваются литеры слова с литерами текста во всем диапазоне значений индекса i от 1 до n. Это обеспечивается циклом, вложенным в основной цикл для каждого значения j внутренний цикл охватывает весь диапа­зон значений i и п литер сравниваются по одной. При первом несовпалении литер внутренний цикл принудительно прерывается. Значение i на выходе из цикла показывает, было обнаружено совпадение или нет; если i меньше n, сравнение закончилось из-за несовпадения.

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

Трудно было поверить, что спустя целых 30 лет после того, как начались исследования в области кибернетики, можно существенно улучшить метод решения такой фундаментальной задачи, какой явля­ется поиск в тексте. Тем не менее в 1976 г. Р. Бойер и Дж. Мур, нашли более быстрый способ. Их идея позволяет увенчивать j более чем на 1 при каждом шаге в основном цикле программы. Сравнение слова с частью текста начинается от конца слова (помещаемого в начале текста) и продолжается по направлению к его началу. Если проверяемая литера в слове не совпадает с соот­ветствующей литерой текста, то слово двигается вправо относительно этой позиции, которую назовем опорной, до тех пор, пока какая-нибудь литера снова не совпадет с литерой текста в этой позиции. Если этого не произойдет, то слово сдвига­ется таким образом, чтобы его первая литера от­стояла от опорной позиции на один интервал.

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

Ниже приводятся рисунки для пояснения вышеуказанных алгоритмов.

Рис. 6.4. ПОИСК СЛОВА В ТЕКСТЕ осуществляется путем последо­вательных сравнений букв. Слово и текст являются мас­сивами букв. В данном случае текст содержит 25 букв, а слово — четыре. Первая буква слова сравнивается с пер­вой буквой текста; поскольку они совпадают (подчеркивание), сравниваются вторые буквы. На этот раз буквы отличаются (обычный кружок); следовательно, слово сдвига­ется на одну позицию вправо и проверка производится заново с начала слова. Слово считается найденным, когда все буквы совпадают. Условия, которым должен удовлетво­рять этот алгоритм, сформулированы в трех предложениях на языке исчисления предикатов, приведенных в нижней части рисунка. Первое высказывание (Р) гласит, что если слово выставлено в позицию j массива-текста, то для всех значений индекса массива-слова i элемент слово [i] оди­наково элементом текст [j+i]. Высказывание (Q) утверж­дает, что для всех меньших значений j не существует ни одного совпадения цепочек; это значит, что ищется пер­вое появление в тексте данного слова. Третье предложе­ние, которое должно выполниться в конце поиска, гласит, что (1) выполнятся и Р, и Q (2) либо i будет иметь зна­чение n (показывающее, что совпадение обнаружено е позиции j ), либо j окажется больше того значения которое возможно для совпадения (признак того, что слово в данном тексте отсутствует).

Рис. 6.5. АЛГОРИТМ БЫСТРОГО ПОИСКА был придуман в 1976 г. Р. Бойером и Дж, Муром, работающими в Техасском университете в Остине. Поиск ведется с начала текста, но с конца слова. Программа должна содержать таблицу расстояний от конца слова до каждой буквы (из одинако­вых букв выбирается ближайшая к концу слова); если буква в слово не входит, в соответствующей позиции таблицы указывается длина всего слова. Когда очередная буква слова не совпадает с буквой текста, для последней из таблицы определяется.соответствующее расстояние; после этого слово сдвигается вправо на нужное число позиций. При первом сравнении буква к в слове не совпа­дает с буквой е в тексте, поэтому слово сдвигается на две позиции.

7. Документирование, сопровождение и эксплуатация программ.

7.1.Стандартизация, дисциплина и творчество в программировании.

Внедрение стандартов в процесс создания программ направлено на создание следующих результатов:

1. Упрощение процесса разработки программы;

2. Облегчение чтения и понимания программ сторонними лицами, что ведет к снижению числа ошибок, упрощает пользование и эксплуатацию;

3. Улучшение подготовки новых кадров.

До последнего времени программирование рассматривалось как искусство, точнее, как прикладное искусство, или ремесло, подобное чеканке или стеклодувному делу. Поэтому введение каких-либо ограничений на приемы и технику программирования, использование готовых операторов и блоков рассматривалось как мера, направленная на сужение творческих возможностей программиста и, как следствие этого, снижение качества программ. Сложившаяся практика могла считаться удовлетворительной, пока применение ЭВМ ограничивалось научными и инженерными расчетами, созданием экспериментальных программ, где процессами программирования занимались "избранные". Однако в настоящее время она уже не может считаться нормальной. Причина этого состоит прежде всего в том, что получили широкое распространение систем обработки самых разнообразных данных, глобально расширилось число областей применения ЭВМ, и самое главное, к процессам программирования стало привлекаться множество людей, зачастую не имеющих достаточных знаний в области программирования. Все это привело к созданию определенных правил как в области написания программ, так и в области составления документации на нее.

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

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

В стандартах ЕСПД установлены требования, регламентирующие разработку, производство, тиражирование и сопровождение программ, что обеспечивает возможность:

а) унификации программных изделий для взаимного обмена программами и применения ранее созданных программ в новых разработках;

б) снижение трудоемкости и повышения эффективности разработки, сопровождения, изготовления и эксплуатации программных изделий;

в) автоматизации изготовления и хранения программ ной документации.

В состав ЕСПД входят:

1) основополагающие и организационно-методические стандарты;

2) стандарты, определяющие виды, форму и содержимое программных документов;

3) стандарты, обеспечивающие автоматизацию разработки программных документов.

Стандарты ЕСПД подразделены на группы в соответствии с табл. 7.1.

Таблица 7.1. Группы стандартов ЕСПД

Код группы	Наименование группы
	Общие положения
	Основополагающие стандарты
	Правила выполнения документации разработки
	Правила выполнения документации изготовления
	Правила Выполнения документации сопровождения
	Правила выполнения эксплуатационной документации
	Правила обращения программной документации
	Резервная группа
	Резервная группа
	Прочие стандарты

Обозначения стандартов ЕСПД строятся ïî классификационному признаку, они состоят из:

номера 19, присвоенного классу стандартов ЕСПД;

одной цифры (после точки), обозначающей код классификационной группы стандартов, определенной табл. 7.1;

двузначного числа, определяющего порядковый номер стандарта в группе;

двузначного числа (после тире), указывающего год регистрации стандарта.

Например, стандарт «Единая система программной документаций. Общие положения» имеет следующее обозначение:

ГОСТ 19.001—77.

Наряду со стандартами на документацию, определенными ЕСПД, большое значение приобретает стандартизация отдельных компонентов программного изделия и самой техники программирования, каталогизация типовых ситуаций и принимаемых в них решений применительно к конкретным условиям: языкам программирования, операционной системе, принятой методике отладки и тестирования, а также характеру самих задач.

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

В практическом отношении наиболее важно унифицировать следующие этапы разработки программ:

1. Проектирование: анализ задачи, фиксация требований к программе, разбиение общей задачи на подзадачи, анализ структур данных, разработка общей структуры программ с выделением основных модулей и определением интерфейса между ними, написание детальных спецификаций модулей.

2. Вычерчивание блок-схем.

3. Собственно программирование или кодирование.

4. Методы «ручной» проверки (без использования ЭВМ).

5. Отладка и тестирование.

6. Документирование.

7. Планирование и оценка качества и количества труда отдельных программистов и коллективов.

Вопрос о стандартизации и унификации процесса программирования непосредственно связан с вопросами дисциплины и эффективной организации труда программиста. Как и всякий интеллектуальный труд, работа программиста трудно поддается контролю и оценке. Поскольку стандартизация способствует лучшему контролю и регламентации труда, побуждает скорее к дисциплине, чем к свободному самовыражению в изобретении остроумных трюков и уловок, то введение стандартов наталкивается на определенное сопротивление со стороны программистов,; чаще всего выражающееся в критике стандартов. Этот психологический барьер необходимо преодолеть. Известный специалист по психологии программирования Вайнберг рекомендует немедленно увольнять с работы всех оригиналов, которые все делают без плана, без документации, считая себя «свободными художниками», разлагают других сотрудников своей недисциплинированностью. Такие решительные меры вряд ли стоит рекомендовать. Надо, прежде всего, разъяснить, что, во-первых, взятые на вооружение и используемые стандарты много полезнее, чем хорошие стандарты, записанные на бумаге, во-вторых, хорошие стандарты получаются не сразу и в процессе систематического применения и совершенствования плохие стандарты можно довести до хороших. Важнейшим фактором в разработке эффективных и приемлемых стандартов является активное участие самих программистов в их разработке и совершенствовании по мере накопления опыта.

7.2. Виды программ и программных документов

Эта книга посвящена программному обеспечению ЭВМ и его важнейшим компонентам, поэтому целесообразно здесь напомнить значение важнейших терминов, используемых нами в дальнейшем. ГОСТ 1978—74 в числе прочих определяет следующие понятия:

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

Программа— алгоритм, записанный в форме, воспринимаемой вычислительной машиной.

Программирование — раздел прикладной математики, разрабатывающий методы использования вычислительных машин для реализации алгоритмов.

Программное обеспечение—совокупность программ и документов на них для реализации целей и задач цифровых электронных вычислительных машин.

Программное изделие — программа на носителе данных, являющаяся продуктом промышленного производства.

В литературе по программированию широкое распространение получили также следующие термины.

Подпрограмма — часть программы, выделяемая в целях сокращения записи программы и выполняющая четко определяемую функцию.

Программный сегмент — часть программы, которая может выполняться, не требуя нахождения в оперативной Памяти остальных частей.

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

ЕСПД устанавливает следующие виды программ с точки зрения документирования.

Рис. 7.1.

Компонент— программа, рассматриваемая как единое целое, выполняющая законченную функцию и применяемая самостоятельно или в составе комплекса.

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

С точки зрения документирования подпрограмма не всегда является компонентом: это зависит от того, обращается ли эта подпрограмма к другим подпрограммам. Что же касается программы, то она может быть и компонентом, и комплексом. На рис. 7.1 показана структура достаточно сложного комплекса с точки зрения его разработки и документирования.

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

Виды программных документов и их содержание приведены в табл. 7.2 и 7.3.

Таблица 7.2. Виды программных документов

Вид программного документа	Содержание программного документа
Спецификация	Состав программы и документация на нее
Ведомость держателей подлинников	Перечень предприятий, на которых хранят подлинники программных документов
Текст программы	Запись программы с необходимыми комментариями
Описание программы	Сведения о логической структуре и функционировании программ
Программа и методика испытаний	Требования, подлежащие проверке при испытании программы, а также порядок и методы их контроля
Техническое задание	Назначение и область применения программы, технические, технико-экономические и специальные требования, предъявляемые к программе, необходимые стадии и сроки разработки, виды испытаний
Пояснительная записка	Схема алгоритма, общее описание алгоритма и функционирования программы, а также обоснование принятых технических и технико-экономических решений
Эксплуатационные документы	Сведения для обеспечения функционирования и эксплуатации программы

Таблица 7.3. Эксплуатационные документы

Вид программного документа	Содержание программного документа
Ведомость эксплуатационных документов	Перечень эксплуатационных документов на программу. Регламентируется стандартом ГОСТ 19.507— 79
Формуляр	Основные характеристики программы, комплектность и сведения об эксплуатации программы. Регламентируется стандартом ГОСТ 19.501—78
Описание применения	Сведения о назначении программы, области применения, классе решаемых задач, применяемых методах, ограничениях для применения, минимальной конфигурации технических средств. Регламентируется стандартом ГОСТ 19.502—78
Руководство системного программиста	Сведения для проверки, обеспечения функционирования и настройки программы на условия конкретного применения. Регламентируется стандартом ГОСТ19.503—79
Руководство программиста	Сведения для эксплуатации программы. Регламентируется стандартом ГОСТ 19.504—79
Руководство оператора	Сведения, необходимые для осуществления действий, связанных с выполнением программы вычислительной системой. Регламентируется стандартом ГОСТ 19.50&-79
Описание языка	Описания синтаксиса и семантики языка. Регламентируется стандартом ГОСТ19.506—79
Руководство по техническому обслуживанию	Сведения для применения тестовых и диагностических программ при обслуживании технических средств

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

Допускается объединять отдельные виды эксплуатационных документов, за исключением ведомости эксплуатационных документов и формуляра. Необходимость объединения документов указывается в техническом задании. Объединенному документу присваивают наименование и обозначение одного из объединяемых документов. В объединенных документах должны быть приведены сведения, которые необходимо включать в каждый объединяемый документ. Требования к содержанию и оформлению каждого из перечисленных документов определены соответствующими стандартами ЕСПД.

Согласно общим требованиям к программным документам (ГОСТ 19.105—78) программный документ может быть представлен на различных типах носителей данных, в том числе и машинных: магнитных лентах и дисках и др. Правила оформления документов и их частей на каждом носителе данных устанавливаются соответствующими стандартами ЕСПД.

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

Таблица 7.4. Классификация документов

Наименование документа	Описание
Подлинник	Документ, оформленный подлинными установленными подписями и выполненный на любом материале, допускающем многократное воспроизведение с него копии (дубликата)
Дубликат	Документ, являющийся копией подлинника, обеспечивающий идентичность воспроизведения подлинника, выполняемый на любом материале, позволяющем снимать копии
Копия	Документ, выполненный способом, обеспечивающим его идентичность с подлинником (дубликатом), и предназначенный для непосредственного использования при сопровождении и эксплуатации программы

7.3. Основные стадии и этапы разработки программ и программной документации

Государственный стандарт ГОСТ 19.102—77 устанавливает следующие стадии разработки программной документации:

1) техническое задание;

2) эскизный проект;

3) технический проект;

4) рабочий проект;

5) внедрение.

Рассмотрим подробнее каждую из стадий.

1. Стадия «Техническое задание». Этапы и содержание работ на этой стадии представлены в табл. 7.5.

Таблица 7.5. Работы, выполняемые на стадии «Техническое задание»

Этапы работ	Содержание работ
Обоснование необходимости разработки программы	Постановка задачи. Сбор исходных материалов. Выбор и обоснование критериев эффективности и качества разрабатываемой программы. Обоснование необходимости проведения научно-исследовательских работ
Научно-исследовательские работы	Определение структуры входных и выходных данных. Предварительный выбор методов решения задач. Обоснование целесообразности применения ранее разработанных программ. Определение требований к техническим средствам. Обоснование принципиальной возможности решения поставленной задачи
Разработка и утверждение технического задания	Определение требований к программе. Разработка технико-экономического обоснования разработки программы. Определение стадий, этапов и сроков разработки программы и документации на нее. Выбор языков программирования
Разработка и утверждение технического задания	Определение необходимости проведения научно-исследовательских работ на последующих стадиях. Согласование и утверждение технического задания

Документ «Техническое задание» оформляется в соответствии с ГОСТ 19.106—78 на листах формата А4 и А3 номера листов (страниц) проставляются в верхней части листа над текстом.

Содержание технического задания должно соответствовать ГОCT 19.201—78 и включать следующие разделы:

введение;

основания для разработки;

назначение разработки;

требования к программе или программному изделию;

требования к программной документации;

технико-экономические показатели;

стадии и этапы разработки;

порядок контроля и приемки;

в техническое задание допускается включать приложения.

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

Для внесения изменений или дополнений в техническое задание на последующих стадиях разработки программы или программного изделия выпускают дополнение к нему. Согласование и утверждение дополнения к техническому заданию проводят в том же порядке, который установлен для технического задания.

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

Все разработки программных систем можно разбить на три группы: управляемые потребителем, контролируемые потребителем и независимые от потребителя. В случае управляемой потребителем разработки характеристики области применения задаются ее потребителем; в случае разработки, контролируемой потребителем, характеристики области применения формулируются совместно разработчиком и потребителем; в случае независимой от потребителя разработки вся ответственность за выбор характеристик области применения ложится на.разработчика.

В разделе «Основания для разработки» должны быть указаны:

документ (документы), на основании которых ведется разработка;

организация, утвердившая этот документ, и дата его утверждения;

наименование и (или) условное обозначение темы разработки. В разделе «Назначение разработки» должно быть указано функциональное и эксплуатационное назначение программы или программного изделия.

Раздел «Требования к программе или программному изделию» должен содержать следующие подразделы:

требования к функциональным характеристикам;

требования к надежности;

условия эксплуатации;

требования к составу и параметрам технических средств;

требования информационной и программной совместимости;

требования к маркировке и упаковке;

требования к транспортированию и хранению;

специальные требования.

В подразделе «Требования к функциональным характеристикам» должны быть указаны требования к составу выполняемых функций, организации входных и выходных данных, временным характеристикам и т. д.

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

В подразделе «Требования к надежности» должны быть указаны требования к обеспечению надежного функционирования программы (контроль входной и выходной информации, описание последствий возможных отказов программных функций, обеспечение устойчивого функционирования, время восстановления после отказа и т. д.). При необходимости должна обеспечиваться защита программ и данных.

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

Необходимый состав технических средств (конфигурация системы), с указанием их основных технических характеристик приводится в подразделе «Требования к составу и параметрам технических средств».

В подразделе «Требования к информационной и программной совместимости» должны быть указаны требования к информационным структурам на входе и выходе и методам решения, исходным кодам, языкам программирования и программным средствам, используемым программой. Могут также указываться протоколы межмашинного и сетевого обмена данными, стандарты протоколов формализации данных и управления терминалами, стандарты и форматы сообщений, протоколы транзакций, протоколы запросов данных, стандарты представления данных, требования к системам управления базами данных и операционным системам.

В подразделе «Требования к маркировке и упаковке» в общем случае указывают требования к маркировке программного изделия, варианты и способы упаковки.

В подразделе «Требования к транспортированию и хранению» должны быть указаны для программного изделия условия транспортирования, места хранения, условия хранения, условия складирования, сроки хранения в различных условиях.

В разделе «Требования к программной документации» должен быть указан предварительный состав программной документации и при необходимости специальные требования к ней,

В разделе «Технико-экономические показатели» должны быть указаны: ориентировочная экономическая эффективность, предполагаемая годовая потребность, экономические преимущества разработки по сравнению с лучшими отечественными и зарубежными образцами или аналогами.

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

В разделе «Порядок контроля и приемки» должны быть указаны виды испытаний и общие требования к приемке работы. Целесообразно зафиксировать важнейшие характеристики программы в некоторой количественной или иной достаточно просто проверяемой форме, с тем чтобы можно было установить степень соответствия готового продукта принятым техническим условиям.

Возможны следующие пути представления результатов разработки:

1) в форме программной документации;

2) в форме конструкторской документации на программное изделие;

3) в форме программного изделия.

В приложениях к техническому заданию при необходимости приводят:

перечень научно-исследовательских и других работ, обосновывающих разработку;

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

другие источники разработки.

2. Стадия «Эскизный проект». Основные этапы и содержание работ на этой стадии приведены в табл. 7.6..

Таблица 7.6. Работы, выполняемые íà стадии Эскиэный проект»

Этапы работ	Содержание работ
Разработка эскизного проекта Утверждение эскизного проекта	Предварительная разработка структуры входных и выходных данных. Уточнение методов решения задачи. Разработка общего описания алгоритма решения задачи. Разработка технико-экономического обоснования. Разработка пояснительной записки Согласование и утверждение эскизного проекта

Полный объем работы по эскизному проектированию и конкретное содержание этой стадии зависят от сложности разрабатываемой программной системы. Результатом проектирования является достаточно полное описание архитектуры системы. Это описание часто делается на нескольких уровнях детализации, начиная с верхнего уровня — общесистемного описания. На верхнем уровне выделяются важнейшие подсистемы—программные, комплексы, им присваиваются имена, устанавливается взаимодействие между этими комплексами и обмен данными между ними, определяются функции каждой такой подсистемы (модуля), которые получаются путем декомпозиции программных функций системы. Затем для каждой из выделенных подсистем может выполняться аналогичная процедура, выделяются модули следующего уровня и т. д. Нижние уровни этой иерархии разрабатываются и описываются на следующей стадии проектирования. В конечном итоге система оказывается организованной иерархически, расслоенной на уровни, каждый из которых представляет собой совокупность взаимосвязанных модулей. При таком построении можно упростить анализ системы, делая уровни максимально независимыми друг от друга, оно получило название нисходящего проектирования. Наряду с нисходящим проектированием на практике используется в какой-то степени противоположный подход — восходящее проектирование. Более подробно вопросы проектирования программ будут рассмотрены выше.

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

Результаты эскизного проектирования отображаются в документе «Пояснительная записка к эскизному проекту:», оформляемом в соответствии с ГОСТ 19.105—78 и ГОСТ 19.404—79. Этот документ должен содержать следующие разделы:

1) введение;

2) назначение и область применения;

3) технические характеристики;

4) ожидаемые технико-экономические показатели;

5) источники, использованные при разработке;

6) приложение.

В зависимости от особенностей документа отдельные разделы (подразделы) допускается объединять, а также вводить новые разделы (подразделы).

В разделе «Введение» указывают наименование программы и (или) условное обозначение темы разработки, а также документы, на основании которых ведется разработка с указанием организации и даты утверждения.

В разделе «Назначение и область применения» указывают назначение программы и характеризуют область ее применения. Характеристики области применения должны точно соответствовать характеристикам, указанным в техническом задании, но должны быть более подробно описаны с точки зрения функционирования программного комплекса.

Раздел «Технические характеристики» должен содержать следующие подразделы:

постановка задачи на разработку программы, описание применяемых математических методов, при этом основное внимание уделяется соотношениям, связывающим входные и выходные данные, внешним функциям программы; описание допущений и ограничений (при необходимости), связанных с выбранным математическим аппаратом;

описание алгоритма и (или) функционирования программы с обоснованием выбора схемы алгоритма решения задачи, возможные взаимодействия программы с другими программами, отдельно должны быть рассмотрены состав и функции программных подсистем, связи этих подсистем и соглашения о связях, требования к программным интерфейсам;

описание и обоснование выбора метода организации входных и выходных данных;

описание и обоснование выбора состава технических и программных средств на основании проведенных расчетов и (или) анализов, распределение носителей данных.

В разделе «Ожидаемые технико-экономические показатели» указывают технико-экономические показатели, обосновывающие преимущество выбранного варианта технического решения, а также при необходимости ожидаемые оперативные показатели,

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

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

После утверждения пояснительной записки она становится программным документом, правила дублирования учета и хранения которого определяются ГОСТ 19.601—78 и ГОСТ 19.602—78. Последующие стадии и этапы разработки программной системы могут выявить необходимость внесения изменений в ее эскизный проект. Эти изменения должны быть отражены в пояснительной записке эскизного проекта; правила внесения изменений определяются ГОСТ 19.603—78 и ГОСТ 19.604—78.

3. Стадия «Технический проект». Этапы и содержание работ на этой стадии определяются табл. 7.7.

Таблица 7.7. Работы, выполненные на стадии «Технический проект»

Этапы работ

Содержание работ

Разработка технического проекта     Утверждение технического проекта

Уточнение структуры входных и выходных данных. Разработка алгоритма решения задачи. Определение формы представления входных и выходных данных. Определение семантики и синтаксиса языка. Разработка структуры программы. Окончательное определение конфигурации технических средств   Разработка плана мероприятий по разработке и внедрению программ. Разработка пояснительной записки. Согласование и утверждение технического проекта

Содержанием работ на этой стадии является проектирование структуры программного комплекса. Результатом — реализующий заданные функции программный комплекс как иерархически организованная структура программных модулей, заданных своими функциональными спецификациями. Формой представления результатов является документ «Пояснительная записка к техническому проекту». Требования к содержанию и оформлению этого документа определены ГОСТ 19.105—78, ГОСТ 19.404—79. Рассмотрим важнейшие этапы работы на этой стадии. Разработка структуры программной системы заключается в выделении всех программных компонентов по функциональным признакам, определении функциональных спецификаций программных модулей и уточнении внешних функциональных спецификаций системы и структуры входных и выходных данных, определении • операционной среды, языковых средств и конфигурации технических средств.

Термины «программная система», «программная подсистема», «программа», «подпрограмма» определяют функциональные элементы разрабатываемого объекта различных уровней, в то время как термины «программный комплекс», «программный компонент», «программный модуль» (просто модуль) определяют структурные единицы. Связь функциональных и структурных единиц выявляется на стадии технического проектирования в процессе разработки функциональных спецификаций программных модулей. В наиболее простых случаях каждая программа разбивается на ряд модулей.

Спецификации модулей являются их внешними характеристиками и содержат все сведения, необходимые вызывающим модулям.

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

4. Стадия «Рабочий.проект». Содержанием работ на этой стадии является описание программы на выбранном проблемно-ориентированном языке (кодирование), отладка, разработка, согласование и утверждение порядка и методики испытаний, разработка программных документов в соответствии с требованиями ГОСТ 19.101—77, проведение предварительных испытаний (тестирование), корректировка программы и программной документации по результатам испытаний, проведение приемо-сдаточных межведомственных, государственных и других видов испытаний.

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

Отметим, что хотя ЕСПД предусматривает разработку порядка и методики испытаний на стадии «Рабочий проект», работа по подготовке и проведению испытаний фактически начинается уже на стадии «Техническое задание», когда намечается порядок контроля и приемки, и ее целесообразно вести в течение всего процесса проектирования программы.

5. Стадия «Внедрение». Содержанием работ на этой стадии является подготовка и передача программы и программной документации для сопровождения и (или) изготовления, оформления и утверждения акта о передаче программы на сопровождение или изготовление, передача программы в фонд алгоритмов и программ.

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

Важным периодом жизни программы является период, непосредственно следующий за внедрением. Процесс работы над программой во время ее использования по назначению получил название сопровождение. Сопровождение программы включает анализ функционирования, развитие и совершенствование программы, а также внесение изменений в нее с целью устранения ошибок. Поскольку не все ошибки удается обнаружить в процессе отладки и испытаний, то ряд ошибок ловится в процессе решения реальных задач, т. е. на этапе сопровождения. Например, каждая версия операционной системы после сдачи ее в эксплуатацию содержит около 1000 ошибок. На этом же этапе осуществляются различные расширения функций программы, вносятся изменения с целью улучшения или адаптации к конкретным условиям применения и т. д.

Значение сопровождения в жизненном цикле больших программ стало осознаваться специалистами лишь в последние годы, когда выяснилось, что затраты на их сопровождение могут составлять до 60% затрат на программное обеспечение, или 50% общих затрат на вычислительную технику. Жизненный цикл программного обеспечения длится около 5—7 лет, в течение которых требования к нему могут существенно меняться. Различие между большими и малыми программами проявляется не только и не столько в их разработке, сколько в сопровождении.

Большую программу по понятным причинам нельзя переделать заново, но при изменении и дополнении больших программ на стадии сопровождения приходится в какой-то степени повторять все предыдущие стадии разработки, что приводит к большим затратам и множеству ошибок. Типичным является следующее распределение ресурсов для больших систем: 100 чел. в течение 2 лет заняты разработкой программного обеспечения и 35 чел. в течение 8 лет — сопровождением. Один из путей упрощения стадии сопровождения состоит в учете особенностей этого этапа на остальных стадиях разработки программного изделия.

Дата добавления: 2014-12-16