Программы сжатия. Кореляционная связь. Динамическое программирование

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ

КАФЕДРА ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ

РЕФЕРАТ

Выполнил

Ляшенко

Проверил

Волощук

МАРИУПОЛЬ 2007

СОДЕРЖАНИЕ

1. Программы сжатия информации…………………………… 3

   1. WinRar 3.5………………………………………………… 5

2. Корреляционная связь…………………………………………10

3. Динамическое программирование……………………………11

Список использованной литературы

1. Программы сжатия информации¹

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

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

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

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

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

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

Степень сжатия информации зависит от нескольких причин:

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

• Во-вторых, большое значение имеет метод сжатия.

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

На сегодняшний день наиболее распространенными являются четыре архиватора — WinRar, WinAce, 7Zip и WinZip. Что касается последней программы, она не выдерживает никакой критики.

1.1. WinRar 3.5

Данный архиватор может ассоциироваться со следующими типами файлов: RAR, ZIP, CAB, ARJ, LZH, ACE, 7-Zip, TAR, GZip, UUE, BZ2, JAR, ISO.

Программа поддерживает файлы практически неограниченного размера (до 8,589,934,591 Гб). Правда, для работы с файлами размером более 4 Гб вам необходимо работать в файловой системе NTFS.

При выборе оптимальных настроек для сжатия необходимо учитывать несколько моментов:

• Несмотря на то, что WinRAR поддерживает формат ZIP, в большинстве случаев рекомендуется выбирать RAR. Это обеспечит более высокий уровень сжатия. Вы можете сжать файлы в ZIP, если вы не уверены, что на компьютере, на котором будут распакованы файлы, будет установлена программа, с помощью которой можно будет распаковать файлы в формате RAR.

• Необходимо определиться, какой метод компрессии лучше всего использовать. Чем выше степень сжатия, тем больше времени уйдет на архивацию, поэтому тут нужно учитывать, для каких целей архивируются данные. Если это долгосрочное хранение, конечно же, имеет смысл подождать и получить архив с максимальной степенью сжатия, если же вам просто необходимо отослать несколько документов по почте, вам подойдет и обычная (Normal) степень сжатия.

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

Если необходимо создать большой архив, на это может уйти довольно много времени. WinRar позволяет определить, сколько примерно времени уйдет на выполнение того или иного задания. Для этого предназначена опция Benchmark and hardware test. Еще одна причина, по которой можно использовать эту опцию — определение возможных ошибок, которые могут возникнуть при архивации на компьютере той или иной конфигурации по причине аппаратного сбоя.

Среди других настроек WinRar'a можно отметить возможность создания самораспаковывающихся архивов с указанием пути распаковки. Такие файлы не требуют наличия на компьютере, на котором их планируется разархивировать, программы-архиватора. Подобные архивы получили название SFX-archives. Их недостатком по сравнению с обычными архивными файлами является больший размер, так как они, кроме собственно запакованных файлов, содержат также исполнительный EXE-модуль.

Cодержимое RAR-архива можно сделать невидимым. Для этого в настройках программы, в окне Archiving with Password нужно установить флажок напротив строки Encrypt File Names.

Можно также установить пароль на открытие архива.

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

Для того чтобы свести к минимуму вероятность потери данных, при создании архивов WinRar рекомендуется использовать опцию Put Recovery Record (этот флажок можно найти на вкладке General окна создания архива).

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

Кроме этого в WinRar, можно уменьшить вероятность повреждения RAR-архива, указав при его создании размер информации для восстановления. Для этого нужно выполнить команду Commands > Protect Archive From Damage в окне Winrar. При этом объем Recovery Record не может превышать десяти процентов от общего размера архива.

Для восстановления поврежденных RAR-архивов необходимо выбрать нужный файл в окне WinRar и выполнить команду Tools > Repair.

WinRAR умеет встраиваться в контекстное меню, причем поддерживает не только меню Проводника, но и других программ, например популярного файлового менеджера Total Commander. Это дает возможность быстро архивировать файлы, используя настройки по умолчанию и не открывая для этого окно программы. Кстати, настройки по умолчанию можно изменить, в соответствии с тем, какие требования вы предъявляете к своим архивам. Сделать это можно, открыв окно WinRar и выполнив команду Options > Settings. В этом окне нужно перейти на вкладку Compression и нажать кнопку Create Default. Настройки, заданные в этом окне и будут использоваться для быстрой архивации.

Если же требуется изменить настройки архивации, это тоже можно сделать при помощи контекстного меню. Для этого нужно выбрать команду Add to Archive… Тут можно установить формат и степень сжатия, указать имя архива и выбрать другие параметры архивации.

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

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

2. Корреляционная связь

Во многих задачах требуется установить и оценить зависимость изучаемой случайной величины У от одной или нескольких других величин. Рассмотрим сначала зависимость У от одной случайной (или не случайной) величины Х, а затем от нескольких величин.

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

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

