8508893158

Literatura

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

• A.V.Aho, J.E.Hopcroft, J.D.Ullman, Algorytmy i struktury danych, Helion, 2003

•    N.Wirth, Algorytmy+struktury danych=programy, WNT, 2002

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

•    D.Knuth, Sztuka programowania, WNT, 2002

•    D.Harel, Algorytmika. Rzecz o istocie informatyki, WNT, 1993

Algorytmy i struktury danych II

30 godzin wykładu, 30 godzin ćwiczeń

3

7

egzamin

Informacje ogólne Wymiar zajęć Semestr Punkty ECTS Sposób zaliczenia

Program

•    Metody konstrukcji algorytmów: rekurencja, usuwanie rekurencji ogonowej, zamiana na iterację ze stosem.

•    Metoda 'dziel i zwyciężaj', proste twierdzenie o złożoności metody.

•    Programowanie dynamiczne - mnożenie macierzy, triangulacja wielokąta, problem plecakowy.

•    Metoda zachłanna, kody Huffmana.

•    Wyszukiwanie wyczerpujące: metoda powrotów i sita, budowa drzewa gry, złożoność i stosowalność wyszukiwania wyczerpującego.

•    Technika rozgałęzień i ograniczeń, problem komiwojażera.

•    Reprezentacje grafów, przegląd DFS i BFS, najkrótsze ścieżki, minimalne drzewo rozpinające.

•    Wyszukiwanie wzorca, metoda KMP.

•    Organizacja pamięci zewnętrznej, struktury danych i algorytmy.

•    Algorytmy rozproszone i równoległe, przykłady.

•    Problemy obliczeniowo trudne: NP-zupełność, przykładowe dowody, algorytmy aproksymacyjne. Literatura

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

• A.V.Aho, J.E.Hopcroft, J.D.Ullman, Algorytmy i struktury danych, Helion, 2003

•    N.Wirth, Algorytmy+struktury danych=programy, WNT, 2002

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

•    D.Knuth, Sztuka programowania, WNT, 2002

•    D.Harel, Algorytmika. Rzecz o istocie informatyki, WNT, 1993

Analiza algorytmów I

30 godzin wykładu, 30 godzin ćwiczeń 5-8

5 (informatyka ogólna),

7 (matematyka obliczeniowa) Zaliczenie (informatyka ogólna) Egzamin (matematyka obliczeniowa)

Informacje ogólne Wymiar zajęć Semestr Punkty ECTS

Sposób zaliczenia

Program

•    Równania rekurencyjne dla metody dziel i zwyciężaj, klasyfikacja, rozwiązania.

•    Dolne ograniczenia na złożoność sortowania.

•    Analiza algorytmu quicksort.

•    Metoda turniejowa sortowania.

•    Problem minimalnej liczby porównań w sortowaniu.

•    Znajdowanie k-tego elementu, metoda podziału, mediana median.

•    Wyszukiwanie w tablicy uporządkowanej, analiza metody kwadratowej.