Понятие коллекции. Классификация

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

Продолжить читать "Коллекции"

Данный метод сжатия данных был впервые обнародован в 1977г. Алгоритм на удивление прост. Если в двух словах, то LZW-сжатие заменяет строки символов некоторыми кодами. Это делается без какого-либо анализа входного текста. Вместо этого при добавлении каждой новой строки символов просматривается таблица строк. Сжатие происходит, когда код заменяет строку символов. Коды, генерируемые LZW-алгоритмом, могут быть любой длины, но они должны содержать больше бит, чем единичный символ. Первые 256 кодов (когда используются 8-битные символы) по умолчанию соответствуют стандартному набору символов. Остальные коды соответствуют обрабатываемым алгоритмом строкам. Простая программа, приведенная ниже, работает с 12-битными кодами. Значения кодов 0 – 255 соответствуют отдельным байтам, а коды 256 – 4095 соответствуют подстрокам. Каждый раз, когда генерируется новый код, новая строка добавляется в таблицу строк. LZW постоянно проверяет, является ли строка уже известной, и, если так, выводит существующий код без генерации нового.

Продолжить читать "Алгоритм сжатия LZW"

Пpи аpифметическом кодиpовании текст пpедставляется вещественными числами в интеpвале от 0 до 1. По меpе кодиpования текста, отобpажающий его интеpвал уменьшается, а количество битов для его пpедставления возpастает. Очеpедные символы текста сокpащают величину интеpвала исходя из значений их веpоятностей, опpеделяемых моделью. Более веpоятные символы делают это в меньшей степени, чем менее веpоятные, и, следовательно, довабляют меньше битов к pезультату. Пеpед началом pаботы соответствующий тексту интеpвал есть [0; 1). Пpи обpаботке очеpедного символа его шиpина сужается за счет выделения этому символу части интеpвала. Hапpимеp, пpименимк тексту “eaii!” алфавита a,e,i,o,u,! модель с постоянными веpоятностями.

Символ          Веpоятность             Интеpвал

a                          .2                         [0.0; 0.2)

e                          .3                        [0.2; 0.5)

i                           .1                        [0.5; 0.6)

o                           .2                        [0.6; 0.8)

u                           .1                        [0.8; 0.9)

!                           .1                        [0.9; 1.0)

Продолжить читать "Арифметическое кодирование"

Метод “стопка-книг“ не требует предварительного анализа входного файла и используется преимущественно в системах передачи данных. У кодировщика и декодировщика в памяти имеется кодовая таблица, в первой колонке которой перечислены символы в произвольном порядке, а во второй – коды, рассчитанные по методу Шеннона-Фано в порядке возрастания длины. При поступлению к кодировщику очередного символа от источника он просматривается в первой колонке таблицы и в канал передается его код. После этого символ перемещается в первую строку таблицы, где ему будет соответствовать самый короткий код. Декодировщик при получении кода, находит символ и также перемещает его в верхнюю строку таблицы. Таким образом, таблицы оказываются одинаковыми. В результате работы алгоритма часто используемые символы будут группироваться в верхней части таблицы, а редко используемые – “оседать“ в нижних строках. Для передачи текста в целом будет использоваться меньшее число кодовых символов, чем при равномерном кодировании. И чем выше избыточность, тем эффективнее будет алгоритм.

Продолжить читать "Метод “стопка-книг“"

Допyстим нам нyжно закодиpовать некотоpое сообщение: AABCDAABCА

Кодирование проводим в несколько этапов.

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

A – 5               5/10 = 0.5

B – 2                2/10 = 0.2

C – 2                2/10 = 0.2

D – 1               1/10 = 0.1

Продолжить читать "Метод Шеннона-Фано"

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

Продолжить читать "Равномерное и неравномерное кодирование"

Введение

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

Проблема измерения количества информации

Измерение информации в быту (информация как новизна). Вы получили какое-то сообщение (например, прочитали статью в любимом журнале). В этом сообщении содержится какое-то количество информации. Как оценить, сколько информации вы получили? Другими словами, как измерить информацию? Можно ли сказать, что чем больше статья, тем больше информации она содержит? Разные люди, получившие одно и то же сообщение, по-разному оценивают количество информации, содержащееся в нем. Это происходит оттого, что знания людей об этих событиях, явлениях до получения сообщения были различными. Поэтому те, кто знал об этом мало, сочтут, что получили много информации, те же, кто знал больше, чем написано в статье, скажут, что информации не получили вовсе. Таким образом, количество информации в сообщении зависит от того, насколько ново это сообщение для получателя. При таком подходе непонятно, по каким критериям можно ввести единицу измерения информации. Следовательно, с точки зрения информации как новизны мы не можем оценить количество информации, содержащейся в научном открытии, новом музыкальном стиле, новой теории общественного развития.

Продолжить читать "Алгоритмы кодирования и сжатия данных"

Представление множеств

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

Основными структурами данных для хранения простых множеств являются массивы. Массивы могут быть одномерными и многомерными (наиболее распространены двумерные, или матрицы). Последовательность элементов одномерного массива имеет вид: A={1,2,3,4}. Произвольную последовательность элементов массива можно записать как (1, 2, 3). Для операций над элементами множеств могут привлекаться вспомогательные переменные. Часто используются указатели массива: l – левая граница, r – правая граница. В процессе работы алгоритма значение l увеличивается, а r – уменьшается.

Продолжить читать "Алгоритмы, основанные на простых множествах"

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

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

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

Продолжить читать "Сложность проблем"

Обычно алгоритмы классифицируют в соответствии с их временной сложностью. Можно выделить следующие их типы:

1. Постоянный – сложность оценивается как O(1).

2. Линейный – оценка равна O(n).

3. Квадратный – O(n²)

4. Кубический, полиноминальный – O(n³),O(n^m).

5. Экспоненциальный – O(t^p(n)), t- константа, p(n) – некоторая полиномиальная функция.

6. Факториальный - O(n!). Обладает наибольшей временной сложностью среди всех известных типов.

Продолжить читать "Классификация по сложности"