Вопрос 2. Поиск и кодирование (сжатие) данных, кодовые деревья, оптимальные префиксные коды

К одовое дерево – специальный граф, отображающий запись всех возможных K-ичных n-разрядных чисел, используемых в качестве кодовых комбинаций для кодирования сообщений в количестве M = Kⁿ. При этом каждое число отображается одним из узлов графа. Из каждого узла выходит K ветвей, которые связывают этот узел с другими. Количество символов, входящих в число, соответствующее данному узлу, называется его порядком.

Рассмотрим граф для двоичного трехэлементного кода.

Рис. 13 Кодовое дерево двоичного трехэлементного кода

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

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

Оптимальному коду всегда соответствует двоичное дерево, в котором любая вершина, не являющаяся листом, имеет двоих детей. Это свойство позволяет легко прийти к выводу о том, что дерево оптимального префиксного кода для файла, в котором используются все символы из некоторого множества C и только они, содержит ровно |C| листьев, по одному на каждый символ, и ровно |C| − 1 узлов, не являющихся листьями.

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

Алгоритм построения кода Хаффмана:

1. Сортируем все символы алфавита в порядке убывания или возрастания вероятности их появления в тексте.

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

3. Прослеживаем путь к каждому листу дерева, помечая направление – направо -1, налево – 0, получаем кода Хаффмана для каждого символа.

Алгоритм Шеннона-Фано

1.Выписываются в ряд все символы в порядке возрастания вероятности появления их в тексте.

2. Последовательно делим множество символов на 2 подмножества так, чтобы сумма вероятностей появления символов одного подмножества была примерно равна сумме вероятностей появления символов другого. Для левого подмножества каждому символу приписываем 0, правого – 1. Дальнейшее разбиение осуществляется рекурсивно до тех пор, пока в подмножествах не останется по 1 элементу. Алгоритм Хаффмана – снизу-вверх, Фанно-Шеннона – сверху-вниз.

Вопрос 3. Документирование процесса производства ПО. Единая система программной документации ЕСПД, состав. Техническое задание на разработку ПО, его содержание. CASE-средства автоматизации документирования.

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

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

1. Техническое задание

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

2. Эскизный проект (прототип)

Эскиз – прототип будущего программного изделия (первый виток в спирали), который определяется сложностью программного изделия и представляет собой предварительную разработку структуры программного изделия, его входных и выходных данных. При этом выполняется обязательное описание алгоритмов решения задачи, подготавливается технико-экономическое обоснование и выполняется разработка пояснительной записки эскиза проекта с дальнейшим его утверждением ГОСТ 19.105–78, ГОСТ 19.404–79.

3. Технический проект

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

4. Рабочий проект

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

5. Внедрение

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

CASE-средства автоматизации документирования

(При ООП подходе) Rational Rose интегрируется со средством SoDA - для документирования проектов.

(При структурном подходе) BPWin и ERWin интегрируются со средством CrystalReports, которое позволяет создавать отчеты.

Также существует динамическая документация, например, когда в модель вносят изменения, то изменения тут же вносятся и в отчет.

Билет 7