Ø Nieprzesuwalny termin oddania rozwiązania: 30.06.2005
Ø W tym projekcie programistycznym każdy będzie miał do napisania moduł implementujący co najmniej dwa algorytmy rozwiązujące ten sam problem (w szczególności, każdy z algorytmów ma tą samą specyfikację wejścia/wyjścia). Każdy z algorytmów należy zaprogramować jako oddzielną procedurę. Algorytmy te były prezentowane na wykładzie lub ćwiczeniach. W razie potrzeby można poprosić Pawła Zalewskiego, by omówił je jeszcze na repetytorium.
Ø Oprócz zaimplementowania algorytmów, Waszym zadaniem jest napisanie programów porównujących szybkość algorytmów.
Ø Na Wasze rozwiązania powinny składać się (co najmniej) następujące pliki:
o Plik z modułem;
o Plik z programem testującym szybkość zaimplementowanych algorytmów;
o Plik(i) z przykładowymi danymi bądź programem je generującym;
o Plik przewodni o nazwie guide zawierający (co najmniej) następujące informacje:
§ Imię i nazwisko autora
§ Treść zadania
§ Spis zawartości poszczególnych plików
§ Wszelkie informacje, które pomogą osobom trzecim testowanie Waszego rozwiązania.
o Plik z opisem sposobu i wyników testowania szybkości algorytmów.
Ø Wszystkie pliki należy spakować w jeden samorozpakowujący się plik typu *.zip. Plik powinien rozpakowywać się do katalogu o nazwie postaci projekt<nr><nazwisko>, np.
projekt1.3lorys
Ø Przyjmujemy
następującą konwencję odnośnie nazw plików:
o Pliki z modułami: <idmodul><nazwisko>, gdzie idmodul jest ze zbioru
{mediana,
mst, mnozenieliczb, macierzelog, macierzeToeplitza, wzorce }
o
Pliki z programami: <idprog><nazwisko>, gdzie
idprog jest ze zbioru
{ Mag5,
Hoare, LazySelect,
Kruskal,
Sollin,
MnozDZ2,
MnozDZ3,
MMKlasyka,
MMStrassen, MM4Rosjan,
ToeplitzDZ,
ToeplitzFFT,
KarpRabin, KMP, BoyerMoore )
o
Pliki z danymi: dane.in
o
Pliki z generatorami danych: generator<nazwisko>
o
Oczywiście nazwy plików z modułami i programami powinny
mieć rozszerzenie właściwe dla użytego języka programowania.
Ø Programy
we wszystkich projektach mają czytać dane z pliku tekstowego dane.in a
wyniki wypisywać do pliku wyniki.out.
Ø Dane
w pliku dane.in oddzielane są pojedynczymi spacjami (nie przecinkami!!!)
Ø Nie
określamy rozmiaru danych. Powinniście przyjąć następujące założenia:
o
Na wykonanie się Waszych programów przeznaczone będzie
100MB pamięci.
o
Programy powinny w ramach tego limitu wykonywać się na
możliwie największych danych.
o
Podczas testowania algorytmów proszę pomyśleć o
zminimalizowaniu:
§
wpływu błędów pomiaru czasu,
§
wpływu czasu
operacji wejścia/wyjścia na wyniki testów
Ø Programy
napisane mają być w jednym z następujących języków programowania:
o
Pascal (standard FreePascal 1.0.6)
o
C++
(standard GCC 3.3.1)
o
Java
(standard J2SDK 1.4.0)
Ø Programy będą kompilowane następującymi
poleceniami: fpc, g++, javac. Jedynym parametrem tych poleceń
będzie nazwa pliku z programem.
Ø Programy będą uruchamiane projektów
środowisku Linux’owym.
Ø Proszę nie korzystać projektów projektów
bibliotek specyficznych dla poszczególnych producentów oprogramowania.
Projekt 1.1
Napisz moduł implementujący algorytmy znajdowania k-tego elementu ciągu: algorytm „magicznych piątek”, algorytm Hoare’a i algorytm LazySelect.
Postać pliku dane.in:
W pliku wynikowym ma znaleźć się jedna liczba całkowita, równa wartości k-tego elementu ciągu.
Projekt 1.2
Napisz moduł implementujący algorytmy znajdujące minimalne drzewo rozpinające grafu: algorytm Kruskala i algorytm Sollina.
Postać pliku dane.in:
W pliku wynikowym zawierającym n-1 wierszy ma znaleźć się opis minimalnego drzewa rozpinającego. W każdym wierszu ma znaleźć się para liczb naturalnych u, v oznaczająca krawędź pomiędzy wierzchołkami u i v.
Możesz założyć, że wejściowy graf jest spójny.
Projekt 1.3
Napisz moduł implementujący algorytmy mnożenia długich liczb metodą dziel i zwyciężaj: podział na dwie części i podział na trzy części.
Postać pliku dane.in:
W jedynym wierszu pliku wynikowego ma znaleźć się iloczyn liczb a i b.
Ambitniejsi studenci mogą zaimplementować dodatkowo algorytm Schoenhage-Strassena.
Projekt
1.4
Napisz moduł implementujący algorytmy mnożenia macierzy logicznych: klasyczny algorytm, zmodyfikowany algorytm Strassena oraz algorytm czterech Rosjan.
Postać pliku dane.in:
W pliku wynikowym mają znaleźć opis macierzy wynikowej (analogiczny jak opisy macierzy wejściowych).
Projekt 1.5
Napisz moduł implementujący algorytmy mnożenia macierzy Toeplitza przez wektor: algorytm oparty na metodzie dziel i zwyciężaj, algorytm oparty na FFT.
Postać pliku dane.in:
W jedynym wierszu pliku wyjściowego ma znaleźć się n liczb wyznaczających wektor wynikowy.
Projekt 1.6
Napisz moduł implementujący algorytmy wyszukiwania wzorca: algorytm Karpa-Rabina, algorytm KMP, algorytm Boyera-Moore’a.
Postać pliku dane.in:
Plik ten zawiera dwa wiersze. W każdym z nich znajduje się po jednym słowie nad alfabetem {a,b,...,z,A,...,Z,0.,9,’spacja’}.
W pierwszym wierszu pliku wyjściowego ma znaleźć się jedna liczba n równa liczbie wystąpień wzorca w tekście. W każdym z kolejnych n ma znaleźć się liczba równa wartości kolejnego przesunięcia z jakim występuje wzorzec w tekście.