Matematyka Dyskretna M

Wykład 01 (02/10/2019), Repetytorium, Lista zadań, Rozwiązania - funkcje całkowitoliczbowe, symbole asymptotyczne, złożoność obliczeniowa algorytmów (znajdowanie maksiumum n liczb, mnożenie macierzy n✕n), zależności rekurencyjne (wieże Hanoi, proste i obszary na płaszczyźnie)
Wykład 02 (09/10/2019), Repetytorium, Lista zadań, Rozwiązania - liczby Fibonacciego, sortowanie przez scalanie, mnożenie liczb n-cyfrowych - algorytm Karacuby, obliczanie NWD, algorytm Euklidesa (rozszerzony)
Wykład 03 (16/10/2019), Repetytorium, Lista zadań, Rozwiązania - liczby pierwsze - rozkład na czynniki pierwsze, nieskończona ilość liczb pierwszych, twierdzenie Czebyszewa i jego dowód, chińskie twierdzenie o resztach, funkcja Eulera
Wykład 04 (23/10/2019), Repetytorium, Lista zadań, Rozwiązania - twierdzenie Eulera, małe twierdzenie Fermata, zasada szufladkowa Dirichleta, zliczanie - wzór dwumianowy Newtona, uogólniony symbol Newtona (dowód rachunkowy, algebraiczny, kombinatoryczny)
Wykład 05 (07/11/2019), Repetytorium, Lista zadań, Rozwiązania - zasada włączania-wyłączania (oraz jej uogólnienie dla n zbiorów), liczba Stirlinga I, II rodzaju, grupy, podgrupy, warstwy, twierdzenie Lagrange'a, twierdzenie Eulera, zliczanie istotnie różnych obiektów, lemat Burnside'a
Wykład 06 (14/11/2019), Repetytorium, Lista zadań, Rozwiązania - równania rekurencyjnie liniowe (równania jednorodne), metoda anihilatorów, operator przesunięcia E, liniowa niezależność ciągów, obliczanie sum, funkcje tworzące
Wykład 07 (21/11/2019), Repetytorium, Lista zadań, Rozwiązania - funkcje tworzące, wykładnicze funkcje tworzące, rozwiązywanie zależności rekurencyjnych, liczby Catalana i ich interpretacja kombinatoryczna
Wykład 08 (28/11/2019), Repetytorium, Lista zadań, Rozwiązania - problem wydawania reszty, podziały liczby; TEORIA GRAFÓW: lemat o uściskach dłoni, "patologie" w grafach, grafy proste, grafy izomorficzne, grafy skierowane (digrafy), grafy puste (bezkrawędziowe), grafy pełne (kliki), dopełnienie grafu prostego, grafy k-regularne, grafy dwudzielne, grafy dwudzielne pełne, grafy spójne i niespójne, podgraf grafu, drogi w grafach - marszruty
Wykład 09 (05/12/2019), Repetytorium, Lista zadań, Rozwiązania - drzewa, równoważne twierdzenia o drzewach (oraz dowód równoważności), las, drzewa spinające, twierdzenie Cayley'a, konstrukcja i odtwarzanie kodu Prüfera, reprezentowanie grafów za pomocą macierzy (macierz sąsiedztwa, macierz incendencji), reprezentacja grafów w pamięci komputera (macierz sąsiedztwa, lista sąsiadów, tablica (lista tablic) sąsiadów), tabela złożoności operacji/kryteriów na grafach, drogi Eulera (problem mostów królewieckich), cykle Eulera, graf eulerowski, graf półeulerowski
Wykład 10 (12/12/2019), Repetytorium, Lista zadań, Rozwiązania - grafy eulerowskie - drogi i cykle Eulera, problem chińskiego listonosza, grafy hamiltonowskie - drogi i cykle Hamiltona, twierdzenie Ore i jego dowód, problem komiwojażera (TSP - travelling salesman problem), przeszukiwanie grafów - w głąb (DFS - Depth First Search) oraz wszerz (BFS - Breadth First Search), problem najkrótszych dróg - algorytm Dijkstry (wraz z jego niezmiennikiem)
Wykład 11 (19/12/2019), Repetytorium, Lista zadań, Rozwiązania - najkrótsze ścieżki w grafach, algorytm Warshalla-Floyda (oraz jego niezmiennik), przechodnie domknięcie grafu skierowanego, znajdowanie przechodniego domknięcia, najkrótsze drzewo spinające (rozpinające) - ogólny schemat i jego dowód, algorytm Kruskala, algorytm Prima-Dijkstry, sieć, przekrój sieci
Wykład 12 (09/01/2020), Repetytorium, Lista zadań, Rozwiązania - sieci, przepływ, pojemność, wzór Kirchoffa, wartość przepływu, przekrój, ścieżka powiększająca przepływ, algorytm Forda-Fulkersona, twierdzenie Forda-Fulkersona, heurystyka Edmondsa-Karpa, Twierdzenie Königa-Egervaryego, tworzenie sieci z grafu
Wykład 13 (16/01/2020), Lista zadań, Rozwiązania - graf planarny, graf płaski, graf homeomorficzny z K5, K3,3, Twierdzenie Kuratowskiego, wzór Eulera, kolorowanie grafów planarnych (wierzchołków lub ścian/map), graf dualny, kolorowanie grafów, liczba chromatyczna, algorytm sekwencyjny
Wykład 14 (23/01/2020), Lista zadań - redukcje wielomianowe, skojarzenia w grafach, twierdzenie Halla, kolorowanie krawędzi, indeks chromatyczny, twierdzenie Vizinga, twierdzenie Königa