Wykładowca: Krzysztof Loryś
|
|
|
Spis treści wykładu
·
Wykład
1: Przypomnienie podstawowych pojęć. Notacja
asymptotyczna. ·
Wykład 2: Podzielność liczb; największy
wspólny dzielnik; algorytm Euklidesa; najmniejsza wspólna wielokrotność;
liczba podzielników; Liczby pierwsze; Twierdzenie Czebyszewa o gęstości liczb
pierwszych; twierdzenie o jednoznaczności rozkładu; sito Eratostenesa;
algorytmy sprawdzania pierwszości liczb. · Wykład 3: Arytmetyka modularna. ciała Zp; grupy Z*p; cykliczność Z*p; rząd elementu; generatory; obliczanie elementu odwrotnego; uogólniony Algorytm Euklidesa; rozwiązywanie prostych kongruencji; Chińskie Twierdzenie o Resztach. ·
Wykład 4: Zależności rekurencyjne. Przykłady z
analizy algorytmów (równanie opisujące koszt algorytmów opartych na metodzie
dziel i zwyciężaj). Rozwiązywanie zależności rekurencyjnych. ·
Wykład 5: Funkcje
tworzące (zastosowanie do rozwiązywania zależności rekurencyjnych). Permutacje. Wariacje. Wariacje z
powtórzeniami. Kombinacje. Kombinacje z powtórzeniami. ·
Wykład 6: Kombinacje
z powtórzeniami (cd). Podziały zbiorów. Zasada Włączania i wyłączania. ·
Wykład 7: Zasada
szufladkowa Dirichleta. Podstawowe pojęcia teorii grafów ( grafy skierowane i
nieskierowane, stopnie wierzchołków, ścieżki i cykle w grafie, grafy spójne,
składowe spójności). Problem cyklu Eulera, problem cyklu Hamiltona. ·
Wykład 8: Sposoby
pamiętania grafów w pamięci komputera. Przechodzenie grafów. Drzewa. Szukanie
minimalnego drzewa rozpinającego (algorytm Kruskala). Znajdowanie
najkrótszych dróg od zadanego wierzchołka (algorytm Dijkstry). Związek
problemu szukania najkrótszych dróg z mnożeniem macierzy. Kolorowanie grafów. |
Listy
zadań
·
Lista nr
1
·
Lista nr
2
·
Lista nr
3
·
Lista nr
4
·
Lista nr
5
·
Lista nr
6
Notatki
·
Notatka
nr 1
·
Notatka
nr 2 (w trakcie konstrukcji)
|