Algorytmy i struktury danych

Grzegorz Bancerek
Politechnika Białostocka, II rok, III semestr, informatyka, 2006

EGZAMIN POPRAWKOWY:
sobota 15.09.2007 godz. 9:15, sala 33C
WYNIKI (oceny pozytywne): 65834, 65852, 65880, 68791, 68787, 65898, 65820, 64447, 51629, 57796
EGZAMIN POPRAWKOWY II:
sobota 13.10.2007 godz. 8:00, sala ??

1. 29.09.2006-01.10.2006
   Wykład: Poprawność i złożoność algorytmu, rzędy wielkości funkcji
   Ps: Porównanie trzech metod obliczania potęgi (patrz slady z wykładu 1.1-1.3): Należy dla każdej metody obliczyć ilość wykonanych mnożeń oraz podać czas działania (przykład oblicznia czasu działania: czas.pas). Żeby czas był miarodajny należy obliczenia wykonać odpowiednio dużą ilość razy (np. 30000).
   Ćwiczenia: Porównywanie rzędów wielkośći funkcji (zadania).

   ---

2. 13.10.2006-15.10.2006
   Wykład: Hierarchia wielkości funkcji. Algorytmy obliczania symbolu Newtona - metoda dynamiczna
   Ps: Porównanie metod obliczania symbolu Newtona (patrz slady z wykładu):
   • metody 1,2,3 - slajd 5,
   • metoda 4 - funkcja wywolująca metode 2 lub 3 w zależności jakie jest n,
   • metoda 5 - funkcja rekurencyjna ze slaidu 5.2,
   • metoda 6 - slajd 5.3,
   • metoda 7 - slajd 5.5 z wymianą dwuwymiarowej tablicy P na jednowymiarową.
   Należy dla każdej metody obliczyć ilość wykonanych mnożeń (metody 1-4) lub dodawań (metody 5-7) oraz podać czas działania (przykład oblicznia czasu działania: czas.pas). Żeby czas był miarodajny należy obliczenia wykonać odpowiednio dużą ilość razy (np. 30000).
   Ćwiczenia: Porównywanie rzędów wielkośći funkcji (zadania).

   ---

3. 27.10.2006-29.10.2006
   Wykład: Metody sortowanie rzędu O(n²)
   Ps: Porównanie jednej z metod sortowania (wybieranie, wstawianie, bąbelkowe) z sortowaniem Shella.
   W porównaniu należy sprawdzić czy tablice są posortowane tak samo i podać ilość porównań i przypisań oraz czasy działania. Należy też umieć wyjaśnić działanie algorytmów.
   Ćwiczenia: Obliczanie złożoności sortowania przez wybieranie i wstawianie (zadania).

   ---

4. 17.11.2006-19.11.2006
   Wykład: Listy, kolejki, stosy
   Ps: Implementacja kolejki jako dwóch stosów:
   Stos należy zaimplementować jako listę liniową jednokierunkową a kolejkę jako rekord zawierający dwa stosy: jeden do wkładania elementów a drugi do pobierania. Jesli pobieramy pierwszy element z kolejki a stos do pobierania jest pusty, to wszystkie elementy ze stosu do wkładania są przerzucane na stos do pobierania i wtedy pobieramy element. Podobnie w przypadku operacji POP.

   type
     List = ^Element;
     Element = record
       nbr: real;
       next: List;
     end;
     Stack = List; {Stos}
   
     procedure InitS(var S: Stack); {wpisanie nil do S}
     function EmptyS(S: Stack): boolean;
     function OnTop(S: Stack): real;
     procedure Push(var S: Stos; a: integer);
       { należy utworzyć nowy Element
         new(e)
         i przypisać
         e^.liczba := a
         i potem wstawić Element e na górze stosu (na początku listy)
       }
     procedure PopS(var S: Stack);
   
     procedure Transfer(var Sin, Sout: Stack); {przerzucanie elementów ze stosu Sin do Sout}
   
   type
     Queue = record          {Kolejka}
       stack_in, stack_out: Stack;
     end;
   
     procedure InitQ(var K: Queue);  {oba stosy są inicjalizowane}
     function EmptyQ(K: Queue): boolean;     {czy oba stosy są puste}
     function First(K: Queue): real;
       {podaje liczbę w pierwszym elemencie stack_out przerzucając wcześniej
        elementy ze stack_in jeśli trzeba}
     procedure Inject(var K: Queue; a: real); {robi Push do stack_in}
     procedure PopQ(var K: Queue);
       {usuwa pierwszy element ze stack_out przerzucając wcześniej
        elementy ze stack_in jeśli trzeba}
     
   

   Ćwiczenia: Obliczanie złożoności operacji na listach (zadania).

   ---