Например если У зависит от случайных факторов З₁, З₂, В₁, В₂, а Х зависит от случайных факторов З₁, З₂, И₁, то между У и Х имеется статистическая зависимость, так как среди случайных факторов есть общие, а именно: З₁ и З₂.

Статистической называют зависимость, при которой изменение одной из величин влечет изменение распределения другой. В частности, статистическая зависимость проявляется в том, что при изменении одной из величин изменяется среднее значение другой; в этом случае статистическую зависимость называют корреляционной.

Приведем пример случайной величины У, которая не связана с величиной Х функционально, а связана корреляционно. Пусть У — урожай зерна, Х — количество удобрений. С одинаковых по площади участков земли при равных количествах внесенных удобрений снимают различный урожай, т. е. У не является функцией от Х. Это объясняется влиянием случайных факторов. Вместе с тем, как показывает опыт, средний урожай является функцией от количества удобрений, т. е. У связан с Х корреляционной связью.

1. Динамическое программирование

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

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

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

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

В последствии Е.С.Вентцель изменил формулировку основного принципа оптимальности динамического программирования, которая немного отличается от формулировки предложенной Р. Беллманом.

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

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

Основное требование – «Процесс управления должен быть без обратной связи, т. е. управление на данном шаге не должно оказывать влияния на предшествующие шаги».

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

Математически, сформулированный им принцип оптимальности, Беллман записал следующим выражением:

f_n-i(S_i)=optimum[R_i+1(S_i, U_i+1)+f_n-(i+1)(S_i+1)] (1)

U_i+1 (i=0, 1, 2, …,n-1),

где

U_i = (U_i⁽¹⁾; U_i⁽²⁾; … ; U_i^(m)) – решение (управление), выбранное на i – шаге;

S_i = (S_i⁽¹⁾; S_i⁽²⁾; … ;S_i^(m)) - состояние системы на i – ом шаге;

R_i = непосредственный эффект, достигаемый i- ом шаге;

f_n-i = оптимальное значение эффекта, достигаемого за n-i шагов;

n = количество шагов или этапов в решаемой задаче.

«Optimum» в выражении (1) означает максимум или минимум в зависимости от условия задачи.

Все вычисления, дающие возможность найти оптимальное значение, достигаемого за n шагов, f_n(S₀), проводятся по формуле (1), которая носит название основного функционального уравнения Беллмана или рекуррентного соотношения.

При вычислении очередного значения функции f_n-i используются значения функции f_n-(i+1), полученное на предыдущем шаге, и непосредственное значение эффекта R_i+1(S_i, U_i+1), достигаемого в результате выбора решения U_i+1 при заданном состоянии системы S_i. Процесс вычисления значений функции f_n-i (i=[0..n-1]) осуществляется при естественном начальном условии f₀(S_n)=0, которое означает, что за пределами конечного состояния системы эффект равен нулю.

Отыскания оптимального решения задачи методом динамического программирования осуществляется на основе функционального уравнения (1) по следующей схеме:

1. процесс вычисления значений функции f_n-i (i=0,1,…n-1) осуществляется при естественном начальном условии f₀(S_n) = 0, которое означает, что за пределами конечного состояния системы эффект равен нулю;

2. записать функциональное уравнение для последнего состояния процесса – ему соответствует i=n-1:

f₁(S_n-1) = optimum[R_n (S_n-1, U_n) + f₀(S_n)];

3. найти R_n (S_n-1,U_n) из дискретного набора его значений при некоторых фиксированных S_n-1 и U_n из соответствующих допустимых областей (так как f₀(S_n) =0), то

f₁(S_n-1)=optimum[R_n(S_n-1, U_n)],

следовательно, в результате первого шага известно решение U_n и соответствующее значение функции f₁(S_n-1);

4. уменьшить значение «i» на единицу и записать соответствующее функциональное уравнение для следующего шага. При i=n-k (k=2,3, … , n) оно будет иметь вид:

f_k(S_n-k) = optimum[R_n-k+1(S_n-k, U_n-k+1) + f_k-1(S_n-k+1)]; (2)

U_n-k+1

5. найти условно-оптимальное решение на основе выражения (2);

6. проверить, чему равно «i». Если «i=0», расчёт условно-оптимальных решений закончен, при этом найдено оптимальное решение задачи для первого состояния процесса. Если «i?0», перейти к выполнению пункта 4;

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

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

Список использованной литературы

1. Ермольев Ю. М., Ляшко И. И. Математические методы исследования операций. — К.: Вища школа, 1979 г.

2. Ермаков С. М. Статистическое моделирование. — М.: Наука, 1982 г.

3. Глушаков С. В. Персональный компьютер. — Х.: Фолио, 2001 г.

4. Кини Р. Л. Принятие решений при многих критериях: предпочтения и замещения. — М.: Радио и связь, 1981 г.

5. Линейное и нелинейное программирование / Под ред. И. Н. Ляшенко. — К.: Вища школа, 1975 г.