ALGORYTMY I STRUKTURY DANYCH
( 2 semestr SPPI )

ZADANIA LABORATORYJNE:

   

Laboratorium 1  

Operacje na wielomianach

Zakładając że wielomian W(x) jest reprezentowany w pamięci jako LISTA rekordów (współczynnik + potęga) napisać program wykonujący operacje:

1. różniczkowanie wielomianów

2. sumowanie wielomianów

3. mnożenie wielomianów

> Uwaga: implementacja ATD Lista musi być wyraźnie oddzielona (np. – chociaż niekoniecznie - w oddzielnym pliku nagłówkowym) od reszty programu, który powinien korzystać z operacji na liście (INSERT, FIRST, ...).

> To samo dotyczyć będzie innych ATD występujących w następnych zadaniach.

 

Laboratorium 2  

Algorytm Huffmana

Kompresja pliku algorytmem Huffmana (por. wykład). Sugerowany sposób realizacji:

1. Zaimplementować drzewo binarne (wybrać w jaki sposób - lista, tablica...? ) wraz z operacjami na nim.

2. Otworzyć plik, sporządzić dla niego tablicę częstości występowania znaków, utworzyć drzewo zgodnie z alg. Huffmana. 

3. Zapisać zakodowany plik na dysku, potem program powinien go odtworzyć...

 

Kompresja na serio... (filesize: 64KB. włączyć dźwięk). 

 

Laboratorium 3  

Leksykograficzne drzewo poszukiwań.

Zbadać wielkość indeksu dla różnych plików - program powinien podać wielkość pliku (w KB - powinno być ponad ~50KB - raczej większy tekst), ilość słów, ilość węzłów w drzewie poszukiwań.

>>> Program powinien, po podaniu z klawiatury słowa, stwierdzić na podstawie indeksu czy słowo występuje w pliku. Opcjonalnie może także podawać pozycję słowa w pliku (jak to efektywnie zaimplementować?)...  

 

Laboratorium 4  

Wyszukiwanie wzorca w tekście

Zaimplementować algorytmy: Naiwny i Knutha-Morrisa-Pratta. Wyszukiwanie w pliku tekstowym. Porównać ich złożoność (w tym celu zaproponować miarę złożoności: czas wykonania? ilość operacji zliczana w trakcie działania alg.? 3. inna?...).

 

Laboratorium 5 :  

Grafy:
Na podstawie poznanych algorytmów grafowych zaproponować i zaimplementować algorytm wyszukujący cykle w grafie nieskierowanym. Przeprowadzić analizę złożoności algorytmu (pisemnie acz zwięźle - max 1 kartka A-4). Program powinien pozwolić na zdefiniowanie grafu (np. przez podanie macierzy incydencji), a jako wyjście podać listę (listy) wierzchołków tworzących cykl (cykle). Uwaga: złożoność rzędu n! (n jest ilością krawędzi) uznajemy za niedopuszczalną (zbyt dużą). n^n także... :) 

 

Laboratorium 6  

Życie...

Symulacja "Gry w życie" na nieograniczonej (nie w sensie obsługi nieogr. liczby komórek ale braku ograniczeń na rozwój populacji w przestrzeni) płaszczyźnie dwuwymiarowej. Zaproponować efektywny (czas dostepu!) sposób pamiętania zbioru żywych komórek w odpowiedniej strukturze danych (drzewo binarne? AVL? tablica haszująca? inne...? Przyjmujemy, ze lista/tablica jest, wobec ilości komórek, nie do przyjęcia. Program powinien działać SZYBKO:). Implementacja struktury danych powinna być oddzielona od reszty programu. Wizualizacja: dowolna (i konieczna).

Zasady:

Gra w Życie jest symulacją odbywającą się na prostokątnej pokratkowanej planszy. Każda kratka jest pusta lub zawiera komórkę, która reprezentuje żywego osobnika. Populacja żywych osobników zmienia się z pokolenia na pokolenie wg. następujących reguł:
1. jeśli żywy osobnik ma co najwyżej jednego żywego sąsiada, to umiera z samotności.
2. jeśli żywy osobnik posiada co najmniej czterech żywych sąsiadów, to umiera z przeludnienia.
3. jeśli żywy osobnik posiada co najmniej dwóch i co najwyżej trzech żywych sąsiadów, to przeżywa.
4. w pustej kratce rodzi się życie (mniejsza o to JAK ;) , jeśli sąsiaduje ona z dokładnie 3 kratkami zawierającymi żywe osobniki.
Sąsiadami kratki jest 8 kratek przyległych.

 


Wyliczenie OGÓLNYCH I NAJWAŻNIEJSZYCH zagadnień. 

1. Złożoność. Miara O(n) i jej własności. Szacowanie O(n).
2. Struktury danych i operacje na nich. Lista. Stos. Kolejka. Drzewo. Porządki przeglądania drzewa. Zbiory. Kolejki z priorytetami. Kopiec, sortowanie kopcowe. Słownik. Algorytm Huffmana.
3. Kodowanie mieszające otwarte i zamknięte. Binarne drzewa poszukiwań. AVL-drzewa. 2-3 drzewa. Leksykograficzne drzewa poszukiwań.
4. Grafy. Przeglądanie grafów. Najkrótsza droga w grafie. Algorytm Dijkstry.
5. Sortowanie: bąbelkowe, przez wstawianie, szybkie. Złozoność alg. sortowania opartych na porównywaniu elementów. Sortowanie przez zliczanie, pozycyjne, kubełkowe.
6. Alg. tekstowe: naiwny, Robina-Karpa, Knutha-Morrisa-Pratta, Boyera-Moore'a
7. Programowanie dynamiczne. Mnozenie ciągu macierzy. Algorytmy zachłanne.
8. Algorytmy geometryczne. klasyczne zagadnienia: wzajemne położenie punktów, przecinanie sie odcinków, problem przynależności pkt do obszaru.
9. Złożoność. Klasy złożoności P i NP. Problemy NP-zupełne.
10. Algorytmy aproksymacyjne. Ograniczenie wzgledne. Alg. aproks. dla pokrycia wierzchołkowego grafu i problemu komiwojażera z/bez nierówn. trójkata.

ZAKOŃCZENIE KURSU:
Wykład: kolokwium zaliczeniowe w formie pisemnej – na ostatnim wykładzie.
Laboratorium: ocena jest wypadkową ocen cząstkowych za zadania realizowane na zajęciach (kryteria oceny: 1.przygotowanie merytoryczne, 2. w przypadku programu - poprawność działania,  3. terminowe oddanie zadania)

LITERATURA: 

Cormen T. Leiserson C. Rivest R. Wprowadzenie do algorytmów, WNT 2000.

Papadimitriou C. Złożoność obliczeniowa WNT 2002.

Knuth D. Sztuka Programowania, tom I, II, III. WNT 2002.

Balińska K., Projektowanie algorytmów i struktur danych, Wyd. Politechniki Poznańskiej 2001.

Banachowski L., Diks K., Rytter W., Algorytmy i struktury danych, WNT 2001.  

Wirth N., Algorytmy + struktury danych = programy, WNT 1989.