Krzysztof Rzecki
Zbiór zadań laboratoryjnych
do przedmiotu
„Algorytmy i Struktury Danych”
Kraków 2006
Krzysztof Rzecki
Zbiór zadań laboratoryjnych
do przedmiotu
„Algorytmy i Struktury Danych”
Kraków 2006
Niniejszy Zbiór zadań laboratoryjnych… to zebrane i usystematyzo-
wane zadania do nauki i ćwiczenia najwaŜniejszych umiejętności profe-
sjonalnego informatyka i programisty, jakimi są umiejętność konstru-
owania wydajnych algorytmów oraz umiejętność projektowania odpo-
wiednich struktur danych. Zbiór ten powstał na bazie zajęć dydaktycz-
nych prowadzonych w postaci ćwiczeń laboratoryjnych w Politechnice
Krakowskiej im. T. Kościuszki. Układ zbioru został zaprojektowany tak,
Ŝe stanowi on pomoc zarówno dla nauczycieli prowadzących laboratorium
do omawianego przedmiotu, studentów realizujących ten program, jak i
osób pragnących samodzielnie zgłębić swoje umiejętności w tym zakre-
sie. Zbiór zawiera zadania pogrupowane w ćwiczenia, z których kaŜde
posiada wyznaczony cel oraz punkt wymieniający podstawowe pojęcia,
algorytmy i struktury danych z którymi naleŜy się zapoznać, aby dane
ćwiczenie zrealizować jak najlepiej. Istotą kaŜdego ćwiczenia są zadania
programistyczne oraz opracowania.
© Copyright by Krzysztof Rzecki, Kraków 2006-2008
E-mail: krz@mars.iti.pk.edu.pl, WWW: http://krz.iti.pk.edu.pl/
Instytut Teleinformatyki E-6
Politechnika Krakowska im. Tadeusza Kościuszki
PL 31-155 Kraków
Niniejszego zbioru w całości lub w części nie wolno powielać ani przeka-
zywać w Ŝaden sposób, nawet za pomocą nośników mechanicznych
i elektronicznych (np. zapis magnetyczny), w tym teŜ umieszczać ani
rozpowszechniać w postaci cyfrowej zarówno w Internecie, jak i w sie-
ciach lokalnych, bez uzyskania pisemnej zgody autorów.
Korekta: Aleksandra Heba
Druki i skład:
CCNS Spółka Akcyjna
ul. Reymonta 27
30-059 Kraków
Wszelkie błędy i wskazówki proszę zgłaszać na adres: krz@pk.edu.pl
Spis treści
Wprowadzenie ............................................................ 7
Ćwiczenie 1. Konto i oprogramowanie ........................ 9
Cel ćwiczenia ..................................................................... 9
Wiadomości wstępne .......................................................... 9
Konto w Laboratorium i na Serwerze ...................................10
Hasło ....................................................................................10
Narzędzia .........................................................................11
Edytory tekstu........................................................................11
Kompilatory ...........................................................................12
Rozwiązywanie zadań ........................................................13
Kompilacja i uruchamianie .......................................................13
Nazwy plików programów i ich połoŜenie....................................14
Opis programu i komentarze ....................................................14
Dokumentacja ........................................................................15
Zadania do samodzielnego wykonania..................................16
Zadanie 1.
Logowanie na zdalny komputer .................................16
Zadanie 2.
Przesyłanie plików ...................................................17
Ćwiczenie 2. Schemat blokowy algorytmu ................ 19
Cel ćwiczenia ....................................................................19
Wiadomości wstępne .........................................................19
Zadania do samodzielnego wykonania..................................20
Zadanie 3.
Potęga – schemat blokowy .......................................20
Zadanie 4.
Potęga - implementacja ...........................................21
Zadanie 5.
Algorytmy arytmetyczne – przykłady .........................21
Zadanie 6.
Schemat blokowy wybranego algorytmu ....................22
Zadanie 7.
Implementacja wybranego algorytmu ........................22
Ćwiczenie 3. Całkowanie ........................................... 23
Cel ćwiczenia ....................................................................23
Wiadomości wstępne .........................................................23
Zadania do samodzielnego wykonania..................................24
Zadanie 8.
Całka oznaczona – metoda trapezów .........................24
Zadanie 9.
Całka oznaczona – metoda prostokątów.....................25
Zadanie 10.
Całka oznaczona – metoda Monte Carlo ...................25
Zadanie 11.
Całka oznaczona – dokumentacja ............................27
Zadanie 12.
Całka oznaczona w przestrzeni 3D ...........................27
Zadanie 13.
Całka nieoznaczona ...............................................28
„Algorytmy i Struktury Danych”
4
Ćwiczenie 4. Rekurencje............................................29
Cel ćwiczenia.................................................................... 29
Wiadomości wstępne ......................................................... 29
Zadania do samodzielnego wykonania ................................. 30
Zadanie 14.
Potęga .................................................................30
Zadanie 15.
Silnia ...................................................................30
Zadanie 16.
Ciąg Fibonacciego..................................................30
Zadanie 17.
Katalogi i pliki .......................................................31
Ćwiczenie 5. Tablice i zbiory......................................33
Cel ćwiczenia.................................................................... 33
Wiadomości wstępne ......................................................... 33
Zadania do samodzielnego wykonania ................................. 34
Zadanie 18.
Prosty zbiór ..........................................................34
Zadanie 19.
Zbiór ...................................................................34
Ćwiczenie 6. Listy jedno- i dwukierunkowe ...............37
Cel ćwiczenia.................................................................... 37
Wiadomości wstępne ......................................................... 37
Zadania do samodzielnego wykonania ................................. 40
Zadanie 20.
Lista jednokierunkowa ...........................................40
Zadanie 21.
Operacje na liście jednokierunkowej ........................40
Zadanie 22.
Lista dwukierunkowa .............................................41
Zadanie 23.
Operacje na liście dwukierunkowej ..........................42
Ćwiczenie 7. Stos i kolejka ........................................43
Cel ćwiczenia.................................................................... 43
Wiadomości wstępne ......................................................... 43
Zadania do samodzielnego wykonania ................................. 44
Zadanie 24.
Stos ....................................................................44
Zadanie 25.
Kolejka ................................................................45
Ćwiczenie 8. Proste metody sortowania ....................47
Cel ćwiczenia.................................................................... 47
Wiadomości wstępne ......................................................... 47
Zadania do samodzielnego wykonania ................................. 49
Zadanie 26.
Sortowanie bąbelkowe ...........................................49
Zadanie 27.
Sortowanie przez wstawianie ..................................49
Zadanie 28.
Sortowanie przez selekcję ekstremum .....................51
Zadanie 29.
Porównanie prostych metod sortowania ...................51
Spis treści
5
Ćwiczenie 9. Zaawansowane metody sortowania...... 53
Cel ćwiczenia ....................................................................53
Wiadomości wstępne .........................................................53
Zadania do samodzielnego wykonania..................................55
Zadanie 30.
Sortowanie shell....................................................55
Zadanie 31.
Sortowanie stogowe/kopcowe .................................55
Zadanie 32.
Sortowanie szybkie................................................55
Zadanie 33.
Porównanie zaawansowanych metod sortowania .......56
Ćwiczenie 10. Hash ................................................... 57
Cel ćwiczenia ....................................................................57
Wiadomości wstępne .........................................................57
Zadania do samodzielnego wykonania..................................58
Zadanie 34.
Hashowanie z metodą łańcuchową...........................58
Zadanie 35.
Hashowanie – badania ...........................................59
Ćwiczenie 11. Grafy .................................................. 61
Cel ćwiczenia ....................................................................61
Wiadomości wstępne .........................................................61
Zadania do samodzielnego wykonania..................................62
Zadanie 36.
Algorytm Floyda-Warshalla .....................................62
Zadanie 37.
Przeszukiwanie wszerz – listy sąsiedztwa .................63
Zadanie 38.
Przeszukiwanie w głąb – macierz sąsiedztwa.............64
Ćwiczenie 12. Drzewa i kopce ................................... 67
Cel ćwiczenia ....................................................................67
Wiadomości wstępne .........................................................67
Zadania do samodzielnego wykonania..................................68
Zadanie 39.
Drzewa BST..........................................................68
Zadanie 40.
Słownik ................................................................69
Ćwiczenie 13. Algorytmy teorioliczbowe ................... 75
Cel ćwiczenia ....................................................................75
Wiadomości wstępne .........................................................75
Zadania do samodzielnego wykonania..................................76
Zadanie 41.
Test Millera-Rabina ................................................76
Zadanie 42.
Algorytmy kryptograficzne......................................76
Zadanie 43.
Kryptoanaliza statystyczna .....................................78
„Algorytmy i Struktury Danych”
6
Ćwiczenie 14. Wyszukiwanie wzorca.........................79
Cel ćwiczenia.................................................................... 79
Wiadomości wstępne ......................................................... 79
Zadanie 44.
Generator tekstu ...................................................80
Zadanie 45.
Algorytm naiwny ...................................................80
Zadanie 46.
Algorytm nie taki naiwny........................................81
Zadanie 47.
Algorytm Rabina-Karpa ..........................................82
Ćwiczenie 15. Zliczanie i prawdopodobieństwo .........85
Cel ćwiczenia.................................................................... 85
Wiadomości wstępne ......................................................... 85
Zadania do samodzielnego wykonania ................................. 86
Zadanie 48.
Permutacje i kombinacje ........................................86
Zadanie 49.
Losowanie liczb z zadanym rozkładem .....................86
Zadanie 50.
Grawitacja............................................................86
Literatura ..................................................................89
Wprowadzenie
Zbiór składa się z 15 ćwiczeń (50 zadań), które zostały opracowa-
ne z myślą o przeprowadzeniu ich na dowolnym komputerze z systemem
Linux (oprócz ćw.1) i kompilatorem g++. Ćwiczenia moŜna takŜe wyko-
nać na dowolnym innym systemie operacyjnym z dowolnym innym kom-
pilatorem C/C++. NaleŜy wówczas zmodyfikować nazwy ścieŜek prze-
chowywanych programów oraz opis programu dotyczący kompilacji i uru-
chamiania.
Podstawowym źródłem wiedzy dotyczącej tematyki algorytmów i
struktur danych jest znakomita ksiąŜka T.H.Cormen, C.E.Leiserson,
R.L.Rivest, C.Stein, pt. „Wprowadzenie do algorytmów”. KsiąŜka ta jest
polecanym podręcznikiem w nauce przedmiotu, a niniejszy skrypt bazuje
na zawartej w niej wiedzy i posiada do niej wiele odwołań w postaci
wskazówek.
Tematyka skryptu obejmuje szeroki zakres problematyki algoryt-
mów i struktur danych: schematy blokowe algorytmów, rekurencje, zbio-
ry, listy (łańcuchy odsyłaczowe), algorytmy sortujące, hash, struktury
grafowe (w tym drzewa i kopce), algorytmy teorioliczbowe, algorytmy
wyszukiwania wzorca oraz zliczanie i prawdopodobieństwo.
Układ skryptu nie wprowadza podziału tematyki na algorytmy i
osobno struktury danych, poniewaŜ oba te zagadnienia są ze sobą ściśle
powiązane. KaŜde z kolejnych ćwiczeń posiada określony cel stanowiący
temat danego ćwiczenia. KaŜde ćwiczenie posiada takŜe informacje doty-
czące wiadomości wstępnych z jakimi naleŜy się zapoznać (najlepiej
„Algorytmy i Struktury Danych”
8
z pozycji [1]), aby dobrze zrozumieć ćwiczenie i poprawnie zrealizować
zadania. W niektórych ćwiczeniach punkt wiadomości wstępnych został
rozwinięty (np. ćwiczenie dotyczące algorytmów sortowania) o ciekawe
przykłady i wyniki.
ZałoŜeniem autorów jest, Ŝe czytelnik posiada przynajmniej pół-
roczne przygotowanie z podstaw programowania w języku C/C++.
Mimo długoletniej historii zagadnień związanych algorytmami
i strukturami danych, zakres pozycji takiego typu jak ten skrypt jest wy-
jątkowo skromny.
Ćwiczenie 1.
Konto i oprogramowanie
Cel ćwiczenia
Celem ćwiczenia ”Konto i oprogramowanie” jest:
•
Przeprowadzenie logowania/wylogowania do systemów Linux i Win-
dows oraz do Serwera.
•
Zmiana hasła do konta na stacjach Laboratorium (system Linux i Win-
dows) oraz do Serwera.
•
Wykonanie testowego programu sprawdzającego działanie kompilatora
g++ w systemie Linux oraz kompilatora DevC++ w systemie Windows.
•
Zapoznanie się z metodą opisywania, uporządkowanego przechowy-
wania i nazywania pisanych programów.
•
Zapoznanie się z podstawowymi elementami dokumentacji, wymaga-
nych przy opracowywaniu niektórych ćwiczeń.
Wiadomości wstępne
Przed przystąpieniem do laboratorium naleŜy zapoznać się (albo
przypomnieć sobie wiedzę z przedmiotu „Wstęp do Informatyki”) z na-
stępującymi zagadnieniami teoretycznymi dotyczącymi pracy w syste-
mie Linux i Windows:
•
system operacyjny, system plików,
•
róŜnice między systemem Linux a Windows,
•
login i hasło do systemu operacyjnego,
•
polecenie systemowe a program,
„Algorytmy i Struktury Danych”
10
•
praca zdalna i przesyłanie plików.
Ponadto naleŜy zapoznać się z ogólnymi zagadnieniami dotyczącymi pro-
gramowania:
•
pojęcia: algorytm, program,
•
narzędzia: kompilator i linker,
•
języki programowania: niskiego i wysokiego poziomu,
•
kod programu: źródłowy i wykonywalny,
•
programy: kompilowane i interpretowane,
•
techniki programowania (uzaleŜnione takŜe od moŜliwości języka):
liniowe, strukturalne i obiektowe.
Konto w Laboratorium i na Serwerze
Ćwiczenia laboratoryjne z przedmiotu „Algorytmy i Struktury Da-
nych” przeprowadzane są na stacjach Laboratorium 202 Instytutu Telein-
formatyki Politechniki Krakowskiej. Stacje te współpracują ze studenckim
Serwerem MARS (http://mars.iti.pk.edu.pl/) korzystając z usług:
•
w systemie Linux:
o
NFS (ang. Network File System) - serwis współdzielenia
przestrzeni dyskowej,
o
NIS (ang. Network Information Service) - usługa autenty-
kacji i autoryzacji,
•
w systemie Windows:
o
Samba – zapewnia zarówno dostęp do przestrzeni dysko-
wej serwera, jak i umoŜliwia kontrolę dostępu do systemu.
Hasło
Przed przystąpieniem do ćwiczeń naleŜy sprawdzić dokładnie, czy
moŜna zalogować się na stacjach Laboratorium na swoje konto, zarówno
w systemie Linux jak i Windows. Zwróć uwagę, Ŝe wykonując zmianę
hasła – dokonuje się to tylko na jednym systemie.
Ćwiczenie 1. Konto i oprogramowanie
11
Pamiętaj, Ŝe hasło do systemu Linux w Laboratorium jest zawsze
takie samo jak hasło na Serwer.
Aby zmienić hasło w systemie Linux, naleŜy zalogować się na jed-
ną ze stacji lub na Serwer i wykonać polecenie (znak $ oznacza prompt i
nie naleŜy go wpisywać):
$ passwd
System zapyta o podanie starego hasła oraz dwukrotnie o nowe.
W systemie Windows wykonujemy tę operację poprzez kombina-
cję klawiszy [Alt]+[Carl]+[Del], a następnie wybieramy myszą klawisz
'zmień hasło'. Podobnie wpisujemy raz hasło stare i dwa razy hasło no-
we.
Uwaga!
Kontroluj ilość zajmowanego przez Twoje pliki miejsca w przestrzeni dys-
kowej Serwera. Podstawowa metoda polega na tym, aby w systemie Li-
nux wykonać polecenie:
$ quota -v
Niekontrolowane zapełnianie przydzielonego miejsca moŜe doprowadzić
do zablokowania konta.
Narzędzia
W Laboratorium dostępne są róŜne narzędzia do edycji kodów
źródłowych oraz kompilatory języka C/C++, które będą wykorzystywane
w dalszych ćwiczeniach.
Edytory tekstu
W systemie Windows dostępny jest prosty edytor Notatnik, ale
lepszym rozwiązaniem jest uŜycie zintegrowanego środowiska DevC++,
o którym mowa dalej.
„Algorytmy i Struktury Danych”
12
W systemie Linux mamy do dyspozycji bardzo duŜo tekstowych i
graficznych edytorów tekstu, które podzielić naleŜy na dwie grupy pod
względem środowiska pracy:
•
W trybie tekstowym:
o
vi / vim – najstarszy i najbardziej popularny edytor posia-
dający moŜliwość m.in. kolorystyki słów kluczowych w róŜ-
nych językach programowania.
o
pico – duŜo prostszy od vi edytor charakteryzujący się
znaczną prostotą obsługi.
o
mc – aplikacja Midnight Commander posiada swój edytor
wewnętrzny uruchamiany klawiszem [F4].
o
emacs – nowoczesny, rozbudowany edytor tekstu posiada-
jący m.in. integrację z róŜnymi kompilatorami.
•
W trybie graficznym (tylko stacje Laboratorium):
o
KEdit – odpowiednik aplikacji Notatnik z systemu Windows.
o
XEmacs – graficzna wersja edytora emacs.
Kompilatory
Większość profesjonalnych kompilatorów języka C/C++ na system
Windows to narzędzia komercyjne. Wydział InŜynierii Elektrycznej i
Komputerowej w Politechnice Krakowskiej posiada licencję EULA na opro-
gramowanie firmy Microsoft, którego dystrybucją na cele dydaktyczne na
Wydział zajmuje się Instytut Teleinformatyki. W skład tego oprogramo-
wania wchodzą środowiska Visual C++ 6.0 oraz Visual Studio .NET. Są to
rozbudowane narzędzia pozwalające sprawnie konstruować i modelować
aplikacje okienkowe, korzystać z zaawansowanych technologii progra-
mowania komponentowego, itp.
Oprócz oprogramowania firmy Microsoft, w Laboratorium dostępne jest
takŜe środowisko DevC++, które jest narzędziem darmowym dostępnym
w sieci Internet.
W systemie Linux dostępne są bardzo popularne kompilatory gcc
(język C) i g++ (język C++), które wchodzą w skład oprogramowania z
dystrybucji systemu Linux. Kompilator g++ będzie wykorzystywany do
ćwiczeń omawianych w tej ksiąŜce.
Ćwiczenie 1. Konto i oprogramowanie
13
Rozwiązywanie zadań
W skład poprawnie rozwiązanego zadania wchodzi kilka elemen-
tów, które zostały opisane poniŜej, a są to:
•
Prawidłowo napisany kod programu (tzn. posiada wcięcia, podział na
funkcje, itp.), kompilujący się bezbłędnie i wykonujący poprawnie dane
zadanie.
•
Kod źródłowy programu jest oryginalnym dziełem studenta, posiada
poprawnie opisany nagłówek oraz komentarze trudniejszych linii pro-
gramu.
•
Niektóre zadania wymagają dokumentacji napisanej w odpowiedniej
formie z uwzględnieniem szeregu waŜnych części.
Kompilacja i uruchamianie
Spróbujmy napisać prosty program, którego zadaniem jest wypi-
sanie ciągu znaków na ekran. Sprawdzimy w ten sposób działanie kompi-
latora języka C++: g++.
Niech plik z programem nazywa się
‘program_testowy.cc’
:
#include <iostream.h>
main()
{
cout << “Program testowy w C++” << endl;
}
Kompilowanie programu:
$ g++ -o program_testowy program_testowy.cc
Jeśli kompilator zgłosił ostrzeŜenie dotyczące przestarzałych nagłówków
moŜna uŜyć opcji ‘-Wno-deprecated’, która zablokuje ten komunikat.
Uruchamianie programu:
$ ./program_testowy
„Algorytmy i Struktury Danych”
14
Nazwy plików programów i ich połoŜenie
Do sprawniejszej organizacji zajęć naleŜy załoŜyć w swoim kata-
logu domowym na Serwerze strukturę katalogów jak poniŜej:
$ cd
// przej
ś
cie do katalogu domowego
$ mkdir aisd
// od słów ‘Algorytmy
// i Struktury Danych’
Na kaŜdych zajęciach realizowane będą kolejne programy, które
naleŜy umieszczać w załoŜonym katalogu ‘aisd’ w odpowiednio nazwa-
nych podkatalogach i plikach. O nazwie podkatalogu ('zadXX-temat') i
programu ('progXX-temat.cc') decyduje podany w zadaniu jego numer
oraz skrócony temat.
Przykład:
Zadanie '08', którego skrócony temat podano jako 'potega' naleŜy zapi-
sać w pliku o nazwie:
prog08-potega.cc
i umieścić w podkatalogu:
zad08-potega
Czyli pełna ścieŜka do pliku z programem jest następująca:
~/aisd/zad08-potega/prog08-potega.cc
Opis programu i komentarze
Programy stanowiące rozwiązania zadań laboratoryjnych naleŜy
opisywać poprzez umieszczenie na początku pliku źródłowego odpowied-
niego nagłówka postaci (przykład):
/*
Data:
28.II.'06
Autor: Jan Kowalski <jankowal@mail.pl>
II rok Informatyki, ITI, IEiK, PK
Grupa: Sroda 11:00-12:30
Zadanie:
08
Temat: Program obliczajacy calki oznaczone.
Kompilowanie:
g++ -o prog08-potega prog08-potega.cc
Uruchamianie:
./prog08-potega <pelna skladnia opcji>
*/
Ćwiczenie 1. Konto i oprogramowanie
15
Korzystając z podanego wzorca naleŜy zawsze zapisać odpowied-
nią datę laboratorium, imię, nazwisko, email, rok, grupę, numer zadania,
temat zadania, pełną składnię opcji wymaganą przy kompilowaniu oraz
pełną i/lub przykładową składnię opcji wymaganą przy uruchamianiu
gotowego programu.
Jeśli w treści zadania nie zostanie napisane inaczej, to wszystkie
zadania są jednoosobowe i w linii związanej z autorem powinny się zna-
leźć dane jednego tylko autora.
WaŜniejsze linie i kawałki kodu programu naleŜy odpowiednio ko-
mentować. W przypadku komentowania funkcji, przed jej nazwą naleŜy
umieścić max. 5-linijkowy opis wraz z wymaganymi parametrami. Ko-
mentowanie trudniejszych linii naleŜy wykonywać na jej końcu przy uŜy-
ciu znaków komentarza (w C/C++: ‘/*’ oraz ‘*/’ lub tylko ‘//’).
Jeśli w treści zadania nie zostanie napisane inaczej, to programy
nie mogą wymagać Ŝadnej interakcji ze strony uŜytkownika.
Dokumentacja
Jeśli dane zadanie lub projekt wymaga wykonania dokumentacji,
naleŜy przygotować ją z uwzględnieniem podanych niŜej kryteriów.
1.
Dokumentację naleŜy pisać w programie Writer pakietu OpenOffi-
ce (moŜesz go pobrać ze strony http://www.ux.pl/).
2.
Nazwa pliku (jeśli nie podano w treści zadania) jest taka jak nu-
mer zadania i skrócony jego temat z przedrostkiem 'dok' i rozsze-
rzeniem 'sxw'. Czyli np. do zadania '06' o skróconym temacie 'tr-
eesearch' plik dokumentacji nazywa się 'dok06-treesearch.sxw'.
3.
PołoŜenie pliku: identycznie jak zadania programistyczne.
4.
Minimalna zawartość dokumentacji:
•
opis problemu,
•
opis rozwiązania (słownie),
•
schemat blokowy algorytmu,
•
wskazanie trudniejszych elementów programu.
„Algorytmy i Struktury Danych”
16
5.
Oprawa edytorska dokumentacji:
•
czcionka: Verdana 11pt,
•
odstęp: 1,5 linii,
•
nagłówek, np.: „05. Algorytmy i struktury danych – .... <tytuł
zadania>...”,
•
oprawa w postaci nasuwanego grzbietu,
•
opis słowny zadanego algorytmu.
6.
Strona tytułowa powinna zawierać przynajmniej:
•
tytuł zadania,
•
imiona i nazwiska autorów + e-mail,
•
rok, kierunek, wydział, uczelnia,
•
data (wydania zadania lub zakończenia zadania),
•
poprawny tytuł, imię i nazwisko prowadzącego.
Zadania do samodzielnego wykonania
Zadanie 1.
Logowanie na zdalny komputer
Wykonaj kilka prób logowania SSH między komputerami i róŜnymi
systemami: domowym, w Laboratorium a Serwerem.
Aby połączyć się ze stacji w Laboratorium, z systemu Linux wyko-
naj polecenie (w tym przykładzie serwerem jest: mars.iti.pk.edu.pl):
$ ssh mars.iti.pk.edu.pl
W podobny sposób moŜesz połączyć się z komputera domowego, z sys-
temu Linux.
Aby połączyć się ze stacji w Laboratorium, z systemu Windows,
wykorzystaj aplikację PUTTY (adres, np.: mars.iti.pk.edu.pl, port: 22). W
podobny sposób moŜesz połączyć się z komputera domowego, z systemu
Windows.
Wykonaj próbę w laboratorium i zaloguj się na Serwer, a następ-
nie powrotem na swoją stację. Spróbuj zalogować się ze swojej stacji
Ćwiczenie 1. Konto i oprogramowanie
17
(lub z Serwera) na dowolną inną stację w Laboratorium, która ma włą-
czony system Linux.
Zwróć uwagę, Ŝe moŜliwe są tylko połączenia:
•
ze stacji Laboratorium na Serwer,
•
z Serwera na stację w Laboratorium,
•
z komputera domowego na Serwer.
Jeśli Twój komputer domowy posiada własny adres IP, albo jeśli jesteś w
sieci osiedlowej, która skonfigurowana jest do przekazywania połączeń,
moŜe być moŜliwe uzyskanie połączenia z Serwera i/lub stacji z Labora-
torium do Twojego komputera.
Zadanie 2.
Przesyłanie plików
Do przesyłania plików w systemie Windows słuŜy oprogramowanie
WinSCP. MoŜna je pobrać z Internetu ze strony: http://winscp.net/
W systemie Linux pliki przesyłać moŜna przy pomocy programu
SCP w następujący sposób (wysyłanie):
$ scp <plik> login@host.docelowy:/sciezka/do/katalogu
Lub (pobieranie):
$ scp login@host.zrodlowy:/sciezka/do/pliku .
Wykonaj próby przesyłania dowolnych plików z/na Twój komputer
oraz z/na Serwer. Zapoznaj się z moŜliwymi opcjami, m.in. rekurencyj-
nym przesyłaniem wszystkich plików z wskazanego katalogu.
Ćwiczenie 2.
Schemat blokowy algorytmu
Cel ćwiczenia
Celem ćwiczenia jest opanowanie umiejętności budowania sche-
matów blokowych do zadanych algorytmów. Ćwiczenie to słuŜy takŜe
wyrobieniu umiejętności odczytywania zadanego schematu blokowego i
tworzenia algorytmu na jego podstawie.
Wiadomości wstępne
Przed przystąpieniem do laboratorium naleŜy zapoznać się z na-
stępującymi zagadnieniami teoretycznymi dotyczącymi schematów
blokowych algorytmów:
•
pojęcia: algorytm, schemat blokowy, skrzynka schematu blokowego,
•
elementy schematu blokowego:
o
skrzynka graniczna,
o
skrzynka operacyjna,
o
skrzynka wejścia/wyjścia,
o
skrzynka warunkowa (decyzyjna).
ZałoŜenia budowy schematu blokowego:
•
kaŜda operacja jest umieszczona w skrzynce,
•
schemat ma tylko jedną skrzynkę „Start” i przynajmniej jedną skrzyn-
kę „Stop”,
•
skrzynki są ze sobą połączone,
„Algorytmy i Struktury Danych”
20
•
ze skrzynki wychodzi jedno połączenie; wyjątki:
o
skrzynka „stop”, z której nie wychodzą juŜ Ŝadne połącze-
nia,
o
skrzynka warunkowa, z której wychodzą dwa połączenia
opisane: „tak” „nie”.
Zadania do samodzielnego wykonania
Zadanie 3.
Potęga – schemat blokowy
Treść:
Zapoznaj się z poniŜszym schematem blokowym prezentującym
algorytm obliczania potęgi dwóch liczb całkowitych zapisanych w zmien-
nych 'podstawa' i 'potęga'.
Ćwiczenie 2. Schemat blokowy algorytmu
21
WskaŜ na schemacie:
•
poszczególne skrzynki i nazwij je,
•
zwróć uwagę na napisy znajdujące się w skrzynkach,
•
prześledź algorytm ze schematu dla liczb:
o
2 i 4,
o
5 i 0,
o
3 i -1,
o
3 i 6.
Zadanie 4.
Potęga - implementacja
Plik:
prog04-potega.cc
PołoŜenie:
~/aisd/zad04-potega/
Uruchamianie:
./prog04-potega <podstawa> <wykladnik>
Treść:
Napisz program, który implementuje algorytm ze schematu z poprzed-
niego zadania.
Zadanie 5.
Algorytmy arytmetyczne – przykłady
Wyjaśnij na czym polegają podane niŜej algorytmy arytmetyczne
(w nawiasie podany został skrócony temat oraz krótki opis zadania, które
zostaną wykorzystane w kolejnym zadaniu):
•
silnia ('silnia', obliczanie silni z podanej liczby całkowitej),
•
NWW ('nww', obliczanie NWW z podanych dwóch liczb całkowitych),
•
NWD ('nwd', obliczanie NWD z podanych dwóch liczb całkowitych),
•
sito Eratostenesa ('sito', wyznaczanie liczb pierwszych mniejszych od
podanej dodatniej liczby całkowitej),
•
trójki pitagorejskie ('trojki', wyszukiwanie wszystkich liczb całkowitych
dodatnich spełniających równanie c2 = a2 + b2, mniejszych od zada-
nej wartości),
•
testowanie liczb pierwszych ('test', sprawdzanie czy podana liczba cał-
kowita jest liczbą pierwszą),
•
zmiana systemu liczbowego ('decbin', zmiana zapisu podanej liczby
całkowitej w zapisie dziesiętnym do zapisu binarnego w U2),
„Algorytmy i Struktury Danych”
22
•
mnoŜenie pisemne liczb ('mnozenie', pisemne mnoŜenie dwóch liczb
całkowitych),
•
wyszukiwanie binarne ('szukbin', wyszukiwanie binarne w posortowa-
nej tablicy),
•
wyznacznik macierzy ('det', obliczanie wyznacznika z macierzy kwa-
dratowej o podanej długości boku, wypełnionej liczbami losowymi).
Zadanie 6.
Schemat blokowy wybranego algorytmu
Plik:
dok06-<skrócony temat>.sxw
PołoŜenie:
~/aisd/zad06-<skrócony temat>/
Wykreśl schemat blokowy zadanego algorytmu i umieść go w dokumen-
tacji, którą naleŜy sporządzić wg wytycznych podanych w Ćwiczeniu 1.
Zadanie 7.
Implementacja wybranego algorytmu
Pliki:
prog07-<skrócony temat>.cc
PołoŜenie:
~/aisd/zad07-<skrócony temat>/
Uruchamianie:
./prog07-<skrócony temat> <parametry>
Treść:
Napisz program, który implementuje zadany algorytm. Program musi
zostać tak napisany, aby nie wymagał od uŜytkownika Ŝadnej interakcji –
wszystkie parametry (jeśli są potrzebne) mają być podawane z linii ko-
mend.
Ćwiczenie 3.
Całkowanie
Cel ćwiczenia
Celem ćwiczenia jest przypomnienie i dopracowanie umiejętności
z podstaw programowania w języku C/C++, które dotyczą:
•
operatorów,
•
instrukcji warunkowych,
•
pętli,
•
typów danych,
•
funkcji,
•
wskaźników,
•
operacji wejścia/wyjścia.
Wiadomości wstępne
Przed przystąpieniem do laboratorium naleŜy zapoznać się z na-
stępującymi zagadnieniami dotyczącymi programowania w C/C++:
•
operatory: arytmetyczne, bitowe, logiczne, relacyjne, priorytety,
•
instrukcje warunkowe: if-else, switch-case,
•
pętle: ‘for-do’, ‘while’, ‘do-while’,
•
typy wbudowane i typy uŜytkownika,
•
tablice jedno- i wielowymiarowe,
•
funkcje: konstrukcja, zwracanie wyniku, przekazywanie parametrów
do funkcji: przez wartość, referencję i wskaźnik,
•
wskaźniki do zmiennych,
„Algorytmy i Struktury Danych”
24
•
operacje wejścia/wyjścia.
Wskazówka:
Jerzy Grębosz, „Symfonia C++”, Oficyna Kallimach, ISBN 83-901689-X.
Zadania do samodzielnego wykonania
W tym ćwiczeniu naleŜy wykonać i porównać w opracowaniu trzy
zadania programistyczne, które implementują algorytmy obliczania przy-
bliŜonej wartości całki oznaczonej z funkcji wielomianowej dowolnego
(mniejszego niŜ 10) stopnia. Przedostatnie zadanie to rozwinięcie jednej
z metod do przestrzeni trójwymiarowej, a ostatnie dotyczy analitycznego
obliczenia całki nieoznaczonej.
Zadanie 8.
Całka oznaczona – metoda trapezów
Plik:
prog08-calkatrapez.cc
PołoŜenie:
~/aisd/zad08-calkatrapez/
Uruchamianie:
./prog08-calkatrapez <an> ... <a1> <a0> <b> <c>
Treść:
Napisz program obliczający całkę oznaczoną z funkcji wielomianowej
jednej zmiennej w zadanym przedziale. Program powinien przyjmować z
linii poleceń wszystkie wymagane parametry (i sprawdzać ich popraw-
ność):
•
an - współczynnik przy n-tej potędze zmiennej (liczba całkowita z
przedziału: -9..0..9); moŜna załoŜyć, Ŝe najdłuŜszy wielomian będzie
10-tego stopnia,
•
b - początek przedziału całkowania (liczba całkowita -1000...1000),
•
c - koniec przedziału całkowania (liczba całkowita -1000...1000, oraz
b<c).
Przykład:
Wywołanie programu:
$ ./prog08-calkatrapez 3 5 0 -7 1 -600 400
Ćwiczenie 3. Całkowanie
25
Oznacza, Ŝe chodzi o wielomian postaci:
f(x) = 3*x^4 + 5*x^3 - 7*x + 1
A całkowanie ma się odbywać w przedziale < -600, 400 >.
Całkowanie naleŜy przeprowadzić metodą obliczenia pola pod wy-
kresem funkcji poprzez sumowanie pól w małych przedziałach. Szerokość
przedziału powinna być rzędu ~1/[k*(c-b)], gdzie k=10, 100, 1000 -
dobrać empirycznie tak, aby czas obliczeń był <5 [s]. Jako figury cząst-
kowe (małe elementy) z których będzie się składać całe pole pod wykre-
sem przyjąć trapez o długościach podstaw równych wartościom funkcji
na początku i końcu elementu, oraz o wysokości równej szerokości ele-
mentu.
Program ma wypisać na ekran postać wielomianu, przedział cał-
kowania, przyjętą szerokość podprzedziałów oraz wynik całkowania.
Zadanie 9.
Całka oznaczona – metoda prostokątów
Plik:
prog09-calkaprost.cc
PołoŜenie:
~/aisd/zad09-calkaprost/
Uruchamianie:
./prog09-calkaprost <an> ... <a1> <a0> <b> <c>
Treść:
Napisz program realizujący podobną funkcjonalność jak w poprzednim
zadaniu, ale wykorzystując prostokąt jako figurę cząstkową. Jako dłu-
gości boków przyjąć szerokość przedziału oraz średnią z wartości funkcji
na początku i na końcu przedziału.
Zadanie 10.
Całka oznaczona – metoda Monte Carlo
Plik:
prog10-montecarlo.cc
PołoŜenie:
~/aisd/zad10-montecarlo/
Uruchamianie:
./prog10-montecarlo <an> ... <a1> <a0> <b> <c>
Treść:
Napisz program realizujący podobną funkcjonalność jak w poprzednim
zadaniu, ale wykorzystując metodę Monte Carlo do obliczenia zadanej
całki. Metoda Monte Carlo to technika, w której wykonuje się ‘ostrzał’
obszaru całkowania. Ów ‘ostrzał’ polega na losowaniu dwóch liczb (x oraz
y), które odpowiadają współrzędnym punktu na wykresie. Liczby losowa-
„Algorytmy i Struktury Danych”
26
ne są z pewnych, ściśle określonych zakresów. Następnie sprawdzane
jest czy wylosowany punkt leŜy pod funkcją (ew. na niej) czy nad funkcją
poprzez obliczenie wartości funkcji dla liczby x w tym miejscu. Zakres
losowanej liczby x na osi odciętych wyznaczają krańce obszaru całkowa-
nia (liczby b i c). Zakres dla liczby y na osi rzędnych wyznaczany jest
przez: oś odciętych i pewną wartość, której ustalenie jest takŜe treścią
tego zadania.
PoniŜszy rysunek wyjaśnia metodę:
Zliczane są punkty w obszarze A i w obszarze B. Wartość całki oznaczo-
nej równa jest polu pod wykresem (P
B
) i wyznaczamy ją na podstawie
wzoru:
P
B
= P
A+B
* L
B
/ L
A + B
Gdzie:
•
P
A+B
– pole całego prostokąta, P
A+B
= h * (c - b),
•
L
B
– liczba trafionych punktów w obszar B (obszar całkowania),
•
L
A+B
– liczba wszystkich punktów.
Zaproponuj w swoim rozwiązaniu metodę wyznaczenia zakresu h. Zwróć
uwagę, Ŝe jeśli funkcja przecina oś odciętych to dolne ograniczenie nie
jest prawdziwe. Uwzględnij ten problem i zaproponuj takŜe metodę wy-
Ćwiczenie 3. Całkowanie
27
znaczenia dolnej krawędzi prostokąta. UzaleŜnij liczbę ‘strzałów’ od wiel-
kości prostokąta, niech to będzie duŜa ilość, ale taka by całkowity czas
działania programu był <5[s].
Program ma wypisać na ekran postać wielomianu, przedział cał-
kowania, dobrane wartości dolnego i górnego ograniczenia, liczbę
wszystkich ‘strzałów’ oraz wynik całkowania.
Zadanie 11.
Całka oznaczona – dokumentacja
Plik:
dok11-calkaoznaczona.sxw
PołoŜenie:
~/aisd/zad11-calkaoznaczona/
Treść:
Zaproponuj 10 róŜnorodnych funkcji wielomianowych, dla kaŜdej z nich
zaproponuj jeden przedział całkowania. Oblicz analitycznie wartości całek
oznaczonych z zadanych przedziałów, wykonaj obliczenia programami z
poprzednich zadań tego ćwiczenia. Porównaj wartości, oblicz błędy, zba-
daj wydajności poszczególnych programów. Napisz jedną dokumentację
do omawianych doświadczeń, narysuj schematy blokowe algorytmów,
wykreśl wykresy zaproponowanych przez Ciebie funkcji wielomianowych.
Zadanie 12.
Całka oznaczona w przestrzeni 3D
Plik:
prog12-calkaoznaczona3d.cc
PołoŜenie:
~/aisd/zad12-calkaoznaczona3d/
Uruchamianie:
.
/prog12-calkaoznaczona3d <an> ... <a1> <a0> <b> <c>
Treść:
Napisz program obliczający pojemność figury otrzymanej z funkcji wie-
lomianowej, obróconej wokół osi OX i ograniczonej zadanymi płaszczy-
znami. Zadanie objaśnia poniŜszy rysunek.
„Algorytmy i Struktury Danych”
28
W programie uŜyj albo algorytmu sumowania objętości albo metody
Monte Carlo (analogicznie do poprzednich zadań). Program ma wypisać
na ekran postać wielomianu, przedział całkowania, wybrany algorytm
oraz stosownie do niego pozostałe wartości.
Zadanie 13.
Całka nieoznaczona
Plik:
prog13-nieoznaczona.cc
PołoŜenie:
~/aisd/zad13-nieoznaczona/
Uruchamianie:
./prog13-nieoznaczona <an> ... <a2> <a1> <a0>
Treść:
Napisz program realizujący analityczne obliczanie całki nieoznaczonej z
zadanego wielomianu.
Program ma wypisać na ekran postać wielomianu przed całkowa-
niem oraz po całkowaniu.
Ćwiczenie 4.
Rekurencje
Cel ćwiczenia
Celem ćwiczenia jest zapoznanie się z techniką programowania
rekurencyjnego oraz moŜliwościami jakie ona daje.
Wiadomości wstępne
Przed przystąpieniem do laboratorium naleŜy zapoznać się z na-
stępującymi zagadnieniami teoretycznymi dotyczącymi rekurencji:
•
pojęcie rekurencji,
•
metody: podstawiania, iteracyjna, rekurencji uniwersalnej.
Wskazówka:
Thomas Cormen, „Algorytmy i Struktury Danych”,
podrozdziały 4.1 – 4.3, str. 77 – 88.
„Algorytmy i Struktury Danych”
30
Zadania do samodzielnego wykonania
Zadanie 14.
Potęga
Plik:
prog14-potega.cc
PołoŜenie:
~/aisd/zad14-potega/
Uruchamianie:
./prog14-potega <podstawa> <potega>
Treść:
Napisz program implementujący algorytm obliczania potęgi z zadanej
liczby w sposób rekurencyjny. Na wejściu program powinien przyjmować
dwa parametry będące liczbami całkowitymi (podstawę i potęgę), a na
wyjściu wyświetlać wynik działania.
Zadanie 15.
Silnia
Plik:
prog15-silnia.cc
PołoŜenie:
~/aisd/zad15-silnia/
Uruchamianie:
./prog15-silnia <liczba>
Treść:
Napisz program implementujący obliczanie silni w sposób rekurencyjny.
Na wejściu program powinien przyjmować parametr będący liczbą całko-
witą, a na wyjściu wyświetlać wynik (silnię z podanej liczby).
Zadanie 16.
Ciąg Fibonacciego
Plik:
prog16-fibonacci.cc
PołoŜenie:
~/aisd/zad16-fibonacci/
Uruchamianie:
./prog16-fibonacci <n>
Treść:
Ciąg Fibonacciego formalnie opisuje wzór:
a
0
= 1
a
1
= 1
a
n
= a
n - 2
+ a
n - 1
Napisz program implementujący rekurencyjne obliczanie wyrazu a
n
w
ciągu Fibonacciego. Na wejściu program powinien przyjmować parametr
Ćwiczenie 4. Rekurencje
31
będący liczbą całkowitą, oznaczający numer wyrazu w ciągu, a na wyj-
ściu wyświetlać wynik (poszukiwaną wartość wyrazu).
Zadanie 17.
Katalogi i pliki
Plik:
prog17-katalogiipliki.cc
PołoŜenie:
~/aisd/zad17-katalogiipliki/
Uruchamianie:
./prog17-katalogiipliki <sciezka>
Treść:
Napisz program implementujący rekurencyjny algorytm przeszukiwania
struktury katalogów i plików. Na wejściu program powinien przyjmować
parametr będący ścieŜką do pliku lub katalogu. Wyjściem programu ma
być schematyczne drzewo określające zawartość podanej ścieŜki.
Przykład:
Jeśli stworzymy strukturę plików i katalogów w następujący sposób:
$ mkdir zoo
$ mkdir zoo/ptaki zoo/ptaki/domowe zoo/ptaki/lesne
$ mkdir zoo/ryby zoo/ryby/slodkowodne zoo/ryby/morskie
$ touch zoo/ptaki/domowe/kury zoo/ptaki/domowe/kaczki
$ touch zoo/ryby/morskie/rekiny
Jeśli program zostanie uruchomiony w następujący sposób:
$ ./prog17-katalogiipliki zoo
To wynikiem działania będzie:
zoo
- jest katalogiem
|-ptaki
- jest katalogiem
| |-domowe
- jest katalogiem
| | |-kury
- jest plikiem
| | |-kaczki
- jest plikiem
| |-lesne
- jest katalogiem (pusty)
|-ryby
- jest kataloiem
|-slodkowodne
- jest katalogiem (pusty)
|-morskie
- jest katalogiem
|-rekiny
- jest plikiem
Program nie moŜe wymagać Ŝadnej interakcji ze strony uŜytkownika.
Ćwiczenie 5.
Tablice i zbiory
Cel ćwiczenia
Wiadomości wstępne
Przed przystąpieniem do laboratorium naleŜy zapoznać się z na-
stępującymi zagadnieniami teoretycznymi dotyczącymi zbiorów:
•
pojęcia: zbiór, podzbiór, element,
•
własności zbioru,
•
operacje na zbiorach: przecięcie, suma, róŜnica,
•
prawa zbiorów: zbiorów pustych, idempotentności, przemienności,
łączności, rozdzielności, pochłaniania, De Morgana,
•
diagram Venna,
•
iloczyn kartezjański,
•
pojęcie relacji oraz jej własności: zwrotna, symetryczna, przechodnia,
równowaŜności, antysymetryczna, częściowego porządku.
Wskazówka:
Thomas Cormen, „Algorytmy i Struktury Danych”,
podrozdziały 5.1 – 5.2, str. 103 – 110.
„Algorytmy i Struktury Danych”
34
Zadania do samodzielnego wykonania
Zadanie 18.
Prosty zbiór
Plik:
prog18-prostyzbior.cc
PołoŜenie:
~/aisd/zad18-prostyzbior/
Uruchamianie:
./prog18-prostyzbior
Treść:
Napisz program implementujący zbiór liczb całkowitych na statycznej
tablicy 100-elementowej. Program po uruchomieniu oczekuje w pętli na
jedną z czterech komend:
•
dodaj <liczba>
- komenda, która dodaje element
<liczba>
(liczba
całkowita) do zbioru; jeśli taka liczba w zbiorze juŜ istnieje, program
wypisuje komunikat na ekran i nowej liczby juŜ nie dodaje; jeśli zbiór
jest pełny (wszystkie komórki tablicy zostały zapełnione) wówczas
element nie jest dodawany, a program wypisuje odpowiedni komuni-
kat,
•
usun <liczba>
- komenda, która usuwa element
<liczba>
ze zbioru;
jeśli taka liczba w zbiorze nie istnieje, program wypisuje odpowiedni
komunikat na ekran,
•
wypisz
– komenda, która powoduje wypisanie na ekran zawartości
całego zbioru,
•
koniec
– zakończenie działania programu.
Zadanie 19.
Zbiór
Pliki:
prog19-zbior.cc
oraz
dok19-zbior.sxw
PołoŜenie:
~/aisd/zad19-zbior/
Uruchamianie:
./prog19-zbior <rozmiar> [<komenda> [<parametr>]] ...
Treść:
Napisz program (a do niego dokumentację zawierającą m.in. schemat
blokowy algorytmu) implementujący zbiór napisów na tablicy dynamicz-
nej. Program ma przyjmować wszystkie parametry (komendy) z linii po-
leceń.
Ćwiczenie 5. Zbiory
35
Parametry (komendy):
•
<rozmiar>
- liczba określająca wielkość zbioru,
•
dodaj <napis>
- dodanie elementu
<napis>
do zbioru; jeśli dany na-
pis istnieje juŜ w zbiorze, wówczas nie jest on dodawany,
•
usun <napis>
- usuwanie elementu
<napis>
ze zbioru,
•
wypisz
– wypisanie zawartości całego zbioru,
•
pusty
– usuniecie wszystkich elementów ze zbioru,
•
pelny
– określenie, czy zbiór jest pełny.
Przykład:
Wywołanie programu z parametrami:
$ ./prog19-zbior 5 dodaj kot wypisz pelny dodaj pies \
dodaj kot dodaj mysz wypisz usun pies wypisz
Spowoduje, Ŝe na ekranie zobaczymy kolejno:
Zbior pomie
ś
ci 5 elementow.
Dodano element ‘kot’ do zbioru.
Elementy zbioru: kot.
Zbior nie jest pelny.
Dodano element ‘pies’ do zbioru.
Element ‘kot’ istnieje ju
Ŝ
w zbiorze.
Dodano element ‘mysz’ do zbioru.
Elementy zbioru: kot pies mysz.
Usunieto element ‘pies’ ze zbioru.
Elementy zbioru: kot mysz.
Przed zakończeniem działania, program usuwa dynamicznie utworzoną
tablicę z pamięci.
Ćwiczenie 6.
Listy jedno- i dwukierunkowe
Cel ćwiczenia
Celem ćwiczenia jest poznanie dwóch bardzo waŜnych struktur
danych, tj. list jedno- i dwukierunkowych. Ćwiczenie polegać będzie na
wykonaniu szeregu zadań obejmujących zaprojektowanie algorytmów
obsługi list, narysowanie schematów blokowych oraz rysunków prezentu-
jących ich działanie.
Wiadomości wstępne
Przed przystąpieniem do laboratorium naleŜy zapoznać się z na-
stępującymi zagadnieniami teoretycznymi dotyczącymi list jedno- i
dwukierunkowych:
•
pojęcia: lista jedno- i dwukierunkowa, głowa, ogon, wskaźnik next,
prev, lista cykliczna, wartownik, nil,
•
operacje na listach:
o
wstawianie: na początek, na koniec, za wskazanym ele-
mentem, za n-tym elementem,
o
usuwanie elementu: z początku, z końca, dowolnego wska-
zanego, n-tego elementu,
o
zamiana: wskazanego elementu z następnym, wskazanego
elementu z poprzednim, n-tego elementu z następnym, n-
tego elementu z poprzednim,
•
usuwanie listy.
„Algorytmy i Struktury Danych”
38
Wskazówka:
Thomas Cormen, „Algorytmy i Struktury Danych”,
rozdział 11, str. 240 – 244.
Przykład:
RozwaŜmy algorytm wstawiania nowego elementu za n-tym elementem
w liście dwukierunkowej. Przyjmijmy następujące załoŜenia dotyczące
struktury pojedynczego elementu (ang. node):
typedef struct node
{
struct node *next;
struct node *prev;
} node;
Oraz dane wejściowe:
node *first
– wskaźnik na pierwszy element listy,
node *element
– wskaźnik na nowy element,
int n
– numer elementu, za którym naleŜy wstawić nowy.
PoniŜszy rysunek prezentuje metodę wstawienia nowego elementu za n-
tym elementem w liście dwukierunkowej:
Działanie algorytmu polega na przejściu do miejsca umieszczenia nowego
elementu poprzez zliczanie elementów listy, począwszy od pierwszego.
Strzałka w prawo od danego elementu na schemacie wskazuje
next
(na-
stępny element listy), a strzałka w lewo
prev
(poprzedni element listy).
Ćwiczenie 7. Listy jedno- i dwukierunkowe
39
Pseudokod algorytmu wygląda następująco:
int i;
node *tmp = first;
for (i = 1 ; i < n ; i++) tmp = tmp -> next;
element -> next = tmp -> next;
tmp -> next = element;
element -> prev = tmp;
Schemat blokowy rozwaŜanego algorytmu:
„Algorytmy i Struktury Danych”
40
Zadania do samodzielnego wykonania
Zadanie 20.
Lista jednokierunkowa
Treść:
Zapoznaj się z poniŜszym schematem blokowym.
Odpowiedz na pytania:
1.
Jaki algorytm przedstawia schemat?
2.
Co się stanie, jeśli 'first' jest wskaźnikiem do NULL?
3.
Narysuj poprawnie schemat blokowy algorytmu, który uwzględniał
będzie sytuację, kiedy 'first' jest wskaźnikiem do NULL.
4.
Napisz pseudokod odpowiadający poprawionemu schematowi al-
gorytmu.
Zadanie 21.
Operacje na liście jednokierunkowej
Plik:
dok23-listajeden.sxw
PołoŜenie:
~/aisd/zad23-listajeden/
Treść:
Wykonaj opracowanie opisujące 13 operacji na liście jednokierunko-
wej. KaŜdy opis pojedynczej operacji powinien zawierać:
•
rysunek poglądowy operacji,
•
schemat blokowy,
Ćwiczenie 7. Listy jedno- i dwukierunkowe
41
•
pseudokod realizujący operację.
Operacje:
•
wstawianie: na początek, na koniec, za wskazanym elementem, za n-
tym elementem,
•
usuwanie elementu: z początku, z końca, dowolnego wskazanego, n-
tego elementu,
•
zamiana: wskazanego elementu z następnym, wskazanego elementu z
poprzednim, n-tego elementu z następnym, n-tego elementu z po-
przednim,
•
usuwanie listy z pamięci.
Wskazówka:
Jedną z operacji pokazuje zadanie Zadanie 20.
Zadanie 22.
Lista dwukierunkowa
Treść:
Zapoznaj się z poniŜszym pseudokodem.
typedef struct node
{
struct node * next;
struct node * prev;
} node;
element = new node;
element -> next = first;
first = element;
element -> prev = NULL;
element -> next -> prev = first;
Odpowiedz na pytania:
Jaki algorytm przedstawia pseudokod?
Co się stanie, jeśli first jest wskaźnikiem do NULL?
Napisz poprawny pseudokod algorytmu, który uwzględniał będzie
sytuację, kiedy 'first' jest wskaźnikiem do NULL.
Narysuj schemat blokowy odpowiadający zadanemu pseudokodowi.
„Algorytmy i Struktury Danych”
42
Zadanie 23.
Operacje na liście dwukierunkowej
Plik:
dok25-listadwa.sxw
PołoŜenie:
~/aisd/zad25-listadwa/
Treść:
Wykonaj opracowanie opisujące 13 operacji na liście dwukierunkowej.
KaŜdy opis pojedynczej operacji powinien zawierać:
•
rysunek poglądowy operacji,
•
schemat blokowy,
•
pseudokod realizujący operację.
Operacje:
•
wstawianie: na początek, na koniec, za wskazanym elementem, za n-
tym elementem,
•
usuwanie elementu: z początku, z końca, dowolnego wskazanego, n-
tego elementu,
•
zamiana: wskazanego elementu z następnym, wskazanego elementu z
poprzednim, n-tego elementu z następnym, n-tego elementu z po-
przednim,
•
usuwanie listy z pamięci.
Wskazówka:
Jedną z operacji pokazuje zadanie Zadanie 23.
Ćwiczenie 7.
Stos i kolejka
Cel ćwiczenia
Celem ćwiczenia jest poznanie struktury oraz mechanizmów dzia-
łania kolejek oraz stosu. Ćwiczenie pokazuje takŜe przykładowe ich za-
stosowanie.
Wiadomości wstępne
Przed przystąpieniem do laboratorium naleŜy zapoznać się z na-
stępującymi zagadnieniami teoretycznymi dotyczącymi stosu i kolejki:
•
stos (strategia LIFO/FILO),
•
kolejka (strategia LILO/FIFO).
Wskazówka:
Thomas Cormen, „Algorytmy i Struktury Danych”,
rozdział 11, str. 236 – 239.
„Algorytmy i Struktury Danych”
44
Zadania do samodzielnego wykonania
Zadanie 24.
Stos
Plik:
prog20-stos.cc
PołoŜenie:
~/aisd/zad20-stos/
Uruchamianie:
./prog20-stos <rozmiar>
Treść:
Zaprojektuj listę dla stosu (strategia LIFO/FILO) oraz algorytmy jego
obsługi poprzez komendy:
•
push <liczba>
– połoŜenie elementu na stosie,
•
pop
– zdjęcie i podanie wartości elementu ze stosu,
•
wypisz
– odczytanie wartości bez zdejmowania elementu ze stosu,
•
koniec
– zakończenie działania programu.
Napisz program, który pobiera z linii poleceń (linii komend) wielkość sto-
su (maksymalną ilość elementów) oraz obsługuje listę jako stos, zawie-
rając omówione wyŜej funkcje. Praca z programem powinna odbywać się
w trybie konsoli.
Przykład:
$ ./prog20-stos 4
Stos o wielko
ś
ci: 4
> push 2
Polozono 2
> push 7
Polozono 7
> wypisz
Na czubku stosu znajduje sie 7
> pop
Zdjeto 7
> wypisz
Na czubku stosu znajduje sie 2
> koniec
Ćwiczenie 6. Stos i kolejka
45
Zadanie 25.
Kolejka
Plik:
prog21-kolejka.cc
PołoŜenie:
~/aisd/zad21-kolejka/
Uruchamianie:
./prog21-kolejka <parametry>
Treść:
Zaprojektuj listę dla kolejki (strategia LILO/FIFO) oraz algorytmy jej ob-
sługi poprzez komendy:
•
put <liczba>
– dołoŜenie elementu do kolejki,
•
get
– wyjęcie elementu z kolejki i podanie jego wartości,
•
wypisz
– odczytanie wartości bez wyjmowania elementu z kolejki.
Napisz program, który pobiera z linii poleceń (linii komend) długość ko-
lejki (maksymalna długość listy), obsługujący taką listę jako kolejkę,
zawierając omówione wyŜej funkcje. Program naleŜy napisać tak, by pre-
zentacja jego działania odbywała się całkowicie z linii komend.
Przykład:
Jeśli program zostanie wywołany w następujący sposób:
$ ./prog07-kolejka 5 wypisz put 4 put 9 wypisz \
get put 2 put 5 wypisz put 6 put 2 put 7
To w wyniku otrzymamy kolejno:
Kolejka wielkosci: 5
Kolejka jest pusta
Dodano 4
Dodano 9
Na wyjsciu kolejki znajduje sie 4
Zdj
ę
to 4
Dodano 2
Dodano 5
Na wyjsciu kolejki znajduje sie 9
Dodano 6
Dodano 2
Nie mozna dodac 7, poniewaz kolejka jest pelna
Ćwiczenie 8.
Proste metody sortowania
Cel ćwiczenia
Celem ćwiczenia jest poznanie, zaimplementowanie, przetestowa-
nie i porównanie trzech prostych (powolnych) metod sortowania: bąbel-
kowego, przez wstawianie oraz przez selekcję ekstremum.
Wiadomości wstępne
Przed przystąpieniem do laboratorium naleŜy zapoznać się z na-
stępującymi zagadnieniami teoretycznymi dotyczącymi prostych metod
sortowania:
•
tematyka: algorytmy, analiza algorytmów, projektowanie algorytmów,
metoda „dziel i zwycięŜaj”, złoŜoność, rząd złoŜoności,
•
sortowanie:
o
bąbelkowe (ang. bubble sort),
o
przez wstawianie (ang. insertion sort),
o
przez selekcję ekstremum (ang. selection sort).
Wskazówka:
Thomas Cormen, „Algorytmy i Struktury Danych”,
rozdział 1, str. 21 – 43.
„Algorytmy i Struktury Danych”
48
Proste metody sortowania, do których zaliczają się: sortowanie
bąbelkowe, sortowanie przez wstawianie oraz sortowanie przez selekcję
ekstremum, są metodami powolnymi, a ich złoŜoność zwykle wynosi Θ
(n^2). PoniŜszy rysunek oparty jest o realne pomiary i prezentuje po-
równanie czasów działania w zaleŜności od rozmiaru problemu trzech
wymienionych metod.
Rysunek pokazuje takŜe wykres dla metody stoogesort (jako cie-
kawostka), opisaną w [1] oraz zmodyfikowaną metodę sortowania przez
wstawianie. Modyfikacja tej metody polega na dodaniu algorytmu wyszu-
kiwania binarnego w posortowanej części ciągu celem znalezienia miej-
sca na wstawienie nowego elementu.
Z rysunku odczytać moŜna, Ŝe:
•
najmniej wydajną jest metodą jest sortowanie bąbelkowe (poza stoo-
gesort),
•
metody sortowania przez wstawianie oraz przez selekcję ekstremum
mają zbliŜoną efektywność działania,
•
zmodyfikowana metoda sortowania przez wstawianie jest znacznie
bardziej efektywna, choć jej złoŜoność pozostaje bez zmian.
Ćwiczenie 8. Proste metody sortowania
49
Zadania do samodzielnego wykonania
Zadanie 26.
Sortowanie bąbelkowe
Plik:
prog26-babelkowe.cc
PołoŜenie:
~/aisd/zad26-babelkowe/
Uruchamianie:
./prog26-babelkowe
Treść:
Narysuj schemat blokowy metody sortowania bąbelkowego. Napisz
pseudokod sortowania bąbelkowego, odpowiadający naszkicowanemu
schematowi blokowemu.
Napisz program, który wypełnia statyczną tablicę 100-elementową licz-
bami całkowitymi, dodatnimi z przedziału -100..100. Program wypisuje
początkowy stan tablicy na ekran oraz sumę liczb z tablicy. Następnie
wykonywane jest sortowanie metodą bąbelkową. Zawartość posortowa-
nej tablicy, wraz z sumą liczb, wypisywane są na ekran.
Program nie moŜe wymagać Ŝadnej interakcji ze strony uŜytkownika.
Wskazówki:
•
wykorzystaj funkcje
time()
oraz
srand()
w celu zainicjalizowania ge-
neratora liczb losowych,
•
zwróć uwagę na równość wartości sum liczb przed sortowaniem i po
sortowaniu.
Zadanie 27.
Sortowanie przez wstawianie
Plik:
prog27-wstawianie.cc
PołoŜenie:
~/aisd/zad27-wstawianie/
Uruchamianie: ./prog27-wstawianie <rozmiar> <plik_we> <plik_wy>
Treść:
Napisz program, który wczytuje z linii komend trzy parametry:
•
<rozmiar>
- rozmiar tablicy na liczby całkowite typu
integer
,
•
<plik_we>
- nazwa pliku wejściowego z losowymi liczbami całkowitymi
typu
integer
zapisanymi w jednym wierszu, oddzielonymi pojedyn-
czymi spacjami,
„Algorytmy i Struktury Danych”
50
•
<plik_wy>
- nazwa pliku wyjściowego, który zawierał będzie posorto-
wane liczby zapisane w jednym wierszu, oddzielone pojedynczymi spa-
cjami.
Program powinien działać według schematu:
•
utworzenie dynamicznej tablicy o rozmiarze
<rozmiar>
,
•
wczytanie do tablicy liczb z pliku o nazwie
<plik_we>
,
•
obliczenie sumy liczb w tablicy,
•
uruchomienie zegara (odczytanie wartości zegara),
•
posortowanie tablicy metodą przez wstawianie,
•
zatrzymanie zegara (ponowne odczytanie wartości zegara),
•
obliczenie sumy liczb w tablicy wynikowej,
•
zapisanie liczb z tablicy do pliku
<pliku_wy>
w taki sam sposób, jak
były zapisane w pliku wejściowym,
•
usunięcie tablicy z pamięci,
•
wypisanie na ekran:
o
sumy liczb przed sortowaniem,
o
sumy liczb po sortowaniu,
o
czas sortowania w milisekundach.
Wskazówki:
•
wykorzystaj słowa kluczowe
new
oraz
delete
do dynamicznej rezerwa-
cji i usuwania tablicy z pamięci,
•
wykorzystaj funkcje
time()
oraz
srand()
w celu odczytania wartości
zegara oraz zainicjalizowania generatora liczb losowych,
•
zabezpiecz program przed błędnym podaniem rozmiaru tablicy w sto-
sunku do ilości liczb w pliku wejściowym,
•
program nie moŜe wymagać Ŝadnej interakcji od uŜytkownika.
Ćwiczenie 8. Proste metody sortowania
51
Zadanie 28.
Sortowanie przez selekcję ekstremum
Plik:
prog28-selekcja.cc
PołoŜenie:
~/aisd/zad28-selekcja/
Uruchamianie:
./prog28-selekcja <rozmiar> <plik_we> <plik_wy>
Treść:
Napisz program, który spełnia funkcjonalność taką samą jak program z
zadania poprzedniego, ale wykonujący sortowanie metodą sortowania
przez selekcję ekstremum.
Zadanie 29.
Porównanie prostych metod sortowania
Plik:
dok29-sortowanieproste.sxw
PołoŜenie:
~/aisd/zad29-sortowanieproste/
Treść:
Wykonaj opracowanie porównawcze prostych metod sortowania:
•
sortowanie bąbelkowe,
•
sortowanie przez wstawianie,
•
sortowanie przez selekcję ekstremum.
Wskazówki:
1.
Do opracowania wykorzystaj programy z zadań z tego ćwiczenia,
program z dotyczącego sortowania bąbelkowego naleŜy rozbudować
tak, aby wczytywał do sortowania liczby z zadanego pliku, posorto-
wane liczby zapisywał do pliku wynikowego, a takŜe podawał czas
sortowania.
2.
W opracowaniu naszkicuj schemat blokowy kaŜdej z metod (tylko
etap sortowania, bez pozostałych funkcji) oraz napisz ich pseudokod.
3.
Zasadniczym elementem opracowania mają być trzy wykresy czasów
sortowania powstałe w zaleŜności od charakteru danych wejściowych:
o
dane wejściowe są losowe,
o
dane wejściowe są posortowane rosnąco,
o
dane wejściowe są posortowane malejąco.
4.
Na kaŜdym wykresie naleŜy wykreślić 3 krzywe prezentujące po-
szczególne metody sortowania w oparciu o schemat:
„Algorytmy i Struktury Danych”
52
o
oś X reprezentuje wielkość problemu (ilość liczb do posor-
towania),
o
oś Y reprezentuje czas sortowania (w sekundach).
5.
NaleŜy tak dobrać wielkości problemów, aby liczba pomiarów dla da-
nej metody i danego typu danych wejściowych mieściła się w prze-
dziale 10..30, a czas sortowania najgorszego przypadku nie przekra-
czał 500 sekund, ale teŜ nie był krótszy niŜ 100 sekund.
6.
Pozostałe elementy dokumentacji opracuj tak jak to zostało opisane
w Ćwiczeniu 1 (str. 15) niniejszego skryptu.
Ćwiczenie 9.
Zaawansowane metody sortowania
Cel ćwiczenia
Celem ćwiczenia jest poznanie, zaimplementowanie, przetestowa-
nie i porównanie trzech zaawansowanych (szybkich) metod sortowania:
shell, stogowego (kopcowego) oraz szybkiego.
Wiadomości wstępne
Przed przystąpieniem do laboratorium naleŜy zapoznać się z na-
stępującymi zagadnieniami teoretycznymi dotyczącymi zaawansowa-
nych metod sortowania:
•
sortowanie shell (ang. shell sort),
•
sortowanie stogowe/kopcowe (ang. heap sort),
•
sortowanie szybkie (ang. quick sort).
Wskazówka:
Thomas Cormen, „Algorytmy i Struktury Danych”,
rozdział 7 i 8, str. 173 – 205,
Opis metod sortowania shell znaleźć moŜna w sieci Internet.
„Algorytmy i Struktury Danych”
54
Zaawansowane (szybkie) metody sortowania, do których zaliczają
się: sortowanie shell, sortowanie stogowe (kopcowe) oraz sortowanie
szybkie, są metodami znacznie wydajniejszymi niŜ te omawiane w po-
przednim ćwiczeniu. ZłoŜoność metod zaawansowanych to przewaŜnie
Θ (n lg n). PoniŜszy rysunek oparty jest o realne pomiary i prezentuje
porównanie czasów działania w zaleŜności od rozmiaru problemu trzech
wymienionych metod.
Rysunek pokazuje takŜe wykres dla metod: przez zliczanie i przez
scalanie (jako ciekawostka), opisane w [1] oraz zmodyfikowaną metodę
sortowania szybkiego. Na rysunku zabrakło metody shell, gdyŜ jej wy-
kres będzie częścią jednego z zadań w tym ćwiczeniu.
Z rysunku odczytać moŜna, Ŝe:
•
najmniej wydajną jest metoda sortowania stogowego (kopcowego),
•
metoda sortowania szybkiego jest najlepsza i istotnie jest to najszyb-
sza ze znanych metod sortowania,
•
załamania na wykresie przy pewnych rozmiarach problemu wynikają z
zapełnienia pamięci RAM (256 MB) komputera na którym były realizo-
wane obliczenia.
Ćwiczenie 9. Zaawansowane metody sortowania
55
Zwróć uwagę na wykres z poprzedniego ćwiczenia i zauwaŜ róŜni-
ce w rozmiarach problemów branych pod uwagę w pomiarach.
Zadania do samodzielnego wykonania
Zadanie 30.
Sortowanie shell
Plik:
prog30-shell.cc
PołoŜenie:
~/aisd/zad30-shell/
Uruchamianie:
./prog30-shell <rozmiar> <plik_we> <plik_wy>
Treść:
Napisz program, który spełnia funkcjonalność taką, jak programy z po-
przedniego ćwiczenia, ale wykonujący sortowanie metodą sortowania
shell.
Zadanie 31.
Sortowanie stogowe/kopcowe
Plik:
prog31-stogowe.cc
PołoŜenie:
~/aisd/zad31-stogowe/
Uruchamianie:
./prog31-stogowe <rozmiar> <plik_we> <plik_wy>
Treść:
Napisz program, który spełnia funkcjonalność taką, jak programy z po-
przedniego ćwiczenia, ale wykonujący sortowanie metodą sortowania
stogowego (często nazywaną metodą sortowania kopcowego). Wyko-
rzystaj operacje kolejkowe dla kopca binarnego.
Zadanie 32.
Sortowanie szybkie
Plik:
prog32-szybkie.cc
PołoŜenie:
~/aisd/zad32-szybkie/
Uruchamianie:
./prog32-szybkie <rozmiar> <plik_we> <plik_wy>
Treść:
Napisz program, który spełnia funkcjonalność taką, jak programy z po-
przedniego ćwiczenia, ale wykonujący sortowanie metodą sortowania
szybkiego.
„Algorytmy i Struktury Danych”
56
Zadanie 33.
Porównanie zaawansowanych metod sor-
towania
Plik:
dok33-sortowaniezaawansowane.sxw
PołoŜenie:
~/aisd/zad33-sortowaniezaawansowane/
Treść:
Wykonaj opracowanie porównawcze prostych metod sortowania:
•
sortowanie shell,
•
sortowanie kopcowe/stogowe,
•
sortowanie szybkie.
Opracowanie wykonaj według takich samych wskazówek jak opracowanie
z ćwiczenia dotyczącego prostych metod sortowania.
Ćwiczenie 10.
Hash
Cel ćwiczenia
Celem ćwiczenia jest poznanie technik związanych z obliczaniem
(czy teŜ wyznaczaniem) wartości hash z zadanego ciągu znaków, a takŜe
moŜliwości wykorzystania własności wartości w róŜnych zastosowaniach.
Wiadomości wstępne
Przed przystąpieniem do laboratorium naleŜy zapoznać się z na-
stępującymi zagadnieniami teoretycznymi dotyczącymi hash:
•
pojęcia: hash, klucz, indeks, kolizja,
•
tablice:
o
z adresowaniem bezpośrednim,
o
z haszowaniem,
•
funkcje haszujące,
•
haszowanie:
o
modularne,
o
przez mnoŜenie,
o
uniwersalne,
o
adresowanie otwarte.
Wskazówka:
Thomas Cormen, „Algorytmy i Struktury Danych”,
rozdział 12, str. 256 – 283.
„Algorytmy i Struktury Danych”
58
Zadania do samodzielnego wykonania
Zadanie 34.
Hashowanie z metodą łańcuchową
Plik:
prog34-hash.cc
PołoŜenie:
~/aisd/zad34-hash/
Uruchamianie:
./prog34-hash <rozmiar> <metoda>
Treść:
Napisz program, który wykonuje wczytanie słownika wyrazów języka
angielskiego z pliku: '/usr/share/dict/linux.words'. Plik ten jest dostępny
na serwerze oraz w kaŜdej dystrybucji systemu Linux. Plik ma być wczy-
tywany do tablicy z haszowaniem z metodą łańcuchową jako metodą
rozwiązywania kolizji.
Program pobiera z linii komend dwa parametry:
•
<rozmiar>
– określa rozmiar dynamicznie tworzonej tablicy ze wskaź-
nikami do list (łańcuchów),
•
<metoda>
- określa funkcję haszującą:
o
mod
– haszowanie modularne,
o
mul
– hashowanie przez mnoŜenie,
o
uni
– haszowanie uniwersalne.
Program, po wczytaniu słownika, ma wypisać na ekran:
•
liczbę wczytanych wyrazów,
•
długość najdłuŜszego łańcucha,
•
ogólną liczbę kolizji (suma długości łańcuchów o długości więcej niŜ
jeden, minus liczba łańcuchów),
•
liczba wykorzystanych komórek w tablicy (liczba łańcuchów),
•
liczbę wpisów bez kolizji (liczba łańcuchów o długości dokładnie jeden),
•
liczba wpisów nie wykorzystanych (liczba pustych komórek w tablicy).
Wskazówki:
•
w przypadku konieczności podania jakichś parametrów do funkcji ha-
szujących – obierz te parametry arbitralnie.
Uwagi:
•
program nie moŜe wymagać Ŝadnej interakcji od uŜytkownika –
wszystkie parametry mają być podawane z linii komend,
Ćwiczenie 10. Hash
59
•
przed zakończeniem działania program zwalnia program z obiektów
dynamicznych.
Zadanie 35.
Hashowanie – badania
Plik:
dok35-hash.sxw
PołoŜenie:
~/aisd/zad35-hash/
Treść:
Wykorzystując program z poprzedniego zadania wykonaj opracowanie
zawierające wyniki przeprowadzonych badań wczytywanego słownika
dla:
•
trzech funkcji haszujących,
•
zmiennego rozmiaru tablicy haszującej w zakresach:
o
od 0 do 1000 z krokiem 100,
o
od 0 do 10 000 z krokiem 1000.
Wskazówki:
•
zbadaj jakość funkcji haszujących zwracając uwagę na wartości wypi-
sywane przez program (opis tych liczb zawiera zadanie programistycz-
ne),
•
zinterpretuj otrzymane wartości,
•
wykreśli odpowiednie wykresy,
•
poszukaj najlepszych wartości godząc ilość zajętej pamięci przez tabli-
cę z jakością rozkładu (jakością funkcji haszujacej),
•
zaproponuj najlepsze rozwiązanie,
•
dokument wykonaj zgodnie ze wskazówkami podanymi w Ćwiczeniu 1
niniejszego skryptu.
Ćwiczenie 11.
Grafy
Cel ćwiczenia
Celem ćwiczenia jest poznanie struktur grafowych, ich własności
oraz podstawowych algorytmów operujących na nich.
Wiadomości wstępne
Przed przystąpieniem do laboratorium naleŜy zapoznać się z na-
stępującymi zagadnieniami teoretycznymi dotyczącymi grafów:
•
pojęcia: graf skierowany/nieskierowany, wierzchołek, krawędź, sto-
pień, ścieŜka, droga, osiągalność wierzchołka, graf spójny/niespójny,
grafy izomorficzne, drzewo, las, multigraf, hipergraf, cyklicz-
ność/acykliczność, itp.,
•
podstawowe algorytmy grafowe: przeszukiwanie wszerz, w głąb,
•
zaawansowane algorytmy grafowe: minimalne drzewa rozpinające,
najkrótsze ścieŜki z jednym źródłem, najkrótsze ścieŜki między wszyst-
kimi parami wierzchołków, maksymalny przepływ.
Wskazówka:
Thomas Cormen, „Algorytmy i Struktury Danych”,
podrozdział 5.4, str. 113 – 116.
Thomas Cormen, „Algorytmy i Struktury Danych”,
rozdziały 23 – 27, str. 526 – 712.
„Algorytmy i Struktury Danych”
62
Zadania do samodzielnego wykonania
Zadanie 36.
Algorytm Floyda-Warshalla
Treść:
Algorytm Floyda-Warshalla to metoda słuŜąca wyznaczeniu najkrótszej
ścieŜki między wszystkimi parami wierzchołków w grafie skierowanym
G=(V, E). Algorytm ten szczegółowo został opisany w [1], str. 640.
Wykonaj kroki algorytmu dla grafu:
a)
o 3 wierzchołkach i 5 krawędziach:
58
22
∞
65
∞
-7
∞
74
∞
b)
o czterech wierzchołkach i dwunastu krawędziach:
∞
97
82
73
97
25
17 -14
-9
56
78 -16
69
∞
∞
∞
c)
o pięciu wierzchołkach i piętnastu krawędziach:
4
54
82
∞
∞
29
∞
∞
-15
∞
0
21
∞
75
∞
∞
88
61
∞
8
75
53
78 -20
∞
Odpowiedzi:
a)
graf o 3 wierzchołkach i 5 krawędziach, po 3 kroku:
58
22
15
65
67
-7
139
74
67
b)
graf o 4 wierzchołkach i 12 krawędziach, po 4 kroku:
73
97
82
66
8
25
17 -14
-9
56
73 -16
69 166 151 135
Ćwiczenie 11. Grafy
63
c)
graf o 5 wierzchołkach i 15 krawędziach, po 5 kroku:
4 54 82 27 35
29 46 34 -27 -19
0 21 55 -6 2
49 61 49 -12 -4
29 41 29 -32 -24
Zadanie 37.
Przeszukiwanie wszerz – listy sąsiedztwa
Plik:
prog37-grafwszerzlisty.cc
PołoŜenie:
~/aisd/zad37-grafwszerzlisty/
Uruchamianie:
./prog37-grafwszerzlisty <plik_we> <zrodlo>
Treść:
Napisz program przeszukiwania wszerz grafu spójnego, niekierowa-
nego, bez wag w oparciu o jego reprezentację na listach sąsiedztwa.
Program jako dane wejściowe przyjmuje nazwę pliku z grafem w postaci:
<liczba wierzholkow>
[<numer wierzcholka sasiedniego>]+
...
Pierwszy wiersz pliku określa liczbę wierzchołków, a zarazem liczbę na-
stępujących wierszy. KaŜdy kolejny wiersz dotyczy kolejnego wierzchołka
i zawiera listę numerów wierzchołków sąsiadujących (połączonych do-
kładnie jedną krawędzią). Numery te są oddzielone spacjami. PoniewaŜ z
załoŜenia mamy do czynienia z grafem spójnym, to numery wierszy nie
są potrzebne, przy czym przyjąć naleŜy, Ŝe numeracja wierzchołków na-
stępuje od numeru 1.
Przykład pliku wejściowego:
4
2 3 4
1 3
1 2
1
„Algorytmy i Struktury Danych”
64
Oznacza, Ŝe chodzi o graf postaci:
Drugim parametrem wywołania programu jest numer wierzchołka będą-
cego źródłem, a więc wierzchołka od którego wykonywane będzie prze-
szukiwanie wszerz.
Wynikiem działania programu powinny być informacje:
•
o charakterze wczytanego grafu, ilości wierzchołków i jego spójności
(proszę zwrócić uwagę, Ŝe sam fakt występowania sąsiada dla kaŜdego
wierzchołka nie przesądza jeszcze o spójności grafu),
•
o najdłuŜszej z najkrótszych ścieŜek, podając numer (numery, jeśli
jest kilka takich ścieŜek) najdalszego wierzchołka wraz z numerami
wierzchołków wyznaczających tę ścieŜkę,
•
czas działania algorytmu mierzony od chwili zakończenia wczytywania
grafu z pliku do chwili przed wypisaniem wyników.
Program nie moŜe wymagać Ŝadnej interakcji z uŜytkownikiem.
Zadanie 38.
Przeszukiwanie w głąb – macierz sąsiedz-
twa
Plik:
prog38-grafwglabmacierz.cc
PołoŜenie:
~/aisd/zad38-grafwglabmacierz/
Uruchamianie:
./prog38-grafwglabmacierz <plik_we> <zrodlo>
Treść:
Napisz program przeszukiwania w głąb grafu spójnego, skierowanego,
z wagami w oparciu o jego reprezentację na macierzy sąsiedztwa.
Ćwiczenie 11. Grafy
65
Program jako dane wejściowe przyjmuje nazwę pliku z grafem w postaci:
<liczba wierzcholkow>
[<numer wierzcholka> <numer wierzcholka sasiedniego> \
<waga krawedzi incydentnej>]+
...
Pierwszy wiersz pliku określa liczbę wierzchołków, a zarazem liczbę na-
stępujących wierszy. KaŜdy kolejny wiersz dotyczy kolejnego wierzchołka
i zawiera jego numer oraz listę wierzchołków sąsiadujących wraz z wa-
gami krawędzi incydentnych. Numery i wartości wag są oddzielone spa-
cjami. Wartości wszystkich wag są tylko dodatnie, co oznacza, Ŝe opisane
są tylko sytuacje krawędzi incydentnych „do” danego wierzchołka. W
odróŜnieniu od poprzedniego zadania, w tym przypadku wiersze muszą
być numerowane, poniewaŜ jeśli wierzchołek miałby tylko krawędzie in-
cydentne „z” niego, nie byłby zapisany.
Przykład pliku wejściowego:
4
1 3 7
2 1 13 3 9
3 2 9
4 1 15
Oznacza, Ŝe chodzi o graf postaci:
Drugim parametrem wywołania programu jest numer wierzchołka będą-
cego źródłem, a więc wierzchołka od którego wykonywane będzie prze-
szukiwanie w głąb.
„Algorytmy i Struktury Danych”
66
Wynikiem działania programu powinny być informacje:
•
o charakterze wczytanego grafu, ilości wierzchołków i jego spójności
(proszę zwrócić uwagę, Ŝe sam fakt występowania sąsiada dla kaŜdego
wierzchołka nie przesądza jeszcze o spójności grafu),
•
o najdłuŜszej z najkrótszych ścieŜek, podając numer (numery, jeśli
jest kilka takich ścieŜek) najdalszego wierzchołka wraz z numerami
wierzchołków wyznaczających tę ścieŜkę oraz sumą wag,
•
o najdroŜszej z najtańszych ścieŜek (wartość ścieŜki wyznacza suma
wag krawędzi łączących źródło z danym wierzchołkiem), podając nu-
mer (numery, jeśli jest kilka takich ścieŜek) wierzchołka docelowego
wraz z numerami wierzchołków wyznaczających tę ścieŜkę oraz sumą
wag,
•
czas działania algorytmu mierzony od chwili zakończenia wczytywania
grafu z pliku do chwili przed wypisaniem wyników.
Ćwiczenie 12.
Drzewa i kopce
Cel ćwiczenia
Celem ćwiczenia jest poznanie szczególnych struktur grafowych
jakimi są drzewa i kopce, ich własności oraz podstawowych algorytmów
operujących na nich.
Wiadomości wstępne
Przed przystąpieniem do laboratorium naleŜy zapoznać się z na-
stępującymi zagadnieniami teoretycznymi dotyczącymi struktur drzewia-
stych i kopców:
•
pojęcia: drzewo, kopiec, węzeł, wysokość, poprzednik/następnik, oj-
ciec, syn, brat, liść, drzewo pozycyjne, prawy/lewy następnik, pod-
drzewo prawe/lewe, itp.,
•
drzewa poszukiwań binarnych,
•
drzewa czerwono-czarne,
•
B-drzewa,
•
kopce dwumianowe,
•
kopce Fibonacciego,
•
struktury danych dla zbiorów rozłącznych.
Wskazówka:
Thomas Cormen, „Algorytmy i Struktury Danych”,
podrozdział 5.5, str. 117 – 125 (drzewa),
„Algorytmy i Struktury Danych”
68
Thomas Cormen, „Algorytmy i Struktury Danych”,
rozdziały 13 i 14, str. 284 – 323 (drzewa),
Thomas Cormen, „Algorytmy i Struktury Danych”,
rozdziały 19 – 22, str. 433 – 525 (drzewa i kopce).
Zadania do samodzielnego wykonania
Zadanie 39.
Drzewa BST
Treść:
Wykreśl z podanych liczb drzewo poszukiwań binarnych BST, a następnie
przeszukaj w porządkach pre-, in- i post- order:
a)
Liczby: 38, 96, 40, 29, 61, 21, 23, 31, 15, 98.
b)
Liczby: 78, 12, 16, 38, 86, 11, 57, 19, 35, 31, 34, 22, 90, 98, 50,
65, 94, 51, 47, 97, 13, 73, 40, 68, 63, 39, 93, 87, 58, 10.
c)
Liczby: 22, 13, 35, 80, 12, 79, 42, 27, 15, 52, 41, 30, 74, 82, 93,
62, 37, 23, 50, 60, 94, 69, 76, 77, 95, 49, 86, 38, 68, 48, 63, 73,
32, 91, 87, 88, 54, 14, 34, 31.
Odpowiedzi:
a) Porządki:
Pre-order: 38, 29, 21, 15, 23, 31, 96, 40, 61, 98.
In-order: 15, 21, 23, 29, 31, 38, 40, 61, 96, 98.
Post-order: 15, 23, 21, 31, 29, 61, 40, 98, 96, 38.
b) Porządki:
Pre-order: 78, 12, 11, 10, 16, 13, 38, 19, 35, 31, 22, 34, 57, 50, 47, 40,
39, 51, 65, 63, 58, 73, 68, 86, 90, 87, 98, 94, 93, 97.
In-order: 10, 11, 12, 13, 16, 19, 22, 31, 34, 35, 38, 39, 40, 47, 50, 51,
57, 58, 63, 65, 68, 73, 78, 86, 87, 90, 93, 94, 97, 98.
Post-order: 10, 11, 13, 22, 34, 31, 35, 19, 39, 40, 47, 51, 50, 58, 63,
68, 73, 65, 57, 38, 16, 12, 87, 93, 97, 94, 98, 90, 86, 78.
c) Porządki:
Pre-order: 22, 13, 12, 15, 14, 35, 27, 23, 30, 32, 31, 34, 80, 79, 42, 41,
37, 38, 52, 50, 49, 48, 74, 62, 60, 54, 69, 68, 63, 73, 76, 77, 82, 93,
86, 91, 87, 88, 94, 95.
Ćwiczenie 12. Drzewa i kopce
69
In-order: 12, 13, 14, 15, 22, 23, 27, 30, 31, 32, 34, 35, 37, 38, 41, 42,
48, 49, 50, 52, 54, 60, 62, 63, 68, 69, 73, 74, 76, 77, 79, 80, 82, 86,
87, 88, 91, 93, 94, 95.
Post-order: 12, 14, 15, 13, 23, 31, 34, 32, 30, 27, 38, 37, 41, 48, 49,
50, 54, 60, 63, 68, 73, 69, 62, 77, 76, 74, 52, 42, 79, 88, 87, 91, 86,
95, 94, 93, 82, 80, 35, 22.
Zadanie 40.
Słownik
Plik:
prog40-slownik.cc
PołoŜenie:
~/aisd/zad40-slownik/
Uruchamianie:
./prog40-slownik <slownik> <dokument>
Treść:
Napisz program, który implementuje słownik wyrazów języka angielskie-
go i sprawdza poprawność wyrazów z zadanego dokumentu.
Program pobiera z linii poleceń dwa parametry:
•
<slownik>
- plik ze słownikiem wyrazów zapisanych jeden pod drugim,
np.: '/usr/share/dict/linux.words' w systemie Linux,
•
<dokument>
- plik z tekstem, który naleŜy sprawdzić.
Zadaniem programu jest sprawdzić, czy wyrazy z pliku
<dokument>
znaj-
dują się wśród wyrazów z pliku
<slownik>
.
Budowa słownika
Program wczytuje słownik z pliku
<slownik>
do pamięci do struktury
drzewa wg poniŜszego schematu:
„Algorytmy i Struktury Danych”
70
Proponowana budowa pojedynczego węzła drzewa, w skład którego
wchodzą następujące elementy:
•
literka – zmienna typu 'char' zawierająca w sobie literę wyrazu,
•
tworzy – zmienna typu 'boolean' określająca:
o
'TRUE' oznacza, Ŝe dana litera kończy juŜ wyraz (na sche-
macie oznaczone symbolem gwiazdki *),
o
'FALSE' oznacza, Ŝe dana litera nie kończy jeszcze wyrazu,
•
brat – odsyłacz do równoległego węzła:
o
jeśli ma wartość NULL oznacza to, Ŝe w tej samej pozycji
nie ma juŜ więcej liter,
o
jeśli wskazuje na jakiś węzeł, wówczas literka z wskazy-
wanego węzła moŜe znaleźć się na aktualnej pozycji (np.
wyrazy 'ala' i 'arab' na drugiej pozycji mają odpowiednio li-
terki 'l' i 'r' dla tego na schemacie węzeł z literką 'l' wska-
zuje na brata który posiada literkę 'r'),
•
syn – odsyłacz do następnego węzła (kolejnej literki w wyrazie) – jeśli
ma wartość NULL oznacza to, Ŝe jest to ostatnia litera i węzeł oznaczo-
ny jest zmienną 'tworzy' ustawioną na 'TRUE'.
Ćwiczenie 12. Drzewa i kopce
71
Wszystkie węzły, które nie posiadają zaznaczonych na schemacie 'braci',
wskaźnik 'brat' ustawiony mają na wartość 'NULL'. Na schemacie ozna-
czenia 'NULL' dla braci zostały pominięte ze względu na jego przejrzy-
stość.
Prześledźmy proces budowy części słownika:
•
słownik zaczyna się od wskaźnika 'slownik',
•
pusty słownik ma ustawiony wskaźnik 'slownik' na NULL,
•
wstawiamy wyraz 'ala':
o
zaczynamy od korzenia drzewa,
o
literka 'a' jest początkiem wyrazu 'ala', schodzimy w dół
słownika i tworzymy nowy węzeł, na który wskazuje 'slow-
nik', umieszczamy literkę 'a' ustawiając 'brata' i 'syna' na
NULL, zmienną 'tworzy' na 'FALSE',
o
bierzemy kolejną literkę, którą jest 'l' i poniewaŜ 'syn' li-
terki 'a' jest ustawiony na NULL, tworzymy nowy węzeł, na
który wskazuje 'syn' poprzedniego węzła (ten z literką 'a'),
umieszczamy literkę 'l', braci i syna ustawiamy na NULL,
zmienną 'tworzy' na 'FALSE',
o
bierzemy kolejną literkę, którą jest 'a' i poniewaŜ 'syn' li-
terki 'l' jest ustawiony na NULL, tworzymy nowy węzeł, na
który wskazuje 'syn' poprzedniego węzła (ten z literką 'l'),
umieszczamy literkę 'a', braci i syna ustawiamy na NULL,
zmienną 'tworzy' ustawiamy na 'TRUE' (koniec wyrazu),
•
wstawiamy wyraz 'alarm':
o
zaczynamy od korzenia drzewa,
o
schodząc w dół zauwaŜamy, Ŝe literka 'a' jest juŜ w drze-
wie,
o
schodząc w dół zauwaŜamy, Ŝe literka 'l' teŜ jest juŜ w
drzewie,
o
schodząc w dół zauwaŜamy, Ŝe literka 'a' takŜe jest juŜ w
drzewie,
o
schodząc w dół zauwaŜamy, Ŝe poniewaŜ 'syn' literki 'a'
jest ustawiony na NULL, tworzymy nowy węzeł, na który
wskazuje 'syn' poprzedniego węzła (ten z literką 'a'),
„Algorytmy i Struktury Danych”
72
umieszczamy literkę 'r', braci i syna ustawiamy na NULL,
zmienną 'tworzy' na 'FALSE',
o
z literką 'm' postępujemy analogicznie do ostatniej literki
'a' z wyrazu 'ala',
•
wstawiamy wyraz 'albo':
o
zaczynamy od korzenia drzewa,
o
schodząc w dół zauwaŜamy, Ŝe literka 'a' jest juŜ w drze-
wie,
o
schodząc w dół zauwaŜamy, Ŝe literka 'l' teŜ jest juŜ w
drzewie,
o
schodząc w dół zauwaŜamy, Ŝe jest literka 'a', a my mamy
w wyrazie literkę 'b':
przechodzimy w prawo w poszukiwaniu literki 'b',
'brat' węzła z literką 'a' jest ustawiony na 'NULL',
tworzymy nowy węzeł, na który wskazuje 'brat' po-
przedniego węzła (ten z literką 'a'), umieszczamy li-
terkę 'b', braci i syna ustawiamy na NULL, zmienną
'tworzy' na 'FALSE',
o
z literką 'o' postępujemy analogicznie do ostatniej literki 'a'
z wyrazu 'ala' – to znaczy dodajemy ją jako 'syna' w sto-
sunku do literki 'b' i ustawiamy odpowiednio wskaźniki 'sy-
n', 'brat' oraz zmienną 'tworzy'.
•
itd.
Sprawdzanie pisowni
ZałóŜmy, Ŝe plik
<dokument>
zawiera następujący wpis:
al
ala
alarm
atom
alarmami
Ćwiczenie 12. Drzewa i kopce
73
Zadaniem programu, po wczytaniu słownika do pamięci, jest przeskano-
wanie pliku
<dokument>
i wypisaniu wszystkich wyrazów z podaniem ko-
mentarzy w następujący sposób:
'al' nie jest wyrazem, jest pocz
ą
tkiem wyrazu,
'ala' jest wyrazem, jest te
Ŝ
pocz
ą
tkiem innego wyrazu,
'alarm'
jest
wyrazem,
nie
jest
pocz
ą
tkiem
innego
wyrazu,
'atom' nie jest wyrazem ze słownika,
'alarmami' nie jest wyrazem ze słownika.
Uwagi:
•
program nie moŜe wymagać Ŝadnej interakcji od uŜytkownika –
wszystkie parametry mają być podawane z linii komend,
•
przed zakończeniem działania program zwalnia pamięć z obiektów dy-
namicznych.
Ćwiczenie 13.
Algorytmy teorioliczbowe
Cel ćwiczenia
Celem ćwiczenia jest poznanie podstawowych, ale bardzo waŜ-
nych algorytmów teorioliczbowych. Ćwiczenie obejmuje takŜe elementy
kryptografii, która opiera się o zaawansowane algorytmy teorioliczbowe.
Wiadomości wstępne
Przed przystąpieniem do laboratorium naleŜy zapoznać się z na-
stępującymi zagadnieniami teoretycznymi dotyczącymi algorytmów
teorioliczbowych:
•
pojęcia podstawowe: podzielność, wielokrotność, dzielniki (trywialne),
czynniki, liczby pierwsze i złoŜone, iloraz, reszta z dzielenia, wspólny
dzielnik, liczby względnie pierwsze, NWW, NWD,
•
arytmetyka modularna: grupa i jej własności,
•
elementy kryptografii: tekst jawny, kryptogram, algorytm kryptogra-
ficzny, klucz kryptograficzny, klucz symetryczny, klucz asymetryczny,
kryptoanaliza,
•
kody Hoffmana jako efektywna metoda kompresji danych.
Wskazówka:
Thomas Cormen, „Algorytmy i Struktury Danych”,
rozdział 31, str. 870 – 928.
„Algorytmy i Struktury Danych”
76
Zadania do samodzielnego wykonania
Zadanie 41.
Test Millera-Rabina
Plik:
prog41-test.cc
PołoŜenie:
~/aisd/zad41-test/
Uruchamianie:
./prog41-test <liczba>
Treść:
Napisz program implementujący algorytm Millera-Rabina, który słuŜy
probabilistycznemu testowaniu duŜych liczb celem stwierdzenia, czy dana
liczba jest pierwsza. Program przyjmował będzie jako parametr długi
napis reprezentujący duŜą liczbę całkowitą w zapisie dziesiętnym. Wyj-
ściem programu ma być stwierdzenie, czy zadana liczba jest pierwsza,
czy teŜ nie.
Zadanie 42.
Algorytmy kryptograficzne
Plik:
prog42-kryptografia.cc
PołoŜenie:
~/aisd/zad42-kryptografia/
Uruchamianie:
./prog42-kryptografia <algorytm> <crypt|decrypt> \
<plik_we> <plik_wy> [<klucz>]
Treść:
Napisz program implementujący kilka spośród wymienionych niŜej algo-
rytmów kryptograficznych:
•
szyfr Cezara (
cezar
), dla którego kluczem niech będzie wielkość prze-
sunięcia liter w alfabecie (takie samo dla wszystkich liter),
•
prosty klucz (
prosty
) opiera swoje działanie na podmianie kaŜdej lite-
ry tekstu literą powstałą z przesunięcia w alfabecie o ilość pozycji za-
daną w kluczu (przykład, poniŜszy rysunek); przyjmij, Ŝe klucz to ciąg
cyfr, a więc jedno przesunięcie moŜe nastąpić w zakresie 0...9,
Ćwiczenie 13. Algorytmy teorioliczbowe
77
•
szyfr podstawieniowy ASCII (
ascii
), którego działanie polega na stałej
podmianie liter (lub sekwencji) na inne; przyjmij działanie w którym
znaki zamieniane są na ich kody ASCII, przy czym naleŜy je zapisywać
ze stałą długością znaków aby uniknąć niejednoznaczności przy odszy-
frowywaniu (tzn. przyjąć 3-cyfrową reprezentację, a dla liczb krótszych
dopisać odpowiednią ilość ‘0’ na początku),
•
ga-de-ry-po-lu-ki (
gadery
) to popularny szyfr harcerski, którego dzia-
łanie polega na podmianie liter z danej sylaby; inna odmiana tego szy-
fru to po-li-ty-ka-re-nu,
•
Rivest-Shamir-Adelman (
rsa
) najpopularniejszy (obok DSA) algorytm
kryptograficzny z kluczem publicznym; szczegółowy opis jego działania
czytelnik znajdzie w [1], str. 902.
Parametry programu:
•
<algorytm>
– skrócona nazwa algorytmu (spójrz na napisy w nawia-
sach na liście algorytmów),
•
<crypt|decrypt>
– określa, czy wykonywana będzie operacja szyfro-
wania, czy deszyfrowania,
•
<plik_we>
– nazwa pliku do zaszyfrowania/odszyfrowania,
•
<plik_wy>
– nazwa pliku do którego ma zostać zapisany krypto-
gram/tekst odszyfrowany,
•
<klucz>
– opcjonalny parametr będący wartością klucza, którą naleŜy
podać w przypadku algorytmów z kluczem.
„Algorytmy i Struktury Danych”
78
Zadanie 43.
Kryptoanaliza statystyczna
Plik:
prog43-kryptoanaliza.cc
PołoŜenie:
~/aisd/zad43-kryptoanaliza/
Uruchamianie:
./prog43-kryptoanaliza <dl_klucza> <plik_we>
Treść:
Metody szyfrowania oparte o klucz, zwłaszcza RSA i DSA, są bardzo trud-
ne do złamania, gdyŜ ich siła powiązana jest z ‘jakością’ klucza uŜytego
do zaszyfrowania. Przez jakość naleŜy rozumieć zarówno długość jak i
własności teorioliczbowe charakterystyczne dla danego algorytmu. Z ko-
lei większość metod szyfrowania opartych tylko o algorytm jest bardzo
łatwa do złamania, to znaczy bardzo łatwo odgadnąć algorytm, przy po-
mocy którego tekst został zaszyfrowany.
W tym ćwiczeniu naleŜy napisać program, który będzie wykonywał kryp-
toanalizę statystyczną do danych przygotowanych jak poniŜej:
•
wygeneruj duŜy (> 1 MB) plik z losowymi pseudozdaniami w języku
angielskim; moŜesz do tego posłuŜyć się programem z następnego
ćwiczenia,
•
na podstawie wygenerowanego pliku, wykonaj procentową statystykę
liter, charakterystyczną dla danego języka (w tym przypadku języka
angielskiego),
•
przygotuj duŜy (> 1 MB) plik (podobnie jak poprzedni), który będzie
tekstem jawnym w tym zadaniu,
•
zaszyfruj otrzymany plik przy pomocy jednego z algorytmów podsta-
wieniowych, najlepiej algorytmem z prostym kluczem (zadanie po-
przednie),
•
wykonaj kryptoanalizę statystyczną (napisz program ją wykonujący) i
spróbuj odtworzyć tekst jawny z kryptogramu, przy czym załoŜyć
moŜna, Ŝe znana jest długość klucza (i niech to będzie 5-10 cyfr) oraz
postać alfabetu (tzn. jakie litery są w alfabecie i jaką kolejność przyj-
mują).
Ćwiczenie 14.
Wyszukiwanie wzorca
Cel ćwiczenia
Celem ćwiczenia jest poznanie problematyki poszukiwania wzorca
oraz szeregu algorytmów rozwiązujących problem poszukiwania wzorca
w tekście.
Wiadomości wstępne
Przed przystąpieniem do laboratorium naleŜy zapoznać się z na-
stępującymi zagadnieniami dotyczącymi wyszukiwania wzorca:
•
tekst, wzorzec, alfabet, słowo,
•
przesunięcie a "występowanie od pozycji”,
•
poprawne i niepoprawne przesunięcie,
•
słowo puste, konkatenacja, prefiks, sufiks,
•
pojęcia z teorii liczb: przystawanie liczb modulo, kongruencja,
Wskazówka:
Thomas Cormen, „Algorytmy i Struktury Danych”,
Rozdział 32, str. 929 – 954.
„Algorytmy i Struktury Danych”
80
Zadanie 44.
Generator tekstu
Plik:
prog44-textgen.cc
PołoŜenie:
~/aisd/zad44-textgen/
Uruchamianie:
./prog44-textgen <plik-zrodlo> <plik-wynik> <dlugosc>
Treść:
Napisz program, który odczytuje zawartość pliku
<plik-zrodlo>
, w któ-
rym znajdują się pojedyncze słowa (np.
/usr/share/dict/linux.words
)
i układa w losowe pseudo-zdania, tzn. wyrazy oddzielone spacjami, z
uŜyciem wielkich liter, znaków interpunkcyjnych, itp. Zdania wynikowe
są zapisywane do
<plik-wynik>
, przy czym ilość wszystkich słów (cią-
gów oddzielonych spacjami) nie przekracza wartości parametru
<długo
ść
>
. Parametr długość jest liczbą całkowitą z przedziału
[0…1000000].
Zadanie 45.
Algorytm naiwny
Plik:
prog45-naiwny.cc
PołoŜenie:
~/aisd/zad45-naiwny/
Uruchamianie:
./prog45-naiwny <plik> <wzorzec>
Treść:
Działanie algorytmu naiwnego (rysunek poniŜej) polega na wyszukaniu
wszystkich wartości poprawnych przesunięć ‘s’ poprzez przejrzenie
wszystkich moŜliwych przesunięć oraz porównywanie wszystkich pozycji
z wzorca ‘P’ (ang. pattern) w tekście źródłowym ‘T’ (ang. text). Porów-
nywanie pozycji przy danym przesunięciu odbywa się od lewej do prawej,
lub od prawej do lewej.
Zakładając, Ŝe ‘n’ to długość tekstu, a ‘m’ to długość wzorca, wówczas ‘s’
zawiera się w przedziale [0...m-n+1].
Ćwiczenie 14. Algorytmy teorioliczbowe
81
Liczba wszystkich porównań wyraŜa się wzorem:
(n-m+1) * m
Zatem złoŜoność wynosi Θ (n*m).
Implementując algorytm naiwny napisz program słuŜący znajdowaniu
wszystkich poprawnych przesunięć dla danego wzorca w ustalonym tek-
ście. Tekst znajduje się w pliku tekstowym, do którego ścieŜka podana
zostaje do programu jako pierwszy parametr. Do wygenerowania pliku
wejściowego słuŜyć moŜe program z poprzedniego zadania.
Wzorzec, który ma zostać odnaleziony, zapisany jest jako drugi parametr
programu i powinien znajdować się w cudzysłowu (“ i ”) co umoŜliwia
zapisanie kilku słów, które są poszukiwane jako jeden, długi wzorzec.
Wyjściem programu jest zagregowana informacja, którą naleŜy ułoŜyć w
schemat:
•
Wzorzec ... zostal/nie zostal odnaleziony w pliku ...
•
Liczba wystapien wzorca:
•
Przesuniecia: ..., ..., ...
•
Czas dzialania algorytmu: ... [s].
Zadanie 46.
Algorytm nie taki naiwny
Plik:
prog46-nienaiwny.cc
PołoŜenie:
~/aisd/zad46-nienaiwny/
Uruchamianie:
./prog46-nienaiwny <plik> <wzorzec>
Treść:
Rozbuduj program z poprzedniego zadania do nie naiwnej postaci, tzn.
dodaj dwa elementy do algorytmu, które przyspieszą jego działanie.
Pierwsza poprawka obejmuje wprowadzenie mechanizmu przerywającego
dalsze porównania wzorca do tekstu (przy danym przesunięciu) w chwili
napotkania pozycji, na której porównywane elementy się róŜnią.
Druga poprawka polega na porównywaniu wzorca z tekstem, przy danym
przesunięciu, od prawej do lewej. Przed przystąpieniem do pętli, która
przesuwa okno wzorca po tekście, wykonywane jest wstępne przetwa-
„Algorytmy i Struktury Danych”
82
rzanie (ang. preprocessing) na wzorcu, którego wynik waŜy na sposobie
późniejszych porównań. I tak:
•
jeśli P[0] == P[1], to przy porównaniach jeśli P[1] != T[s+1], lub
•
jeśli P[0] != P[1], to przy porównaniach jeśli P[1] == T[s+1], wówczas
po zakończeniu sekwencji porównań okno ze wzorcem naleŜy przesunąć
o dwie pozycje.
Obrazowo działanie drugiej poprawki prezentuje poniŜszy rysunek, na
którym przekreślone zostały porównania niepotrzebne.
Porównaj czasy działania obydwu programów.
Zadanie 47.
Algorytm Rabina-Karpa
Plik:
prog47-rabinkarp.cc
PołoŜenie:
~/aisd/zad47-rabinkarp/
Uruchamianie:
./prog47-rabinkarp <preprocessing|search> <parametry>
Treść:
Algorytm Rabina-Karpa słuŜy wyszukiwaniu wzorca w tekście, ale wyma-
ga przeprowadzenia pewnych obliczeń (ang. preprocessingu), których
celem jest późniejsze przyspieszenie w wyszukiwaniu. Szczegółowy opis
algorytmu znajduje się w [1], str. 934.
Ćwiczenie 14. Algorytmy teorioliczbowe
83
Napisz program, który implementuje algorytm Rabina-Karpa a jego
działanie uzaleŜnione jest od parametrów:
•
<preprocessing>
- przeprowadź preprocessing tekstu zapisanego w
pliku, a
<parametry>
stanowią kolejno:
o
<plik_wejsciowy>
- plik z tekstem, na którym prepro-
cessing zostanie wykonany,
o
<plik_wyjsciowy>
- plik wynikowy preprocessingu,
o
<dlugosc>
- liczba znaków wzorca [1…10], który będzie
wyszukiwany w tekście (na podstawie tej liczby dobierana
jest ilość kolejnych znaków tekstu, z którego wykonywany
jest hash),
•
<search>
- wyszukaj zadany wzorzec w tekście, który jest zapisany w
pliku, a
<parametry>
stanowią kolejno:
o
<plik_wejsciowy>
- plik zawierający przetworzony tekst
(patrz operacja
<preprocessing>
),
o
<wzorzec>
- wyszukiwany ciąg znaków (zaprojektuj algo-
rytm tak, aby zadany
<wzorzec>
mógł być nie krótszy niŜ
długość podana w parametrze
<dlugosc>
wykorzystywa-
nym podczas preprocessingu).
Wyjście programu powinno mieć taką samą postać jak w zadaniach po-
przednich dotyczących wyszukiwaniu wzorca. Wykonaj pomiary porów-
nawcze w stosunku do algorytmów z poprzednich zadań. Zwróć uwagę
na czas wykonywania preprocessingu i czas poszukiwań. W jakich sytu-
acjach algorytm Rabina-Karpa będzie lepszy od algorytmu naiwnego?
Ćwiczenie 15.
Zliczanie i prawdopodobieństwo
Cel ćwiczenia
Celem ćwiczenia jest zapoznanie się z problematyką i zastosowa-
niem implementacji zliczania i prawdopodobieństwa.
Wiadomości wstępne
Przed przystąpieniem do laboratorium naleŜy zapoznać się z na-
stępującymi zagadnieniami teoretycznymi dotyczącymi zliczania i ra-
chunku prawdopodobieństwa:
•
zliczanie: teoria zliczania, reguła sumy, reguła iloczynu, słowo, posło-
wo, permutacja, kombinacja, współczynniki dwumianu, rozwinięcie
dwumianu, funkcja entropii,
•
prawdopodobieństwo: zdarzenie, przestrzeń zdarzeń, zdarzenie ele-
mentarne, rozkład prawdopodobieństwa (dyskretny, jednostajny,
geometryczny, dwumianowy), aksjomaty prawdopodobieństwa, dopeł-
nienie zdarzenia, prawdopodobieństwo warunkowe,
•
dyskretne zmienne losowe: dyskretna zmienna losowa, funkcja gęsto-
ści prawdopodobieństwa, wartość oczekiwana, wariancja, odchylenie
standardowe.
Wskazówka:
Thomas Cormen, „Algorytmy i Struktury Danych”,
Dodatek C, str. 1119 – 1151.
„Algorytmy i Struktury Danych”
86
Zadania do samodzielnego wykonania
Zadanie 48.
Permutacje i kombinacje
Plik:
prog48-permutkombi.cc
PołoŜenie:
~/aisd/zad48-permutkombi/
Uruchamianie:
./prog48-permutkombi <ciag_znakow>
Treść:
Napisz program, który przyjmuje jako parametr jeden ciąg znaków i wy-
pisuje na ekran w linii oddzielonej spacjami wszystkie permutacje i kom-
binacje bez powtórzeń powstałe ze znaków z zadanego ciągu. Przyjmij,
Ŝe zadawany ciąg znaków nie będzie posiadał powtórzeń.
Zadanie 49.
Losowanie liczb z zadanym rozkładem
Plik:
prog49-losowanie.cc
PołoŜenie:
~/aisd/zad49-losowanie/
Uruchamianie:
./prog49-losowanie <rozklad> <ilosc> <a> <b>
Treść:
Napisz program generujący pewną ilość liczb rzeczywistych (dwa miejsca
po przecinku) pseudolosowych z zadanego zakresu z podanym rozkładem
prawdopodobieństwa. Program przyjmuje parametry:
•
<rozklad>
- nazwa rozkładu,
•
<ilosc>
- ilość liczb, którą naleŜy wygenerować,
•
<a>
i
<b>
- zakres liczb, spośród których naleŜy generować.
Zadanie 50.
Grawitacja
Plik:
prog50-grawitacja.cc
PołoŜenie:
~/aisd/zad50-grawitacja/
Uruchamianie:
./prog50-grawitacja <n> <h>
Treść:
Najprostszą metodą doświadczalnego wyznaczenia wartości przyspiesze-
nia ziemskiego g jest wykonać pomiar czasu upadania przedmiotu z za-
danej wysokości. Przy załoŜeniu, Ŝe opory powietrza są pomijalnie małe
wzór na przyspieszenie opisuje:
g = 2*h / t^2
Ćwiczenie 15. Zliczanie i prawdopodobieństwo
87
Gdzie:
1.
h – wysokość z jakiej przedmiot jest upuszczany,
2.
t – czas spadania.
Aby uzyskać jak najdokładniejszy wynik, naleŜy wykonać serię takich
pomiarów i uśrednić wartość. Poprawnie opisane pomiary zawierają takŜe
podane wartości odchylenia standardowego, które określa błąd pomia-
rów.
Napisz program, który dla zadanej liczby pomiarów
<n>
upadku przed-
miotu z wysokości
<h>
wygeneruje taką serię pomiarów (wypisze na
ekran czasy kolejnych upadków przedmiotu), Ŝe:
3.
średnia wartość g będzie ‘w pobliŜu’ wartości rzeczywistej,
4.
odchylenie standardowe oraz wartość błędu będzie jak najbardziej
rzeczywista.
Program powinien ze znanej wartości g i danej wartości h obliczyć poszu-
kiwaną wartość t i tak wykonywać pseudo-pomiary wartości t, aby uzy-
skać jak najbardziej rzeczywiste wyniki. Skorzystaj z umiejętności im-
plementacji generatora liczb pseudolosowych o zadanym rozkładzie
prawdopodobieństwa.
Literatura
[1]
T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, „Wprowadzenie
do algorytmów”, WNT 2004.
[2]
L. Banachowski, K. Diks, W. Rytter, „Algorytmy i struktury danych”,
WNT 2001.
[3]
J. Grębosz, „Symfonia C++”, Oficyna Kallimach 1996.
[4]
N. Wirth, „Algorytmy + Struktury Danych = Programy”, WNT 1980.
[5]
N. Deo, „Teoria Grafów i jej zastosowania w technice i informaty-
ce”, PWN 1980.
[6]
R. Baran, „Magiczne bloczki”, http://www.rafalbaran.net/mb/.
[7]
Słownik pojęć, „Dictionary of Algorithms and Data Structures”,
http://www.nist.gov/dads/.