Matematyka dyskretna
dla informatyki analitycznej
semestr letni 2024/25
Instytut Informatyki Analitycznej
Wydział Matematyki i Informatyki
Uniwersytet Jagielloński
Prowadzący
Krystian Gajdzica, Jędrzej Hodor, Piotr Micek
Zajęcia
wykłady w środy 8:30 - 11:00 (sala 0174)
ćwiczenia w czwartki 8:30 - 11:00 (grupa 1, sala 0116)
ćwiczenia w czwartki 8:30 - 11:00 (grupa 2, sala 0119)

wszystkie zajęcia trwają 2h 15min + 15min przerwy
dyżury w środy 12:00 - 14:00

Matematyka dyskretna to dział matematyki zajmujący się strukturami przeliczalnymi, czyli nieciągłymi, czy po prostu dyskretnymi. Obiektem badań są np. liczby całkowite (teoria liczb), zbiory, częściowe porządki, grafy, kombinatoryczne gry. Ważnym tematem jest zliczanie obiektów. Czasami wiązać się to będzie z rozwiązaniem układu równań czy rekurencyjnej zależności. Rozważając grafy będziemy próbować zrozumieć ich strukturę i związki pomiędzy najważniejszymi parametrami. Szczególnie wdzięcznym tematem tu są kolorowania grafów.

Aktualna punktacja
Warunki zaliczenia
W trakcie kursu można zdobyć 100 punktów, przy czym:

Zestawy zadań będą publikowane co siedem dni (z przerwami na święta lub kolokwia). Liczba zestawów będzie równa $Z$, gdzie $Z\in\{11,12\}$. Studenci przy pomocy elektronicznego formularza będą deklarować rozwiązania zadań z bieżącego zestawu. Deklaracja rozwiązania równoważna jest gotowości prezentacji rozwiązania przy tablicy. Prezentacja zadania co do zasady ma być bez pomocy (bez notatek). Oczywiście w sytuacji gdy zadanie jest bardzo rachunkowe będziemy robić wyjątki, jednak student(-ka) ma rozumieć rozwiązanie bez notatek. Za deklarację bez pokrycia będą negatywne konsekwencje: zerowanie punktów za zestaw, ujemne punkty, itp. Za rozwiązanie zadań pojedynczego zestawu będzie można uzyskać co najwyżej $X=\frac{20}{Z}$ punktów. Jeśli zestaw zawiera $N$ zadań, a student zadeklarował $M$ zadań, to student uzyskuje $\min(\frac{M}{0.9\cdot N},1)\cdot X$ punktów za zestaw. Deklaracje będą zbierane jedynie od studentów obecnych na zajęciach. Poza tym obecność nie będzie mieć wpływu na ocenę.

Rozwiązania wyróżnionych (bonusowych) zadań domowych nie będą podlegać systemowi deklaracji i będą mogły być spisywane w grupach co najwyżej dwuosobowych. Dwie osoby mogą być co najwyżej raz razem w grupie; studenci z różnych grup ćwiczeniowych mogą stworzyć grupę. Rozwiązania będą akceptowane jedynie w formacie pdf, który został wygenerowany przez kompilator Latexa. Rozwiązanie pisemne zadania będzie przyjmowane do terminu podanego w zestawie. Rozwiązanie należy wysyłać na adres matematyka.dyskretna.tcs@gmail.com. Wysłanie rozwiązania równoważne jest gotowości prezentacji rozwiązania przy tablicy. Prowadzący mogą też prosić autorów rozwiązania o indywidualne rozmowy weryfikujące poprawność i samodzielność rozwiązania. Punkty za zadania bonusowe liczą się w sumarycznej punktacji jedynie w przypadku studentów, którzy otrzymali w sumie za oba kolokwia i aktywność więcej niż 50 punktów.

Kodeks honorowy: Zabronione jest wyszukiwanie w sieci treści zadania wyróżnionego czy jego rozwiązania oraz konsultowanie rozwiązań poza grupą podpisaną pod rozwiązaniem. Dozwolone jest korzystanie z książek i materiałów z sieci; jeśli student rozwiązał zadanie dzięki znalezieniu go, lub bardzo podobnego, w materiałach to należy podać referencje do tych materiałów. Każda wysłana pisemna praca ma zawierać oświadczenie autorów o zachowaniu powyższych wytycznych. Poza grupami sformowanymi do konkretnych zestawów dyskusje na temat zadań i ich rozwiązań są dozwolone jedynie na forum.tcs oraz poprzez email z prowadzącym zajęcia.

Niech $A$ będzie sumą punktów uzyskanych w semestrze z aktywności, niech $K$ będzie sumą punktów uzyskanych na kolokwiach i niech $B$ będzie sumą punktów uzyskanych za zadania bonusowe. Wtedy liczba punktów uzyskanych za ćwiczenia obliczana jest wzorem:

$\textrm{if $A+K>50$ then}$
$\qquad\textrm{return $A+K+B$}$
$\textrm{if $A+K \leq 50$ then}$
$\qquad\textrm{return $A+K$}$

Oceny z ćwiczeń wystawiane będą względem następujących progów:

Wszyscy studenci, którzy otrzymali zaliczenie z ćwiczeń (tj. ocenę przynajmniej 3,0) przystąpią do egzaminu końcowego w formie ustnej. Jeśli student otrzymał co najmniej 3,0 z ćwiczeń i egzaminu to jego ocena końcowa jest średnią arytmetyczną tych dwóch ocen zaokrągloną do najbliższej oceny w kierunku oceny z egzaminu (zatem jeśli student otrzymał 5,0 z ćwiczeń i 4,5 z egzaminu to otrzymuje ocenę 4,5 z całego kursu). W pozostałych przypadkach student otrzymuje ocenę 2,0 lub NZAL. Jeśli student otrzyma ocenę 2.0 lub NZAL za ćwiczenia to może przystąpić do kolokwium poprawkowego, które zdecyduje o możliwości przystąpienia do egzaminu. Studenci, którzy uzyskali co najmniej 30 punktów w semestrze zdają kolokwium poprawkowe jeśli uzyskają co najmmniej 50% punktów, pozostali studenci zdają kolokwium po uzyskaniu 66% punktów. Osoby uprawnione do przystąpienia do egzaminu które nie zdały (nie przystąpiły) w pierwszym terminie będą mogły podejść do egzaminu w sesji poprawkowej. Osoby, które zdadzą egzamin w drugim terminie otrzymują ocenę końcową 3,0.

Archiwum kolokwiów
Pytania egzaminacyjne
[pdf] (to są pytania z edycji kursu w 2024 r.; nowa lista pytań pojawi się w czerwcu)
Materiały
wykłady zestawy zadań