Adam Gregosiewicz
Adam Gregosiewicz

Matematyka dyskretna | I1S | semestr zimowy 2024/2025

Aktualności

26.01.2025 — Drugie zadanie dodatkowe

Oto drugie zadanie do zaprogramowania dla chętnych.

Treść zadania: Reprezentacja Lucasa.

Za poprawne rozwiązania można ponownie otrzymać maksymalnie 15 pkt. Tym razem sama implementacja nie jest jednak bardzo trudna (chociaż dobry pomysł i tak trzeba mieć), więc trochę inaczej wygląda rozkład punktów. Poprawne odpowiedzi warte są 7 pkt., a pozostałe 8 pkt. można zdobyć za opis rozwiązania, który zapewne będzie dłuższy i bardziej matematyczny. Pewnie trzeba tam uzasadnić jakąś przydatną własność ciągu Lucasa.

Reguły są takie same, jak w zadaniu pierwszym. Rozwiązania (kod źródłowy programu, rozwiązania dla powyższych danych i ewentualnie wyjaśnienie w osobnym pliku) należy wysłać na mój adres e-mail (tytuł: „Zadanie dodatkowe 2”) do północy 2 lutego 2024 (oczywiście punkty zostaną uwzględnione przy ocenie z ćwiczeń i ewentualnego zwolnienia z egzaminu). Prosiłbym o stosowanie jednego ze „standardowych” języków, powiedzmy C/C++/C#/Python/Java/JavaScript/Rust.

Zadanie można rozwiązywać samodzielnie lub w parach (w tej sytuacji proszę w mailu podać dane osób rozwiązujących zadanie).

23.01.2025 — Dane testowe

W końcu udało mi się przygotować wszystkie pliki.

W pliku testy.zip znajdują się testy (pliki *.in) z poprawnymi odpowiedziami (pliki *.out). Testy są różnego typu (bez rozwiązań, z małymi lub dużymi rozwiązaniami). W pliku dane.zip znajdują się zestawy do rozwiązania. Dla każdego pliku *.in (z jakiegoś powodu brakuje tam pliku 03.in, ale proszę się tym nie przejmować) należy utworzyć plik *.out i przesłać razem z rozwiązaniem. Proszę zachować oznaczenia 01.out, 02.out itd.

Rozwiązania (kod źródłowy programu, rozwiązania dla powyższych danych i ewentualnie wyjaśnienie w osobnym pliku) należy wysłać na mój adres e-mail (tytuł: „Zadanie dodatkowe 1”) do północy 2 lutego 2024 (oczywiście punkty zostaną uwzględnione przy ocenie z ćwiczeń i ewentualnego zwolnienia z egzaminu). Prosiłbym o stosowanie jednego ze „standardowych” języków, powiedzmy C/C++/C#/Python/Java/JavaScript/Rust.

Nad zadaniem można pracować samodzielnie lub w parach (w tej sytuacji proszę w mailu podać dane osób rozwiązujących zadanie).

Za rozwiązanie zadania można otrzymać 15 pkt. Zestawy w pliku dane.zip są z grubsza posortowane poziomem trudności. Zestawy 01.in i 02.in są najłatwiejsze. Im numer pliku większy, tym rozwiązanie jest trudniejsze do znalezienia, ale też można za nie otrzymać więcej punktów. Przejście wszystkich testów daje 10 pkt., a dodatkowe 5 pkt. można otrzymać za jakiś w miarę sensowny opis sposobu rozwiązania. Nie chodzi oczywiście o komentowanie poszczególnych linii kodu, ale o wyjaśnienie, w jaki sposób działa Państwa algorytm.

Proszę pamiętać o tym, że program dla każdego pliku powinien kończyć działanie w rozsądnym czasie, powiedzmy 5 s.

Powodzenia!

PS. Dzisiaj powinno się również pojawić drugie zadanie dodatkowe.

18.01.2025 — Dane testowe do zadania dodatkowego

Bardzo przepraszam za zwłokę, ale ciągle mam drobne problemy z wygenerowaniem plików testowych, które mają odpowiednie własności. Proszę uzbroić się w jeszcze trochę cierpliwości.

12.01.2025 — Zadanie dodatkowe

Oto obiecene pierwsze zadanie do zaprogramowania, za które można zdobyć dodatkowe punkty, które zostaną dodane do wyników z kolokwiów i aktywności na zajęciach.

Treść zadania: Pokoje.

Za poprawne rozwiązanie zadania można otrzymać maksymalnie 15 pkt., przy czym 10 za program i 5 za opis rozwiązania.

Pliki testowe (zostaną wstawione 1517.01.2025):

  • input1,
  • input2,
  • input3.

Dla powyższych plików program powinien zwracać odpowiedź po maksymalnie 5 sekundach.

