Архив‎ > ‎Весна 2009‎ > ‎

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

Предмет  Курс  Семестр  Группа
 Практикум на ЭВМ  2  3  261

Введение

За время семестра предлагается реализовать 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)
   Архиватор  БД  Курсовая  Зачет
 Солодкая Анастасия        
 Ахмедьянов Ренат        
 Цыпан Ксения        
 Лапин Сергей        
 Колянов Дмитрий        
 Кузнецов Кирилл        
 Миронов Артем        
 Мурашов Кирилл        

Comments