Практикум на ЭВМ (261, 4-й семестр)

Введение

За время семестра предлагается реализовать 3 программы:

    • Реализация сжатия файлов на основе метода Хаффмана
    • Реализация сжатия файлов на основе метода арифметического кодирования
    • Реализация эффективного поиска данных по предопределенному критерию

Так же в рамках данного курса.предусмотрена курсовая работа без отдельного зачета.

Задачи

Язык программирования предлагается на выбор: F#, C#, Java

Принимаются хорошо оформленные программы выложенные в систему контроля версий по адресу http://code.google.com/p/261studentprojects

К каждой задаче обязательно должны прилагаться тесты.

Метод Хаффмана

Написать программу, сжимающую файл методом Хаффмана.

    • Интерфейс программы может быть как консольным, так и графическим. В любом случае, интерфейс следует проектировать после ознакомления с аналогичными продуктами (7-zip, gzip, bzip2, WinZip, WinRAR).
    • Допустимо ограничиться сжатием одного файла, размером менее 2Гб. Для сжатия несколько файлов можно будет использовать программу tar или аналогичную. (См. связку программ gzip + tar)
    • Рекомендуемые тесты: пустой файл, файл со всеми символами, "левое" дерево, произвольный бинарный файл, текст.

Срок сдачи - конец марта

Арифметическое кодирование

Задача состоит в реализации метода арифметического кодирования для сжатия файлов

    • Одна из задач - макимально переиспользовать код предыдущей задачи. В идеале - реализовать оба метода с единым интерфесом.

Срок сдачи - середина апреля

B-Tree

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

Данные для поиска необходимо сгенерировать:

    • Выбрать тип данных и представление.
    • Например, это могут быть карточки с полями: Имя, Фамилия, Отчество, Пол, Телефон, Адрес. Поля имеют фиксированную длину, строки дополняются пробелами до максимальной длины.
    • Сгенерировать файл с данными.
    • Размер файла должен быть таким, чтобы его чтение занимало больше 1 секунды (условно).

Условие поиска:

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

Построение индекса:

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

Запросы:

    • По имееющимся данным, отношению порядка, и построенному индексу необходимо выполнять следующие запросы:
      • Количество карточек, лежащих в указанном диапазоне
      • Список всех карточек, лежащих в указанном диапазоне
      • Список первых n карточек, лежащих в указанном диапазоне
      • Первая карточека, из указанного диапазона
    • При этом запросы должны выполняться эффективно в следующем смысле
      • Запросы выполняются на "разогретой" БД: программа заргужена, все файлы открыты, предварительно выполнено несколько запросов.
      • Поиск 1 карточки должен занимать время сильно меньше 1 секунды.
      • Выборка списка карточек должна занимать время сравнимое с временем запроса 1 карточки.
      • Взятие следующего элемента из списка карточек должна занимать время не хуже, чем время запроса 1 карточки.
    • Замечание: "список", получающийся в результате запроса, следует реализовать как "итератор" в СУБД: т.е. это структура, в которой хранится элемент, и способ найти следующий элемент.

Срок сдачи - середина мая

Отчет по курсовой

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

Итак, требования к отчету:

    • Письменный отчет: от 1 листа формата A4 (можно больше. Например, см. ГОСТ Р 7.0.5-2008).
    • Отчет должны содержать следующие: заголовок или титульный лист, введение, постановка задачи, основная часть, заключение, список использованной литературы.
    • Формат отчёта - pdf или odt, формат презентации - pdf или odp
    • Защита курсовой со слайдами и проектором.

Желательно выбрать тему не связанную с данным курсом (что-то по работе, по студенческим проектам, и т.п.). Для тех, у кого нет готовой темы или выполненной работы, предлагаются следующие темы:

    • Реализация алгоритма Хаффмана
    • Особенности алгоритмов, представление данных, степень сжатия, эффективность
    • Реализация арифметического кодирований
    • Так же: кроме общих слов и особенностей реализации, добавить сравнение с конкурентами.
    • Сравнение различных методов сжатия данных.
    • Кроме реализованных методов следует сравнить с конкурентами.
    • Оптимизация поиска в линейной БД (?)

Первая попытка презентации состоится 11.05

Долги

(на 01.07.2009)