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/.
Wyszukiwarka
Podobne podstrony:
blok 2 skrypt id 90327 Nieznany (2)
blok 3 skrypt id 90351 Nieznany (2)
md skrypt id 290151 Nieznany
Enzymologia Skrypt I id 162159 Nieznany
AiSD wyklad 1 id 53489 Nieznany
blok 8 skrypt id 90430 Nieznany (2)
aisd zestaw 6 id 53504 Nieznany (2)
AiSD Zestaw 8 id 53502 Nieznany (2)
AiSD wyklad 9 id 53492 Nieznany (2)
Ekonomia skrypt id 156120 Nieznany
MANGANOMETRIA skrypt id 278631 Nieznany
Eschatologia skrypt id 163497 Nieznany
mikro II skrypt id 300610 Nieznany
Prawoznawstwo skrypt id 388928 Nieznany
parazyty skrypt id 349280 Nieznany
handel zagraniczny skrypt id 19 Nieznany
ELEKTROFOREZA skrypt id 158052 Nieznany
blok 5 skrypt id 90384 Nieznany (2)
więcej podobnych podstron