Topic outline

  • Topic 1

    Zasady zaliczania przedmiotu. 

    Zasady dobrego programowania. Wprowadzenie do struktur danych. Złożoność obliczeniowa. Złożoność pamięciowa. Notacje asymptotyczne Θ, O i  Ω. Przykłady.

    • Topic 2

       

      Tempo wzrostu różnych funkcji. Znaczenie pewnych zapisów. Podstawy rekurencji. Rozwiązywanie równań rekurecyjnych z pomocą twierdzenia o rekurencji uniwersalnej lub drzew rekursji.

      • Topic 3

        Rozwiązywanie  równań T(n) = 2T(n/2) + nlgn i T(n) = 2(n-1) +1 za pomocą zliczania wartości węzłow w drzewach rekursji. Pseudokod: zalety i podstawowe instrukcje  Podział tablic. Tablice nieuporządkowane: definicja, wyszukiwanie elementu. Analiza algorytmów pod względem zlożoności obliczeniowej.  Tablice uporządkowane o znanych wymiarach: definicje, wyszukiwanie binarne.

        • Topic 4

          Sortowanie tablic. Podział metod sortowania. Proste metody: wstawianie, wybór, zamiana. Zaawansowana metoda wstawiania ShellSort (samodzielnie na podstawie podręcznika i załączonych notatek)

        • Topic 7

          Spr. nr 1