В.Д. Валединский - Избранные главы лекций по программированию (1114957)
Текст из файла
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТимени М. В. ЛОМОНОСОВАМеханико-математический факультетИзбранные главы лекцийпо программированиюЛектор — В. Д. ВалединскийII курс, 3 семестр, поток математиковМосква, 2003 г.Оглавление1.....333442.Файловые системы2.1. Файловая система FAT . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.2. Файловая система EXT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.3. NTFS (New Technology File System) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .55793.Эффективные алгоритмы сортировок массивов3.1. Простейшие сортировки .
. . . . . . . . . . . . . . .3.2. Оценка снизу для трудоёмкости сортировок . . . . .3.3. Быстрая сортировка . . . . . . . . . . . . . . . . . .3.4. Пирамидальная сортировка (HeapSort) . . . . . . .3.5. Сортировки за линейное время . . . . . . . . . . . .3.5.1. Сортировка подсчётом . . . . . .
. . . . . . .3.5.2. Поразрядная быстрая сортировка . . . . . ..............................................................................................................................................................................................1011131415161617Сжатие данных4.1. Алгоритм группового кодирования (RLE) .4.2. Алгоритм Хаффмана (Huffman Encoding) .4.3. Адаптивный вариант алгоритма Хаффмана4.4. Арифметическое кодирование . . . .
. . . .4.5. Адаптивное арифметическое кодирование .4.6. Алгоритм LZW (Lempel – Ziv – Welch) . . . .4.6.1. Кодирование . . . . . . . . . . . . . .4.6.2. Декодирование . . . . . . . . . . . . .........................................................................................................................................................................................................................1718192021222323234.Структуры данных1.1.
Данные и их представления. Общие замечания . . . . . . .1.2. Стек (Stack) и дек (Double-End Queue) . . . . . . . . . . . .1.3. Красно-чёрные деревья . . . . . . . . . . . . . . . . . . . . .1.4. Совершенные hash-функции (Perfect Hash Functions, PHF)................2................................................................................................................ВведениеК сожалению, это не полный курс лекций. Однако здесь написано много хорошего, тем более, что разделыо сжатии данных написаны самим лектором.Последняя компиляция: 15 мая 2006 г.Обновления документа — на сайтах http://dmvn.mexmat.net,http://dmvn.mexmat.ru.Об опечатках и неточностях пишите на dmvn@mccme.ru.1. Структуры данных1.1.
Данные и их представления. Общие замечанияДанные нужно как-то представлять, чтобы их было удобно хранить, обрабатывать и передавать. Будем считать, что доступ к данным реализуется посредством объектов — сущностей, которые хранят данные и реализуютдействия над ними. При этом объект может представлять собой чёрный ящик с той точки зрения, что мы незнаем, как он устроен изнутри.
Такой подход хорошо реализуется на C++ с использованием классов1 .При построении любого объекта начинать следует с разработки интерфейса, который обязательно содержит••••МетодыМетодыМетодыМетодыдля создания объекта и его инициализациидоступа к данным объектадля опроса состояния объектадля удаления объекта и освобождения связанной с ним памятиЗдесь слово метод употреблено в том контексте, в котором оно используется в C++ , а именно, подразумевается функция, принадлежащая некоторому классу. Таким образом, объект — это множество данных M cоперациями над ними. Рассмотрим некоторые представления данных, которые могут быть полезны для нашихзадач.1.2. Стек (Stack) и дек (Double-End Queue)Образно говоря, стек представляет собой стопку книг. Мы можем положить очередную книгу в стопку толькосверху, убрать из стопки можно только самую верхнюю книгу, кроме того, мы можем видеть название только уверхней книги (это означает, что в каждый момент времени разрешён доступ только к верхнему элементу стека).Такая организация структуры данных называется LIFO (last in — first out).
В принципе, может присутствоватьжёсткое ограничение по количеству элементов стека.Рассмотрим интерфейс класса StackInt, который будет представлять собой стек целых чисел типа intфиксированной длины.#define STACKERRNOROOM (-1)class StackInt{int Size;int * Mem;int * CurSize;public:StackInt(int iSize);//~StackInt();//int Add(int Element);//int Get();//void Delete();//bool Empty();//bool HasRoom();//};конструктордеструктордобавление элементапросмотр вершины стекаудаление вершиныпуст ли стекесть ли место в стекеStackInt::StackInt(int iSize);{Mem = new int[iSize];Size = iSize;CurSize = 0;}int StackInt::Add(int Element){1 Здесь не будет подробно излагаться курс C++ , ибо достаточно подробно он описан только в книге Б.
Страуструпа «Языкпрограммирования C++ », а до Страуструпа нам всем пока далеко. Тем не менее некоторые пояснения будут иметь место, чтобынепосвящённый читатель не смотрел на код как на древние манускрипты.3if (HasRoom()){Mem[CurSize] = Element;CurSize++;} else return STACKERRNOROOM;}Здесь реализованы не все методы класса, однако реализация остальных методов очевидна и предоставляетсячитателю в качестве упражнения. Заметим, что в данном примере нет никакой обработки ошибок, связанныхс отсутствием памяти при её выделении в конструкторе. В реальных программах это недопустимо и в случаевозникновения ошибок подобного рода необходимо использовать механизмы обработки исключений (exceptions),либо возвращать код ошибки.Дек, или очередь с двумя концами, представляет собой модифицированный стек, в который можно добавлять элементы спереди и сзади.
Дек фиксированной длины несложно реализовать на базе кольцевого буфера, т. е. массива, запись в который происходит по принципуArray[I % Length] = Element. Нужно лишь, чтобы операция взятия остатка работала как вычеты по модулю, то есть, например, должно выполняться правило (-1) % Length = Length - 1.После того, как мы так представим дек, реализация становится очевидной: нам необходимо хранить текущую длину цепочки в кольце и её начальную позицию.
В принципе, можно хранитьпозицию хвоста, чтобы каждый раз не вычислять её по формуле (StartPos + ChainLength) % Length.1.3. Красно-чёрные деревьяКрасно-чёрные деревья представляют собой ещё один вариант реализации балансировки бинарного деревапоиска. Итак, красно-чёрным деревом называется бинарное дерево поиска, удовлетворяющее 4 свойствам:••••Каждой вершине приписан один из цветов: красный (RED) или черный (BLACK).Красные вершины имеют чёрных детей.Чёрная длина ветви — количество чёрных вершин на данной ветви, не считая её корня.Чёрная длина всех ветвей одного корня одинакова.Теорема 1.1.
Глубина красно-чёрного дерева с N вершинами не превосходит 2 log2 N . По существу нам надо доказать, что чёрная длина не превосходит log2 N , посколькудлинных чисто красных ветвей в дереве быть не может. Докажем это, используя индукKцию. Пусть h — чёрная высота дерева, а N — количество вершин в нём. Наше утверждениеhсостоит в том, что N > 2h . База индукции очевидна: для N = 1 имеем h = 0, для N = 2, 3h0 Lполучаем h 6 1. Допустим, что для любого сбалансированного КЧ-дерева c меньшим, чемRN , числом вершин наша оценка верна. Возьмём сбалансированное КЧ-дерево с N вершинами и разобьём его на 2 поддерева, содержащих NL и NR вершин, и корень K.
Для этихподдеревьев справедливо предположение индукции. Их чёрные высоты равны некоторому h0 , поскольку этиподдеревья имеют общий корень K. Очевидно, чёрная высота нашего дерева не превосходит h = h0 + 1. ИмеемNL > 2h0 и NR > 2h0 . Поскольку N = NL + NR + 1, имеем N > 2h0 + 2h0 + 1 > 2h0 +1 = 2h , что и требовалось.
1.4. Совершенные hash-функции (Perfect Hash Functions, PHF)Допустим, что у нас есть m слов (ключей). Мы хотим построить такую hash-функцию, чтобы она не давала коллизий на этих словах. Такой подход очень хорош при построении различного рода словарей, проверкиорфографии, компиляции и т.п. Hash-функция h называется совершенной, если Im h = 0, . . . , m − 1 . Такуюфункцию, конечно, можно построить длительным перебором большого количества функций, генерируемых,например, случайным образом. Проблема только одна: это хочется сделать быстро.Рассмотрим общий метод построения такой hash-функции, который приводит к успеху в среднем с однойдвух проб.
Будем искать h в виде h(x) = g f1 (x) + g f2 (x) , где f1 и f2 — hash-функции, а g — некотораяфункция перекодировки. Пусть n = cm, где c ∈ N, c > 1. Сгенерируем две случайные hash-функцииf1 и f2с диапазонами 0, . . . , n − 1. Каждому слову x поставим в соответствие пару f1 (x), f2 (x) , и из этих пар, какиз рёбер, построим граф, склеивая вершины с одинаковыми значениями. Нам хочется, чтобы в этом графеq небыло циклов. Можно доказать, что вероятность отсутствия циклов в таком графе асимптотически равна c−2cпри n = cm, n −→ ∞. Мы сможем построить h, если циклов в этом графе не будет, а из формулы видно, чтопри достаточно больших c вероятность близка к 1. Значит, пробовать придётся не так долго, а если сразу неполучилось, то надо вновь сгенерировать f1 и f2 .Пусть граф не содержит циклов.
Произвольно пронумеруем все рёбра числами 0, . . . , m − 1. Заметим, чтокаждому ребру соответствует некоторое слово нашего множества. Теперь для каждой компоненты связности4C графа будем вычислять g. Вспомним, что каждая вершина графа содержат либо f1 (x), либо f2 (x). Выберемпроизвольную вершину P ∈ C и положим g(P ) = 0, а для всех остальных вершин из C вычислим g по такомуправилу: пусть мы знаем значение g в вершине P ∈ C. Рассмотрим любого соседа Q вершины P . Пусть реброP Q имеет номер i.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
