Stefan Sokołowski

MATEMATYKA DYSKRETNA

Slajdy do wykładu

W poniższej tabelce kliknięcie

na ,,przegląd'' daje dostęp do wersji drukowanej slajdów do wykładu (lepsze do szybkiego przeglądania);
na ,,slajdy'' wyświetla wykład ze wszystkimi nakładkami, tak jak jest prowadzony w sali wykładowej.

Slajdy są tylko pomocą do wykładu i nie wystarczą do opanowania materiału przez osoby nieobecne na wykładzie. Na ćwiczeniach obowiązuje założenie, że student był na wykładzie (i uważał), a następnie co najmniej przejrzał slajdy w domu.
Jeśli to nie wystarcza do zrozumienia tematu, to należy mi to jak najszybciej zgłosić.

Bardzo proszę o zgłaszanie mi również

błędów w slajdach;
błędów w tym, co powiedziałem na wykładzie;
pomysłów, jak można było coś wyjaśnić prościej.

Za każdą dobrze wcelowaną krytykę przewidziane są punkty podwyższające stopień na zaliczenie.

Wykłady już przeprowadzone:

Reguły gry i zaliczania.

przegląd
slajdy

Indukcja matematyczna:
Podstawowa reguła indukcji.
Błędne użycie indukcji.
Indukcja a programowanie

przegląd
slajdy

Indukcja matematyczna:
Indukcja zupełna.
Rekurencje.

przegląd
slajdy

Rekurencje liniowe:
-- jednorodne,
-- niejednorodne.

przegląd
slajdy

Podzielność:
-- iloraz całkowity i reszta,
-- największy wspólny dzielnik i algorytm Euklidesa,
-- liczby względnie pierwsze,
-- równania diofantyczne,
-- liczby pierwsze,
-- tw. o jednoznaczności rozkładu na liczby pierwsze.

przegląd
slajdy

Podzielność, c.d:
-- polityczne konsekwencje zaokrągleń,
-- nwd i nww,
-- kongruencje,
-- liniowe równania ,,modulo''.

przegląd
slajdy

Powtórka z relacji:
-- graf i wykres,
-- równoważność i jej klasy abstrakcji,
-- zbiór ilorazowy,
-- liniowe równania ,,modulo''.
Obliczenia i równania ,,modulo''.
Chińskie twierdzenie o resztach.

przegląd
slajdy

Arytmetyka komputerowa to arytmetyka ,,modulo''
-- kiedy komputerowe obliczenia na Z dają błędne wyniki,
-- zastosowanie chińskiego twierdzenia o resztach.
Funkcja φ Eulera.
Szyfrowanie asymetryczne RSA

przegląd
slajdy

Kombinatoryka
-- permutacje, wariacje, kombinacje,
-- symbole Newtona i trójkąt Pascala,
-- zasada szufladkowa,
-- ile jest ciągów i zbiorów spełniających pewne warunki

przegląd
slajdy

Teoria grafów
-- wierzchołki, krawędzie, itp.,
-- drogi w grafie,
-- grafy eulerowskie,
-- grafy ważone,
-- algorytm Dijkstry,
-- reprezentacje grafu

przegląd
slajdy

Wykład najbliższy:

Teoria grafów, c.d.
-- kod Prüfera,
-- drzewo spinające,
-- problem trwałych małżeństw,
-- grafy hamiltonowskie,
-- kolorowanie krawędzi,
-- grafy skierowane,
-- sortowanie topologiczne

przegląd
slajdy

Zadania z ćwiczeń

Uwaga:

Poniższe zadania częściowo rozwiązujemy wspólnie na zajęciach. Te, które pozostaną nierozwiązane, Państwo są zobowiazani rozwiązać samodzielnie w domu. Gdyby były z tym jakieś trudności, to koniecznie należy zgłosić je na początku następnych zajęć.

Przy niektórych zadaniach jest adnotacja, że ich rozwiązania można mi przysyłać dla zdobycia punktów do zaliczenia.

Czasem na początku laboratoriów będą mieć miejsce niezapowiedziane krótkie sprawdziany wiedzy i umiejętności, oraz znajomości wykładów. Stanowią one najłatwiejszą formę zaliczenia — rozbójnik na koniec semestru jest trudniejszy. Proszę więc przygotowywać się na bieżąco, nie spóźniać się na zajęcia i być aktywnym.