Category Archives: 2017

Zadanie 4 – Programowanie dynamiczne

Zagadnienia

  • Metodyka programowania dynamicznego
  • Metoda przeglądu wyczerpującego
  • Złożoność obliczeniowa w/w metod
  • Zakres stosowalności programowania dynamicznego
  • Sformułowanie problemu plecakowego oraz metoda jego rozwiązania

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

Continue reading →

Zadanie 3 – Algorytmy grafowe

Zagadnienia

  • 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 projektu: 23.05.2017

Continue reading →

Zadanie 2 – Złożone struktury danych

Zagadnienia

  • 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): 11.04.2017
Termin dostarczenia sprawozdania (mailem pdf): 25.04.2017

Continue reading →

Zadanie 1 – Algorytmy sortowania

Algorytmy sortowania

  • sortowanie przez proste wybieranie (selection sort)
  • sortowanie przez proste wstawianie (insertion sort)
  • sortowanie przez prostą zamianę (bubble sort)
  • sortowanie przez kopcowanie (heapsort)
  • sortowanie przez zliczanie (counting sort)
  • sortowanie przez scalanie (merge sort)
  • sortowanie za pomocą malejących przyrostów (shell sort)
  • sortowanie szybkie (quicksort)

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

Continue reading →

Zadanie wstępne

  1. Napisz funkcję generującą tablicę losowych liczb o zadanej długości. Wypisz na ekran zawartość tablicy od końca.
  2. Wyznacz ile z wylosowanych liczb to liczby pierwsze. Zmierz czas wykonania programu.
  3. Zmierz czasy wykonania fragmentu programu odpowiedzialnego za obliczenia, dla wielu parametrów wejściowych. Skorzystaj z funkcji clock(). Wypisz czasy działania w postaci: 
    długość tablicy;czas działania;ile liczb pierwszych
1;0.001;0
10;0.01;1
600;0.6;31
...
  4. Zaimportuj wynik działania programu do arkusza kalkulacyjnego i narysuj wykres zależności czasu wykonania od długości ciągu.
  5. 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.