Adam Gregosiewicz
Adam Gregosiewicz

Matematyka dyskretna | I1S | semestr zimowy 2025/2026

Aktualności

27.01.2026 — Rozwiązania zadań i wyniki kolokwium

Poniżej znajdą Państwo rozwiązania zadań z drugiego kolokwium. Wyniki wraz z propozycją ocen postaram się wysłać w środę.

19.01.2026 — Zwolnienia z egzaminu

Postanowiłem ostatecznie, że zwolnienia z egzaminu będą przysługiwały osobom, które uzyskają z zaliczenia ćwiczeń ocenę 4.0 lub wyższą.

19.01.2026 — Harmonogram sesji

  • 2.02.2025 – egzamin, godz. 18.00, sale E201 i E301.
  • 2.02.2025 – pierwsza poprawa ćwiczeń (grupy 1.1 i 1.4), godz. 16.15, sala E201.
  • 5.02.2025 – druga poprawa ćwiczeń (grupy 1.1 i 1.4), godz. 12.00, sala E201.
  • 9.02.2025 – pierwsza poprawa egzaminu, godz. 16.00, sale E201 i E401.
  • 12.02.2025 – druga poprawa egzaminu, godz. 10.15, sale E301 i E401.

Przypominam, że aby podejść do pierwszego terminu egzaminu (2.02) trzeba uzyskać zaliczenie ćwiczeń w pierwszym terminie. Uzyskanie zaliczenia ćwiczeń w terminie poprawkowym (pierwszym lub drugim) uprawnia do podejścia do obu egzaminów poprawkowych.

13.01.2026 — Termin drugiego kolokwium

Drugie kolokwium dla grup 1.1 i 1.4 odbędzie się 26 stycznia o godz. 18.00 w sali E201.

15.12.2025 — Wstępny harmonogram sesji

Oto wstępny harmonogram sesji. Dokładne godziny i sale będą uzupełnione.

  • 2.02.2025 – egzamin,
  • 2.02.2025 – pierwsza poprawa ćwiczeń (grupy 1.1 i 1.4),
  • 5.02.2025 – druga poprawa ćwiczeń (grupy 1.1 i 1.4),
  • 9.02.2025 – pierwsza poprawa egzaminu,
  • 12.02.2025 – druga poprawa egzaminu.

5.12.2025 — Termin pierwszego kolokwium

Kolokwium dla grup 1.1 i 1.4 odbędzie się 15 grudnia o godz. 18.00 w sali E201.

Kolokwia i egzaminy

Wykład

  • Piątek, 12.15–14.00, sala E201.

Prowadzący

Wykład

Adam Gregosiewicz

Ćwiczenia

  • Adam Gregosiewicz (gr. 1.1, 1.4)
  • Artur Kukuryka (gr. 1.5, 1.6)
  • Ernest Nieznaj (gr. 1.2, 1.3)

Zasady zaliczenia i egzaminu

Wykład

  • Osoby, które uzyskają pozytywną ocenę z ćwiczeń przystępują do egzaminu pisemnego (nie można podejść do egzaminu bez zaliczonych ćwiczeń).
  • Uzyskanie oceny 5.0 z ćwiczeń zwalnia z egzaminu.

Ćwiczenia

  • W trakcie semestru odbędą się dwa kolokwia. Za każde z nich można zdobyć maksymalnie 40 punktów.
  • Za aktywność na zajęciach można uzyskać dodatkowo do 20 punktów.
  • Zdobycie łącznie minimum 50 punktów gwarantuje pozytywną ocenę z ćwiczeń.

Konsultacje

Adam Gregosiewicz

  • Środa, 10.15–11.00, Pentagon, pok. 3 (PE 3).
  • Czwartek, 14.15-15.00, Pentagon, pok. 3 (PE 3).

Terminy konsultacji pozostałych prowadzących można znaleźć tutaj.

Materiały

Skrypt

Równolegle z prowadzonym wykładem będę starał się na bieżąco publikować skrypt, w którym znajdą się wszystkie omawiane zagadnienia. Aktualną wersję skryptu zawsze można znaleźć tutaj:

Jest to wersja bardzo wstępna, zawierająca na pewno jakieś usterki. Mam nadzieję, że tych merytorycznych niedociągnieć jest możliwie mało. Bardzo zachęcam do czytania skryptu na bieżąco. Jeśli ktoś znajdzie jakiś błąd, to bardzo proszę o informację przez e-mail (a.gregosiewicz@pollub.pl). Za każdy znaleziony błąd będę przyznawał dodatkowe punkty, które wpłyną pozytywnie na ocenę końcową z przedmiotu.

Na końcu każdego rozdziału znajduje się zestaw zadań. Podzielony jest on zwykle na cztery częśći: A, B, C i D. Zadania z części A powinny być zrobione samodzielnie przed odpowiednimi ćwiczeniami. Jeżeli mamy z tymi zadaniami problem, musimy wrócić do notatek z wykładu. Podczas zajęć skupimy się na zadaniach z części B, które trudnością odpowiadają zadaniom z kolokwium. Część C zawiera zadania trochę trudniejsze, ale niekoniecznie bardzo trudne, które wymagają głębszego zastanowienia. W szczególności za rozwiązanie tych zadań można uzyskać więcej punktów za aktywność na ćwiczeniach. W częśći D znajdują się zadania algorytmiczne, polegające na napisaniu programu, który realizuje określone zadanie.

