21. Кодирование

Алфавитное кодирование.

Алфавитное кодирование- кодирование при котором символы некоторого первичного алфавита кодируются комбинациями символов другого алфавита

Алфавитное (или побуквенное) кодирование задается схемой(или таблицей кодов) s:

 ai Î A,  bi Î В*.

 Множество кодов букв V:={bi} называетсямножеством элементарных кодов.Алфавитное кодирование пригодно для любого множества сообщенийS:F:A*®B*,        a_il...a_ik=aÎA*,        F(a) :=bi1…bik.

Неравенство Макмиллана.

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

В качестве кодирующего алфавита часто рассматривается множество {0,1} — так называемый двоичный или бинарный алфавит.

конкатенацию кодовых слов, соответствующих каждому символу этого слова.

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

Префиксным кодом называется алфавитный код, в котором ни одно из кодовых слов не является префиксом никакого другого кодового слова. Любой префиксный код является разделимым.

Теоремы Шеннона (первая, обратная).

Если источник сообщения имеет энтропию Н бит/букву, а канал связи обладает пропускной способностью Сбит/сек, то всегда можно найти такой способ кодирования, который обеспечивает передачу букв по каналу со средней скоростью,

Vср=(С/Н-Е) букв /сек

Е – сколь угодно малая величина.

Обратная теорема. Передача букв по каналу со средней скоростью больше, чем С/Н невозможна, следовательноVmax=С/Н

Алгоритмы Фено и Хаффмена.

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

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

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

3. Прослеживаем путь к каждому листу дерева, помечая направление к каждому узлу (например, направо - 1, налево - 0) . Полученная последовательность дает кодовое слово, соответствующее каждому символу

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

Кодирование Шеннона — Фано— алгоритм префиксного неоднородного кодирования. Относится к вероятностным методам сжатия (точнее, методам контекстного моделирования нулевого порядка). Подобно алгоритму Хаффмана, алгоритм Шеннона — Фано использует избыточность сообщения, заключённую в неоднородном распределении частот символов его (первичного) алфавита. Алгоритм вычисления кодов Шеннона — Фано

Код Шеннона — Фано строится с помощью дерева. Построение этого дерева начинается от корня. Всё множество кодируемых элементов соответствует корню дерева (вершине первого уровня).

Пример кодового дерева 

Исходные символы:

• A (частота встречаемости 50)

• B (частота встречаемости 39)

• C (частота встречаемости 18)

• D (частота встречаемости 49)

• E (частота встречаемости 35)

• F (частота встречаемости 24)

Кодовое дерево

Полученный код: A — 11, B — 101, C — 100, D — 00, E — 011, F — 010.

21. Моделирование и проектирование информационных систем

22. Задачи и функции информационной системы.

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

Задачи второй группы - задачи информатизации

общества "вглубь".

Для решения поставленных задач ИС должна выполнять следующие функции:

- отбор сообщений из внутренней и внешней среды, необходимых для реализации основной деятельности;

- ввод информации в ИС;

- хранение информации в памяти ИС, ее актуализация и поддержание целостности;

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

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

Функциональное моделирование IDEF0: основные определения и положения.

Общая методология IDEFсостоит из трех частных методологий моделирования, основанных на графическом представлении систем:

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

• IDEF1 применяется для построения информационной модели, отображающей структуру и содержание информационных потоков, необходимых для поддержки функций системы;

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

Инструментальная среда BPwin.

BPwinподдерживает три методологии моделирования: функциональное моделирование (IDEF0); описание бизнес- процессов (IDEF3); диаграммы потоков данных (DFD).

При создании новой модели возникает диалог, в котором следует указать, будет ли создана модель заново или она будет открыта из файла либо из репозитория ModelMart, затем внести имя модели и выбрать методологию, в которой будет построена модель.

Как было указано выше, BPwinподдерживает три методологии —IDEF0,IDEF3 иDFD, каждая из которых решает свои специфические задачи. ВBPwinвозможно построение смешанных моделей, т. е. модель может содержать одновременно диаграммы какIDEF0, так иIDEF3 иDFD. Состав палитры инструментов изменяется автоматически, когда происходит переключение с одной нотации на другую.

Модель в BPwinрассматривается как совокупность работ, каждая из которых оперирует с некоторым набором данных. Работа изображается в виде прямоугольников, данные — в виде стрелок.

Наиболее удобным языком моделирования бизнес- процессов является IDEF0, где система представляется как совокупность взаимодействующих работ или функций. Такая чисто функциональная ориентация является принципиальной — функции системы анализируются независимо от объектов, которыми они оперируют. Это позволяет более четко смоделировать логику и взаимодействие процессов организации.

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