Category Archives: AiSD

Zadanie 3 – Algorytmy grafowe

Definicja grafu skierowanego i nieskierowanego
Reprezentacje grafu, ich złożoność pamięciowa i złożoność pozyskiwania informacji o grafie z poszczególnych struktur danych
Algorytmy przeszukiwania grafu “w głąb” (Depth First Search = DFS) oraz “wszerz” (Breadth First Search = BFS)
Algorytm znajdowania cyklu Eulera w grafie, warunki istnienia cyklu Eulera w grafie skierowanym i nieskierowanym, złożoność obliczeniowa procedury poszukiwania cyklu Eulera
Metoda poszukiwania minimalnego drzewa rozpinającego w grafie oraz jej złożoność obliczeniowa
Algorytm sortowania topologicznego

Termin oddawania programów i wyników eksperymentów (+ wykresy): 17.5.2016
Termin dostarczenia sprawozdania (mailem pdf): 24.5.2016

Struktura listy jedno- i dwukierunkowej
Struktura drzewa poszukiwań binarnych (Binary Search Tree – BST)
Tworzenie i usuwanie w/w struktur
Wyszukiwanie elementu na liście/ w drzewie
Usuwanie pojedynczych elementów listy/ drzewa
Przeglądanie drzewa w porządku wzdłużnym (preorder), poprzecznym (inorder) i wstecznym (postorder)
Definicja drzewa wyważonego i dokładnie wyważonego

Termin oddawania programów i wyników eksperymentów (+ wykresy): 19.04.2016
Termin dostarczenia sprawozdania (mailem pdf): 26.04.2016

Termin oddawania programów i wyników eksperymentów (+ wykresy): 22.03.2016
Termin dostarczenia sprawozdania (mailem pdf): 05.04.2016

Napisz program generujący tablicę losowych liczb o zadanej długości. Wypisz na ekran zawartość tablicy od końca.
Napisz funkcję liczącą wartość średniej liczb w tablicy. Zmierz czas wykonania programu.
Zmierz czasy wykonania fragmentu programu odpowiedzialnego za obliczenia, dla wielu parametrów wejściowych. Skorzystaj z funkcji clock(). Wypisz czasy działania w postaći:
```
długość;czas działania
1;0.001
10;0.01
600;0.6
...
```
Zaimportuj wynik działania programu do arkusza kalkulacyjnego i narysuj wykres zależności czasu wykonania od długości ciągu.
Zmodyfikuj program tak, aby obliczenia wykonane zostały zadaną liczbę razy, odrzuć wyniki skrajne (min i max), wypisz średni czas działania dla danej długości ciągu.

Termin oddawania programów i wyników eksperymentów (+ wykresy): 09.06.2015
Termin dostarczenia sprawozdania (mailem pdf): 16.06.2015

Definicja grafu skierowanego i nieskierowanego
Reprezentacje grafu, ich złożoność pamięciowa i złożoność pozyskiwania informacji o grafie z poszczególnych struktur danych
Algorytmy przeszukiwania grafu “w głąb” (Depth First Search = DFS) oraz “wszerz” (Breadth First Search = BFS)
Algorytm znajdowania cyklu Eulera w grafie, warunki istnienia cyklu Eulera w grafie skierowanym i nieskierowanym, złożoność obliczeniowa procedury poszukiwania cyklu Eulera
Metoda poszukiwania minimalnego drzewa rozpinającego w grafie oraz jej złożoność obliczeniowa
Algorytm sortowania topologicznego

Termin oddawania programów i wyników eksperymentów (+ wykresy): 05.05.2015
Termin dostarczenia sprawozdania (mailem pdf): 12.05.2015