Książki

  1. E. Lehman, T. Leighton, A. Meyer, Mathematics for Computer Science, Samurai Media Limited, 2017.
  2. H. Lewis, R. Zax, Essential Discrete Mathematics for Computer Science, Princeton University Press, 2019.
  3. K. Ross, C. Wright, Discrete Mathematics, Prentice Hall, 1999.

Pozycja [1] jest oficjalnie udostępniania przez autorów w wersji elektronicznej. Niżej można też znaleźć linki do kursu prowadzonego przez jednego z autorów oraz nagrania wykładów.

Pozycje [2] i [3] mają polskie tłumaczenia, odpowiednio:

  • Matematyka dyskretna. Niezbędnik dla informatyków, Wydawnictwo Naukowe PWN, 2021.
  • Matematyka dyskretna, Wydawnictwo Naukowe PWN, 2012.

Obie są dostępne w Bibliotece PL.

Strony internetowe

Zdecydowanie polecam korzystać z materiałów dostępnych na stronie wazniak.mimuw.edu.pl. W szczególności interesujące dla nas są kursy:

  1. Logika i teroria mnogości.
  2. Matematyka dyskretna 1.
  3. Matematyka dyskretna 2. Notatki są trochę bardziej zaawansowane, ale na pewno mogą się przydać.
  4. MIT 6.042J Mathematics for Computer Science. Kurs prowadzony przez T. Leightona i M. van Dijka w oparciu o książkę [1]. Bardzo polecam.

Kursy wideo

  1. MIT 6.042J Mathematics for Computer Science. Nagrania wykładów z kursu T. Leightona i M. van Dijka.

Wykłady

Tydzień 1 — 3.10.2025

Informacje organizacyjne. Wprowadzenie do teorii mnogości. Zbiory liczbowe. Konstruktor zbioru. Działania na zbiorach. Prawa rachunku zbiorów. Zbiór potęgowy.

Materiały:

Tydzień 2 — 10.10.2025

Dowodzenie praw rachunku zbiorów. Para uporządkowana i iloczyn kartezjański. Antynomia Russella. Zasada indukcji matematycznej.

Materiały:

Tydzień 3 — 17.10.2025

Zasada indukcji zupełnej. Przykłady: ciągi zadane rekurencyjnie, teoria grafów, reprezentacja binarna, algorytm szybkiego potęgowania. Twierdzenie o niezmiennikach pętli.

Materiały:

Tydzień 4 — 24.10.2025

Dowód poprawności i badanie złożoności czasowej algorytmu szybkiego potęgowania. Wstęp do logiki matematycznej. Podstawowe funktory logiczne.

Materiały:

Tydzień 5 — 7.11.2025

Formuły logiczne. Tautologie. Podstawowe prawa rachunku zdań. Postacie normalne. Zupełność zbioru formuł. Problem SAT i P=NP.

Materiały:

Tydzień 6 — 14.11.2025

Funkcje zdaniowe. Wykres funkcji zdaniowej. Kwantyfikatory. Bramki logiczne. Budowa sumatorów.

Materiały:

Tydzień 7 — 21.11.2025

Problem stopu. Wprowadzenie do relacji. Podstawowe własności relacji. Relacje porządku. Diagram relacji. Elementy wyróżnione.

Materiały:

Tydzień 8 — 28.11.2025

Kresy zbiorów. Relacje równoważności. Klasy abstrakcji i zasada abstrakcji. Relacja przystawania (kongruencji). Wstęp do teorii liczb. Twierdzenie o dzieleniu z resztą.

Materiały:

Tydzień 9 — 5.12.2025

Dowód twierdzenia o dzieleniu z resztą. Największy wspólny dzielnik. Twierdzenie i algorytm Euklidesa.

Materiały:

Tydzień 10 — 12.12.2025

Złożoność algorytmu Euklidesa. Rozszerzony algorytm Euklidesa. Wstęp do kongruencji.

Materiały:

Tydzień 11 — 19.12.2025

Małe twierdzenie Fermata. Funkcja Eulera i twierdzenie Eulera. Kongruencje liniowe. Element odwrotny.

Materiały:

Tydzień 12 — 9.01.2026

Rozwiązywanie kongruencji liniowych. Układy kongruencji liniowych. Chińskie twierdzenie o resztach. Systemy resztowe (residue number system). Wprowadzenie do kryptografii klucza publicznego.

Materiały:

Tydzień 13 — 16.01.2026

Protokół Diffiego–Hellmana i kryptosystem RSA. Wprowadzenie do teorii grafów. Podstawowe definicje i klasy grafów.

Materiały:

Tydzień 14 — 23.01.2026

Problem mostów królewieckich. Grafy eulerowskie. Algorytm Fleury’ego. Grafy hamiltonowskie. Twierdzenie Orego. Algorytm Dijkstry.

Materiały:

Tydzień 15 — 30.01.2026

Dowód poprawności algorytmu Dijkstry. Podstawy kolorowania grafów.

Materiały:

Zestawy zadań