Matematyka dyskretna
dla informatyki analitycznej
wiosna 2017
Zespół Katedr i Zakładów Informatyki Matematycznej
Wydział Matematyki i Informatyki
Uniwersytet Jagielloński
Wykłady
Piotr Micek, w piatki 11:00 - 13:30 (z 15 min. przerwą) w sali 0174
Ćwiczenia
Tomasz Krawczyk środy 9:30 - 12:00 w sali 0122 aktywność: [www]
Piotr Micek środy 9:30 - 12:00 w sali 0086 aktywność: [pdf] (aktualizacja: 19 czerwca)
Punkty
[pdf] (aktualizacja: 27 czerwca)
Kolokwia
Ćwiczenia
2 marca [pdf] Indukcja i Zasada Szufladkowa zachęcamy do napisania rozwiązań zadań 1 i 5 na ćwiczenia 8 marca; poprawne rozwiązanie obu zadań będzie odnotowane dodatkowym plusem z aktywności
8 marca [pdf] Zliczanie i współczynniki dwumianowe pisemnie na ćwiczenia 15 marca: rozwiązanie zadania 13
15 marca [pdf] Zliczanie, liczby Stirlinga i liczby Catalana
22 marca [pdf] Posety i zbiory
29 marca Dzień Wydziału
5 kwietnia [pdf] Twierdzenia Ramseyowe
12 kwietnia [pdf] Funkcje tworzące I
19 kwietnia [pdf] Funkcje tworzące II
26 kwietnia Kolokwium (od 8:15)
10 maja [pdf] Grafy: drzewa, ścieżki, cykle, stopnie wierzchołków
17 maja [pdf] Grafy: przeplywy i spojnosc
24 maja [pdf] Grafy: kolorowanie
31 maja [pdf] Grafy: kolorowanie 2
7 czerwca [pdf] Grafy: Zadania rozne
Wykłady
3 marca współczynniki dwumianowe, wzór Pascala, dwumian Newtona, tożsamości współczynników dwumianowych, 12 wariantów problemu podziału: n obiektów (rozróżnialne lub nierozróżnialne), k szuflad (rozróżnialne lub nierozróżnialne) i wkładamy obiekty do szuflad (jakkolwiek lub każda szuflada ma co najwyżej 1 obiekt lub każda szuflada ma co najmniej 1 obiekt)
10 marca zasada włączeń i wyłączeń, liczby Stirlinga pierwszego i drugiego rodzaju, liczby Catalana
17 marca posety i krata Boolowska, Twierdzenie Dilwortha i dualne do niego, Lemat Erdősa-Szekeresa, Twierdzenie Spernera, podział kraty Boolowskiej na łańcuchy symetryczne, Twierdzenie Erdősa-Ko-Rado
24 marca Twierdzenie Ramsey'a, ograniczenia górne i dolne na liczby Ramsey'a
31 marca Twierdzenie Schura, Twierdzenie Erdősa-Szekeresa (dwa dowody: jeden wykorzystujący Twierdzenie Ramsey'a i drugi z kubkami i czapeczkami), Twierdzenie Van der Waerdena, Twierdzenie Halesa-Jewetta i jego dowód autorstwa Shellaha (tutaj jest ładna ekspozycja tego dowodu)
7 kwietnia funkcje tworzące, podstawowe operacje i ich interpretacje: dodawanie, mnożenie o stałą, przesunięcie w prawo, przesunięcie w lewo podstawienie x -> cx, podstawienie x -> x^n, różniczkowanie, całkowanie i splot czyli mnożenie tworzących; Uogólnione Twierdzenie Dwumianowe, funkcja tworząca liczb Fibonacciego, rozwiązywanie równań rekurencyjnych
21 kwietnia liczby Catalana i ich interpretacje (przykłady były też na ćwiczeniach i pierwszym kolokwium); zastosowanie funkcji tworzących do przeliczenia prawdopodobieństwa, że losowy spacer zatrzyma się w punkcie docelowym
5 maja podstawowe definicje w teorii grafów, ograniczenie dolne na liczbę nieizomorficznych grafów na n wierzchołkach, algorytm weryfikacji czy zadany ciąg liczb jest ciągiem stopni pewnego grafu
12 maja twierdzenie o 4 kolorach (bez dowodu), proste ograniczenia górne na liczbę chromatyczną (w terminach liczby krawędzi, maksymalnego stopnia), liczba kolorująca grafu i (wielomianowy) algorytm jej obliczania, twierdzenie Brooksa, konstrukcja Mycielskiego, konstrukcja Zykova
19 maja twierdzenie Koniga, twiedzenie Vizinga, shift grafy, double shift grafy, konstrukcja Tutte'a,
26 maja grafy przedziałowe; grafy przecięć obiektów geometrycznych na płaszczyźnie, w szczególności grafy przecięć: kwadratów i prostokątów; ograniczenia górne na liczbę chromatyczną tych grafów w terminach liczby klikowej
2 czerwca konstrukcja Burlinga, reprezentacja grafów Burlinga jako grafów przecięć odcinków na płaszczyźnie, twierdzenie Mantela (czyli pierwszy przypadek twierdzenia Turana), czyli o maksymalnej liczbie krawędzi w grafie na n wierzchołkach bez trójkąta, twierdzenie Turana
Reguły
W trakcie kursu można zdobyć 100 punktów, przy czym: Oceny z ćwiczeń wystawiane będą względem następujących progów: Egzamin odbędzie się w sesji letniej i będzie w formie ustnej. Ocena końcowa będzie wystawiana według następującego wzoru: Studenci, którzy otrzymali ocenę końcową 2,0 mają prawo do zaliczenia kursu w drugim terminie (we wrześniu). Drugi termin "egzaminu" będzie miał formę zbliżoną do kolokwiów przeprowadzonych w trakcie kursu.
Archiwum
Literatura