10.01.2025 — Harmonogram sesji

  • 4.02.2025 Egzamin I, godz. 12.15–14.00, sale E201 i E301.
  • 4.02.2025 Kolokwium poprawkowe I, godz. 14.15–16.00, sala E301.
  • 7.02.2025 Kolokwium poprawkowe II, godz. 10.15–12.00, sala E401.
  • 11.02.2025 Egzamin poprawkowy I, godz. 14.15–16.00, sale E201 i E301.
  • 14.02.2025 Egzamin poprawkowy II, godz. 10.15–12.00, sale E201 i E301.

Oczywiście powyższe terminy kolokwiów poprawkowych dotyczą grup 1.1–1.4. Przypominam również, że warunkiem przystąpienia do pierwszego egzaminu jest posiadanie zaliczenia ćwiczeń.

29.11.2024 — Zmiana sali

Ćwiczenia dla grupy 1.2 w czwartek 5. grudnia odbędą się w sali E402.

4.11.2024 — Zmiana terminu wykładu

W bieżącym tygodniu wykład z matematyki dyskretnej odbędzie się zamiast wykładu ze wstępu do matematyki we wtorek o godz. 10.15 w sali E201. Wykład ze wstępu do matematyki zostaje przeniesiony na piątek, godz. 12.15, sala E201.

Ćwiczenia dla grup 1.1 i 1.4 w aktualnym tygodniu się nie odbędą i zostaną odrobione w późniejszym terminie.

Wykład

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

Prowadzący

Wykład

Adam Gregosiewicz

Ćwiczenia

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 4.5 lub 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

  • Czwartek, 9.00–10.00, Pentagon, pok. 3 (PE 3).
  • Piątek, 11.00-12.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.

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 — 4.10.2024

Informacje organizacyjne. Wstępny program wykładu. Podstawy naiwnej teorii mnogości. Pojęcia zbioru i należenia do zbioru. Definiowanie zbiorów przez wyróżnianie elementów. Operacje na zbiorach (suma, iloczyn, różnica, różnica symetryczna, dopełnienie). Podzbiory i zbiory potęgowe. Para uporządkowana.

Materiały:

Tydzień 2 — 11.10.2024

Dowodzenie praw rachunku zbiorów. Definicja pary uporządkowanej i jej własności. Iloczyn kartezjańki zbiorów. Funkcja jako podzbiór iloczynu kartezjańskiego. Zasada indukcji matematycznej.

Materiały:

Tydzień 3 — 18.10.2024

Przykłady zastosowań zasady indukcji matematycznej.

Materiały:

Tydzień 4 — 25.10.2024

Podstawy logiki matematycznej. Rachunek zdań. Funktory zdanitwórcze. Podstawowe prawa rachunku zdań. Tautologie.

Materiały:

Tydzień 5 — 5.11.2024

Postać normalna formuły logicznej (CNF i DNF). Twierdzenie o istnieniu formuły równoważnej w postaci normalnej. Zupełne zbiory funktorów. Zupełność funktorów NAND i NOR. Informacje o problemie spełnialności (SAT) i P = NP.

Materiały:

Tydzień 6 — 15.11.2024

Problem P = NP. Funkcje zdaniowe. Wykres funkcji zdaniowej. Kwantyfikatory. Prawa rachunku kwantyfikatorów.

Materiały:

Tydzień 7 — 22.11.2024

Bramki logiczne. Budowa półsumatora i sumatora. Problem stopu. Relacje i ich własności.

Materiały:

Tydzień 8 — 29.11.2024

Relacje porządku. Diagram relacji porządku. Elementy wyróżnione i ich własności.

Materiały:

Tydzień 9 — 6.12.2024

Kresy zbiorów. Relacje równoważności. Zasada abstrakcji. Wprowadzenie do teorii liczb. Twierdzenie o dzieleniu z resztą.

Materiały:

Tydzień 10 — 13.12.2024

Dowód twierdzenia o dzieleniu z resztą. Algorytm obliczania ilorazu i reszty. Pojęcie niezmiennika pętli oraz dowód poprawności algorytmu. Największy wspólny dzielnik i metody jego obliczania. Algorytm Euklidesa.

Materiały:

Tydzień 11 — 20.12.2024

Złożoność algorytmu Euklidesa. Lemat Bézouta i rozszerzony algorytm Euklidesa. Relacja przystawania i własności kongruencji.

Materiały:

Tydzień 12 — 10.01.2024

Wykład odwołany z powodu niedostępności sali.

Tydzień 13 — 17.01.2025

Małe twierdzenie Fermata. Funkcja Eulera i twierdzenie Eulera. Element odwrotny. Rozwiązywanie kongruencji liniowych.

Materiały:

Tydzień 14 — 24.01.2025

Rozwiązywanie układów kongruencji. Chińskie twierdzenie o resztach. Systemy resztowe.

Materiały:

Tydzień 15 — 28.01.2025

Podstawy kryptografii. Problem dystrybucji klucza. Protokół Diffiego-Hellmana i problem logarytmu dyskretnego. Kryptosystem RSA.

Materiały:

Zestawy zadań

Każdy zestaw zadań podzielony jest 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.

Kolokwia i egzaminy