Обратимость сжатия

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

•.JPG для графических данных;

•.МРО для видеоданных;

•.МР3 для звуковых данных.

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

•.GIF,.TIF,.PCX и многие другие для графических данных;

•.AVI для видеоданных;

•.ZIP,.АRJ,.RAR,.LZH,.LH,.САВ и многие другие для любых типов данных.

25.Алгоритмы сжатия :

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

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

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

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

26. Программные средства сжатия данных.

Для сжатия данных используются программы, работающие в основном с архивами Rar, Zip, 7z. Это соответственно WinRar, WinZip, 7zip – популярные программы. Некоторые архивы может читать также непосредственно ОС Windows.

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

Программа 7Zip на данный момент доминирует по плотности сжатия, работает с большинством популярных форматов и бесплатна. При создании архива способна защитить его паролем, разбить на тома и сделать непрерывным.

WinZip – менее популярна, чем WinRar и 7Zip, однако имеет почти такие-же высокие показатели работы. При создании архива способна защитить его паролем, разбить на тома, однако нельзя гибко настроить сжатие и отсутствуют некоторые необходимые функции, имеющиеся в WinRar и 7Zip (например непрерывное сжатие)

27.Базовые требования к диспетчерам архивов. WinRAR. WinArj. WinZip.

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

• извлечение файлов из архивов;

• создание новых архивов;

• добавление файлов в имеющийся архив;

• создание самораспаковывающихся архивов – архив создается как самостоятельная программа и может извлекаться без архиватора;

• создание распределенных архивов на носителях малой емкости – разбиение архива на тома;

• тестирование целостности структуры архивов;

• полное или частичное восстановление поврежденных архивов;

• защита архивов от просмотра и несанкционированной модификации – шифрование содержимого файлов и даже полное шифрование (без пароля архив даже не откроется).

28.Программные средства уплотнения носителей. Теоретические основы.

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

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

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

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

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

29.Алгоритмизация. Эволюция языков программирования.

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

Свойства алгоритма:

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

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

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

· Завершаемость (конечность) — при корректно заданных исходных данных алгоритм должен завершать работу и выдавать результат за конечное число шагов.^{[ источник не указан 1119 дней ]} С другой стороны, вероятностный алгоритм может и никогда не выдать результат, но вероятность этого равна 0.

· Массовость (универсальность). Алгоритм должен быть применим к разным наборам исходных данных.

· Результативность — завершение алгоритма определёнными результатами.

· Алгоритм содержит ошибки, если приводит к получению неправильных результатов либо не даёт результатов вовсе.

· Алгоритм не содержит ошибок, если он даёт правильные результаты для любых допустимых исходных данных.

Существуют несколько видов алгоритмов. Выделим самые основные виды:

Линейные – все команды выполняются последовательно

Разветвляющийся – выбор одной из последовательности команд в зависимости от условия

Циклический – повторяется последовательность команд, пока истинно какое-либо условие.

Воспомогательный – замена большой серии команд короткой фразой

Структурная блок-схема, граф-схема алгоритма – наглядное изображение алгоритма, предназначенное для человека.

Эволюция языков программирования:

По уровню языки программирования развивались (от раннего машинного кода до поздних языков высокого уровня) в течении V поколений, проходя следующие этапы:

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

2.Язык Ассемблера – первый язык, использующий символы. Появился транслятор, переводящий команды Ассемблера в машинные. Понадобилось расширение информатики и ее дисциплин. II поколение, по прежнему самый низкий уровень

3. Языки высокого уровня – универсальные, почти независимые от типа ЭВМ. Добавились возможности использовать переменные, записывать сложные выражения, использование и создание новых типов и библиотек, расширилось число встроенных типов и операций. Появляются среды программирования языков, включающие редактор (создание программы), отладчик (поиск ошибок) и др. инструменты для данного языка. Популярные языки – C, Basic, Pascal, … III поколение языков, слабо зависящих от конкретной ЭВМ, высокий уровень (многие команды выполняют несколько машинных инструкций)

