Matematyka Dyskretna

 

Wykładowca:               Krzysztof Loryś

 

 

 Komunikaty:

·     Są już dostępne wyniki kartkówek.

 

 

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)