8508893160

•    Złożoność wyszukiwania w drzewach BST i AVL.

•    Konstrukcja optymalnych drzew BST.

•    Złożoność haszowania.

•    Problem sumowania zbiorów rozłącznych, zastosowania.

•    Złożoność amortyzowana.

•    Drzewa rozchylane, analiza.

•    Probabilistyczne struktury danych: drzewa-kopce, listy z przeskokiem.

Literatura

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

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

•    R. Sedgewick, Algorytmy w C++, Wydawnictwo RM, Warszawa 1999

Analiza algorytmów II

30 godzin wykładu, 30 godzin ćwiczeń

5-8

7

egzamin

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

Program

•    Kopce dwumienne i Fibonacciego, zastosowania w algorytmach grafowych.

•    Algorytmy znajdowania skojarzeń i przepływów w grafach.

•    Dopasowywanie wzorca: algorytm Boyera-Moore'a, Karpa-Rabina, automat Aho-Corasica, wzorce 2-wymiarowe.

•    Wyszukiwanie w plikach tekstowych: drzewa trie i patricia, drzewa sufiksowe, grafy DAWG, algorytmy konstrukcji.

•    Geometria obliczeniowa: techniki, struktury danych, problem wypukłej powłoki, lokalizacja punktu, przecięcia figur.

•    Algorytmy algebraiczne i teorioliczbowe: FFT, szybkie mnożenie liczb i wielomianów.

•    Modele obliczeń równoległych: PRAM, tablica procesorów, hiperkostka. Algorytmy równoległe.

•    Wstęp do teorii złożoności: klasy złożoności i ich inkluzje, problemy zupełne

Literatura

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

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

• A.V.Aho, J.E.Hopcroft, J.D.Ullman, projektowanie i analiza algorytmów, Helion, 2003.

Analiza matematyczna I

Informacje ogólne Wymiar zajęć Semestr Punkty ECTS Sposób zaliczenia 30 godzin wykładu, 30 godzin ćwiczeń 2 5

zaliczenie

Program

•    Przestrzenie metryczne. Metryka Hausdorffa. Przestrzenie topologiczne. Zwartość. Spójność. Zupełność.

•    Przestrzenie Banacha. Przestrzenie Hilberta.

•    Ciągi w przestrzeniach metrycznych i unormowanych.

•    Zwartość zbiorów. Twierdzenie Cantora o zupełności. Zwartość a ciągowa zwartość.

•    Granice i ciągłość funkcji. Definicje Cauchy’ego i Heinego. Jednostajna ciągłość funkcji. Granice jednostronne, granice niewłaściwe. Twierdzenia typu Darboux.

•    Twierdzenia Weierstrassa.

•    Szeregi liczbowe i wektorowe. Kryterium zbieżności.

•    Różniczka i jej własności. Różniczka złożenia.

20