5. 01.12.2006-03.12.2006
   Wykład: Strategia programowania ,,dziel i zwyciężaj'', wyszukiwanie elementu w tablicy posortowaje, sortowanie przez scalanie i szybkie.
   Ps: Implementacja sortowania przez scalanie z użyciem kolejek.
   Należy użyć jednostki LISTY (uses LISTY), której interfejs wyglada tak (tego nie należy kopiować do programu)
   
   Program powinien wyglądać tak:

   Program MergeSort;
   
   uses Listy, crt;
   
   procedure Dziel(var K,K1,K2: Kolejka);
   begin
   { Dzieli kolejkę K na dwie części, które zapisuje do K1 i K2}
   end;
   
   procedure Scal(var K1,K2,K: Kolejka);
   begin
   { scala posortowane kolejki K1 i K2 w pustą kolejkę K }
   end;
   
   procedure SortowaniePrzezScalanie(var K: Kolejka);
   var K1,K2: Kolejka;
   begin
     Init(K1);
     Init(K2);
     if K.Count > 1 then
     begin
       Dziel(K,K1,K2);
       SortowaniePrzezScalanie(K1);
       SortowaniePrzezScalanie(K2);
       Scal(K1,K2,K);
     end;
     
   end;
   
   var K: Kolejka;
   
   begin
   { Wczytanie z pliku 'dane.txt' liczb do sortowanie do kolejki K }
     SortowaniePrzezScalanie(K);
   { Wypisanie kolejki K }
   end.
   

   Ćwiczenia: Obliczanie złożoności algorytmów stosujących strategię ,,dziel i zwyciężaj'' (zadania).

   ---

6. 15.12.2006-17.12.2006
   Wykład: Sortowanie przez kopcowanie, połówkowe wstawianie i leksykograficzne (pozycyjne)
   Ps: Implementacja sortowania leksykograficznego przy użyciu kolejek.
   Ćwiczenia: Obliczanie złożoności algorytmów sortowania

   ---

7. 12.01.2007-14.01.2007
   Wykład: Drzewa binarnego wyszukiwania.
   Ps: Implementacja podstawowych operacji na drzewach binarnych.
   Ćwiczenia: Implementacja rekurencyjna i nierekurencyjna funkcji DELETE dla drzewach BST

   ---

8. 26.01.2007-28.01.2007
   Wykład: Drzewa AVL
   Ps: Implementacja podstawowych operacji na drzewach AVL.
   Ćwiczenia: Kolokwium

   ---

• 29.01.2007-11.02.2007: Sesja egzaminacyjna
  Kolokwium poprawkowe z ćwiczeń. Propozycja zadań na kolokwium

  ---

9. 02-04.03.2007
   Wykład: Reprezentacja grafów, przeglądanie grafu
10. 16-18.03.2007
    Wykład: Reprezentacja zbiorów w problemie UNION-FIND
11. 30.03-01.04.2007
    Wykład: Algorytm Kruskala
12. 13-15.04.2007
    Wykład: Algorytm Prima
13. 27-29.04.2007
    Wykład: Programowanie zachłanne
14. 18-20.05.2007
    Wykład: Kolejność mnożenia macierzy
15. 01-03.06.2007
    Wykład: Wyszukiwanie wzorca w tekście
    Algorytm Knutha-Morrisa-Pratta
16. 15-17.06.2007
    Wykład: Omówienie zadań na egzamin

1. Sortowania: zliczanie, wybieranie, wstawianie, bąbelkowe, Shella, scalanie, szybkie (quicksort), kopcowanie
2. Listy (tablicowe i dowiązaniowe), kolejki, stosy
3. grafy, przeszukiwanie grafu
4. zbiory, UNION-FIND
5. algorytmy Prima i Kruskala
6. drzewa BST, operacje wyszukiwania, wstawiania i usuwania
7. drzewa AVL
8. Strategie programowania: dynamiczna, dziel i zwyciężaj, zachłanna, rekurencja a iteracja
9. wyszukiwanie wzorca w tekście, algorytmy: naiwny, KMP, RK, BM