4. Проблемно-ориентированные языки – решение узкого круга задач – языки для экономических задач (COBOL), для задач реального времени (Modula-2, Ada) и т.д. Языки запросов систем управления базами данных (QBE, SQL).

5. Объектно-ориентированные языки – языки, поддерживающие простое создание множества однотипных объектов (создание экземпляров по встроенным или подключаемым классам), наследование (несколько классов имеют один общий класс). На данный момент большинство приложений созданы на объектно-ориентированных языках (C++, C#, Basic, Delphi…). IV поколение языков - использование процедур и функций позволило выполнять большие схожие группы команд одной фразой.

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

7. Множество нестандартных и мощных технологий <описание, пример> – прототипные языки (изменение структуры уже созданных объектов по отдельности, что недоступно в обычных языках, Javascript), динамические языки (анализ и компиляция «на лету», Python), скриптовые языки (позволяет использовать одной программой неограниченное множество модулей или объектов, построенных по сценарию; сверхпопулярны, Python) и др.

Можно выделить новейшие языки V поколения, к которым относиться языки с логическим программированием – программы, созданные на этих языках, способны самостоятельно подбирать решение для задачи.

30.Переменные и константы. Операторы и операции. Условные операторы.

Константа — это составная часть программы; объект, имеющий значение. Константу нельзя изменить во время выполнения программы. В программировании с константой можно связать имя, например к числу 3,14 прировнять Pi. Константе необязательно указывать тип данных, поскольку константа в программе не меняется.

Переменная -это составная часть программы, имеющая значение и название. Переменную можно изменять во время выполнения программы. При этом переменная имеет диапазон значений, зависящий от емкости переменной – чем больше памяти занимает переменная, тем больше/точнее будет ее значение. К переменной нужно обращаться по имени, которое она получила при создании. Например, возможно создать переменную Х со значением 5, а затем изменить на 4 и потом 10 и т.д.

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

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

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

Операции бывают унарны (применимы к одному аргументу, отрицание), бинарны (применимы к двум аргументам, сложение, вычитание, …) и тернарны (применимы к трем аргументам, логические).

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

Оператор с одной ветвью может выполнить/пропустить единственный блок инструкций, сверяясь с условием

Оператор с двумя ветвями выполнит первый из двух блоков если условие истинно и второй блок если условие ложно.

Оператор с несколькими ветвями проверяет равенство условия нескольким значениям, и выполняет блок, следующий за совпадающим значением. Может содержать блок, который выполнится, если условие не равно ни одному из значений.

31.Циклы. Операции с символьными переменными.

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

- Условие – от истинности которого зависит, будет ли выполняться тело цикла.

- Тело – набор инструкций, выполняемых циклом

- Инициализатор – в цикле For – создает или использует переменную, приравнивая к указанному значению.

- Изменение счетчика – в цикле For – изменяет указанным способом переменную

Выделяют следующие виды циклов:

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

Циклы с предусловием/постусловием – тело выполняется до тех пор, пока истинно условие. Условие проверяется перед/после выполнения тела цикла.

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

Цикл со счетчиком – наиболее популярен цикл for, компактно и логично сочетающий инициализацию, условие и изменение одной или нескольких переменных. В языке С++ выглядит так:

For (инициализация; условие; изменение счетчика)

{

Тело цикла

};

Имеет похожую структуру в других языках программирования. Обычно в инициализации, условии и изменении используют одну и ту-же переменную. Пример цикла for в c++: цикл, который выполняется пока a меньше 5, будет выглядеть так:

For(a=1; a<5; a = a + 1)

{

Тело цикла

};

Данный цикл выполниться четыре раза (при а = 1,2,3,4).

Операции с символьными переменными

Символьный тип (Сhar) — простой тип данных, предназначенный для хранения одного символа (управляющего или печатного) в определённой кодировке. Может являться как однобайтовым (для стандартной таблицы символов), так и многобайтовым (к примеру, для Юникода). Основным применением является обращение к отдельным знакам строки. Любой символ имеет номер в некой таблице символов (ANSI, Unicod)

Строка – переменная, состоящая из нескольких символов. В некоторых языках является массивом символов с завершающим нулевым символом «\0».