Проекти по Обектно-Ориентирано Програмиране

спец. Компютърни Науки, 2 поток

Правила и критерии за оценка

Проектите да бъдат предавани под формата на ZIP файл, съдържащ:

Всеки проект може да бъде избиран от не повече от 8 пъти. Срокът за избор на проект е 7 май 2015 г. Срокът за предаване на проект е до края на семестъра.

Всеки проект трябва да бъде защитен в рамките на 15 мин. При установено взаимстване от друг източник или недостатъчно познаване на кода проектът се анулира.

Всеки проект ще бъде оценяван по следните критерии:

Проекти

Матрици и вектори

Да се напишат подходящи класове, които позволяват операции с матрици и вектори от обекти от произволен тип. Класовете да поддържат следните операции:

1. Матрици

2. Вектори

Да се реализират следните операции за работа с вектори:

Да се напише подходяща примерна програма, която демонстрира работата с класовете.

Бонуси:

Големи числа

Да се реализира клас, който представя “големи числа”, т.е. цели числа, чиято дължина не е предварително ограничена, като на примитивните типове short, int, long. Числата могат да са отрицателни или положителни. За класа да се реализират:

Да се напише подходяща примерна програма, която демонстрира работата с класа.

Бонуси:

Геометрия

Да се реализират класове, които представят точка, вектор, права и равнина в тримерното пространство.

Точка да може да се конструира като

Вектор да може да се конструира като:

Права да може да се конструира като:

Равнина да може да се конструира като:

Да се реализират следните операции:

Бонуси:

Да се напише подходяща примерна програма, която демонстрира работата с класа.

Дати

Да се напише клас, който да представя дата от Григорианския календар с ден, месец и година. За класа да се реализират:

Не е позволено използването на системна библиотека за работа с дати.

Да се напише подходяща примерна програма, която демонстрира работата с класа.

Бонуси:

Кодирания RLE и Base64

1. RLE

Run-length encoding (RLE) представлява кодиране на низове, при което последователности от еднакви символи се заменят с двойка от символа и броя повторения. Например S = AAAABBBBCCCAABBBB може да се представи с RLE списъка R = (4,A) (4,B) (3,C) (2,A) (4,B). Да се напише клас, който представя низ от символи чрез RLE кодиране. За класа да се реализират:

За всяка една от горните операции е забранено да се извършва декодиране и повторно кодиране на RLE списък, те трябва да се извършват директно над вътрешното RLE представяне с цел ефективност.

2. Base64

Да се реализира клас, който представя масив от байтове (unsigned char) като низ с произволна дължина, съдържащ само символите “A-Za-z0-9+/”, чрез така нареченото Base64 кодиране, както е описано по-долу.

Целта на кодирането е да се избегнат специалните символи като ‘\t’, ‘\n’, ‘\0’ и други. Забележете, че броят на символите в множеството “A-Za-z0-9+/” е 26 = 64 (= 26+26+10+2). Така всеки символ носи 6 бита информация. Следователно, всеки 3 байта = 24 бита се представят с 4 символа.

Алгоритъм на кодиране:

  1. разглеждаме входния двоичен масив като последователност от групи по 24 бита (три байта  от по 8 бита)
  2. всеки 24 бита разбиваме на четири 6-битови байта
  3. на всеки 6-битов байт съпоставяме съответния символ от списъка “A-Za-z0-9+/”
  4. записваме получените символи в текстовия файл

Имаме от един от следните случаи:

  1. броят байтове е кратен на 3, тогава всичко е ОК
  2. броят байтове дава остатък 1 при деление на 3. Тогава при последното четене са останали само 8 бита. Допълваме до 12 бита с нули и кодираме с два символа. Допълваме с два символа ‘=’ (padding), така че общият брой на символите да се дели на 4.
  3. броят байтове дава остатък 2 при деление на 3. Тогава при последното четене са останали само 16 бита. Допълваме до 18 бита с нули и кодираме с три символа Допълваме с един символ ‘=’ (padding), така че общият брой на символите да се дели на 4.

Това кодиране се нарича base64 и се използва при прикрепяне на файл към e-mail съобщение, заради изискванията на протокола да не се използват специални символи. Резултатът от кодирането е текстов файл с размер 4/3 спрямо оригиналния, но без специални символи и върши работа за всякакви файлове. Недостатък е, че съдържанието на кодирания файл е неразбираемо за човек. Съществува и друго широко използвано кодиране наречено quoted-printable – като при него се разчита, че се изпраща главно текст и малък брой специални символи, които се escape-ват.

Подробна спецификация на base64 и quoted-printable кодиранията можете да намерите в секции 6.7 и 6.8 на rfc2045 (например на адрес http://www.faqs.org/rfcs/rfc2045.html).

За класа да се реализират:

Не се позволява използването на стандартни библиотеки и готови решения!

Да се напише подходяща примерна програма, която демонстрира работата с класовете.

Бонуси:

XML Parser

Да се реализира клас, който представя XML елемент, който съдържа следната информация:

Класът да поддържа следните операции:

Минимални изисквания за поддържаните XPath заявки

Примерите по-долу са върху следния прост XML низ:

<people>

<person id=”0”>

                <name>John Smith</name>

                <address>USA</address>

</person>

<person id=”1”>

                <name>Ivan Petrov</name>

        <address>Bulgaria</address>

</person>

</people>

Да се напише подходяща примерна програма, която демонстрира работата с класовете.

Забележка: За проекта не е позволено използването на готови библиотеки за работа с XML. Целта на проекта е да се упражни работата със структурирани текстови файлове, а не толкова със самия XML. Внимание: Не се изисква осигуряване на всички условия в  XML и XPath спецификациите! Достатъчно е файловете да “приличат на XML” (както файла в горния пример, който не е валиден XML), а завките да “приличат” на XPath.

Бонуси:

Детерминиран краен автомат

Да се реализира клас, който представя детерминиран краен автомат над азбука, състояща се от цифрите и малките латински букви. За класа да се реализират:

Бонуси:

Недетерминиран краен автомат

Да се реализира клас, който представя недетерминиран краен автомат с ℇ-преходи. над азбука, състояща се от цифрите и малките латински букви. За класа да се реализират:

Бонуси:

Стеков автомат и контекстно-свободна граматика

Да се реализира клас, който представя контекстно-свободна граматика, използваща главни латински букви за променливи (нетерминали) и малки латински букви и цифри за терминали. За класа да се реализират:

Да се реализира клас, който представя недетерминиран стеков автомат. За класа да се реализират:

Бонуси:

Машина на Тюринг

Да се реализира клас, който представя потенциално безкрайна двупосочна лента от малки латински букви, цифри и интервал. Лентата да бъде реализирана чрез масив, който може да се разширява в двете посоки при нужда.

Да се реализира клас, който представя детерминирана машина на Тюринг с потенциално безкрайна лента, първоначално инициализирана с интервали. За класа да се реализират:

Бонуси: