Практикум на ЭВМ (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)