Projekt z metod programowania

Informatyka, st. dzienne, sem. 5

prowadzący: Szymon Grabowski ( sgrabow@kis.p.lodz.pl )

Wymagania co do zaliczenia:

o początek semestru: pisemna specyfikacja projektu (1 strona), wydruk+doc;

o w trakcie semestru: referowanie projektu + prezentacja np. w PPT (założenia – dokładnie (np. interfejs użytkownika); opis wybranych problemów i propozycji ich rozwiązania, prezentacja podobnych istniejących rozwiązań – jeśli są takowe);

o koniec semestru: aplikacja + krótki raport (2 strony), wydruk+doc.

Specyfikacja:

o tytuł projektu,

o nazwiska Autorów,

o jakie funkcje będzie posiadała aplikacja,

o planowany język programowania + użyte biblioteki.

Dopuszczalne języki programowania: C, C++, Java, C#.

Dopuszczalne platformy: Windows 2000/XP, Linux, Mac OS.

Zalecany kompilator C++: MS VC++ 6.0 lub nowszy.

PROGRAMY UŻYTKOWE

1. Automatyczne sprawdzanie testów (wejście – np. skan BMP b&w), detekcja pytań.
(1 osoba)

2. Komunikator sieciowy
(1-2 osoby).

3. Przeglądarka obrazów w formacie JPEG wraz z obsługą EXIF-ów (sortowanie np. po zoomie, wyświetlanie (slideshow) z katalogu np. tylko zdjęć zrobionych z lampą błyskową itp.).
(2 osoby)

4. Katalogowanie płyt CD (a la DiskBase, http://diskbase.learsy.com/).

(2 osoby)

6. Program do zmiany grupowej nazw plików (w stylu Multi-Rename Tool z Total Commandera, ctrl-M :-).

(1 osoba)

7. Edytor tekstu z funkcją pracy grupowej w sieci lokalnej.
(1-2 osoby)

8. Edytor programistyczny (podświetlanie składni różnych języków, funkcje na blokach, „inteligentny” search (np. na życzenie omijanie komentarzy) etc.)
(1-2 osoby)

SZACHY

9. Preprocesor plików PGN (partie szachowe) pod kątem dalszej kompresji. Idee do zaimplementowania: usunięcie numerów ruchów, zastąpienie pól szachowych (np. „a7”), pojedynczymi bajtami, rozróżnienie między gońcami biało- a czarnopolowymi, obsługa nagłówków partii.

(1 osoba).

10. Program rozwiązujący zadania szachowe typu: mat pomocniczy, samomat.
Informacje nt. tego typu zadań:

http://www.logicalchess.com/info/reference/glossary.html

http://en.wikipedia.org/wiki/Selfmate

http://www.chessbase.com/puzzle/christmas2005/chr05-4a.htm

http://www.chessvariants.org/problems.dir/helpmate.html

Zalecane GUI.
(1-2 osoby).

11. Przeglądarka i wyszukiwarka partii szachowych zapisanych w formacie PGN (z interfejsem graficznym). Przykładowe kolekcje partii w tym formacie: http://www.chessopolis.com/chessfiles/pgn_collections.htm . Wyszukiwanie wg kryteriów dotyczących np. liczby ruchów w partii, pojawiających się końcówek (np. K+S+pp vs. K+G+pp) etc.
(1-2 osoby).

KOMPRESJA

12. bzip2/zzip + adaptive block adjustment (ewent. ulepszenie algorytmu z zzipa) + LZ(P/77)
(1 osoba)

13. Bezstratny preprocesor XML pod kątem dalszej kompresji.

Idee (m.in.): zastępowanie tagów zamykających 1-bajtowymi flagami; „gęste” kodowanie liczb i specyficznych wzorców (np. dat), zastępowanie częstych słów odnośnikami do słownika (dynamicznego), wykorzystanie DTD lub XML Schema.
Dokładniejsze informacje w pracy http://www.ii.uni.wroc.pl/~inikep/papers/07-AsymmetricXML.pdf
(1 osoba)

WYSZUKIWANIE WZORCÓW

14. Wyszukiwanie w obrazach JPEG (1 osoba).

15. Similarity search na obrazkach. (1-2 os.)

16. Indeksowanie tekstu a la Glimpse z wyszukiwaniem przybliżonym

http://citeseer.ist.psu.edu/28496.html
(2 osoby).

17. Indeksowanie bazy muzycznej (MIDI) pod kątem wyszukiwania przybliżonego

(alpha, delta, gamma). 1-2 osoby.

18. Sparse suffix array – implementacja i testy prostej struktury do indeksowania tekstu. (1 os.)

PROGRAMY EDUKACYJNE

19. Program demonstrujący "szkolne" konstrukcje geometryczne typu „cyrkiel i linijka”. Wykonujący skrypty (w prostym języku) opisujące elementarne operacje. Opcje: grubość / kolor / styl linii, okręgów; zoom (?), opóźnienie czasowe, zaznaczanie specjalnych punktów, np. przecięć.

(2 osoby).

20. Optyka - symulacje wybranych zjawisk optycznych (1 os.)

21. Model Układu Słonecznego (z obliczaniem siły grawitacji na poszczególnych planetach). (1 os.)

GRY LOGICZNE, UKŁADANKI

22. Program do gry logicznej "Szyki" (Lines of Action, http://en.wikipedia.org/wiki/Lines_of_Action ), nie grający, lecz tylko służący jako plansza dla gry dla 2 osób, z kontrolą poprawności ruchów.
(1 os.)

23. Program do rozwiązywania Sudoku. Przykładowe opcje: podpowiedzi (tj. wskazywanie zabronionych cyfr w wierszach / kolumnach / kwadratach), cofanie wpisu, pomiar czasu, baza zadań (w pliku tekstowym, albo w wielu plikach), poziom trudności zadań (łatwe / średnie / trudne), logowanie graczy i ich statystyki oraz związane z tym funkcje (np. ile zadań rozwiązał i ile z danej kategorii, udaremnianie ponownego rozwiązywania tego samego zadania przez danego gracza etc.). Dla dwóch osób również funkcja rozwiązywania zadania przez komputer.

(1-2 osoby).

24. Program do stawiania pasjansów (3-4 wybrane). 1-2 osoby.

25. Gra „Life” (możliwe modyfikacje, np. 2 lub więcej gatunków) (1 os.)

Inne: warcaby "na wybitkę", reversi, quod, gry karciane (tysiąc, kierki, kanasta?).

Kółko i krzyżyk na dużej planszy (5 w linii prostej).

GRY ZRĘCZNOŚCIOWE itp.

Arkanoid (1 osoba), skoki narciarskie (1-2 osoby), "goryle" (1 osoba).

Bilard (2D) (1 osoba).

PRZETWARZANIE OBRAZÓW

Mapowanie tekstur, czyli filtr, który nałoży obraz na inną powierzchnię

lub wyprostuje skrzywioną geometrię.

(Zastosowanie: np. preprocessing przed OCR ze zdjęcia z aparatu;

deformacje geometryczne są zwykle duże, w przeciwieństwie do obrazów

pozyskiwanych ze skanera.) (1 os.)