Adam Gregosiewicz
Adam Gregosiewicz

Matematyka dyskretna | I1S | semestr zimowy 2023/2024

Aktualności

27.02.2024 — Dodatkowe terminy poprawkowe

Kolokwium (dotyczy grup 1.2, 1.5–1.7):

  • 28.02.2024, 18.00–19.15, sala E401.

Egzamin:

  • 1.03.2024, 14.15-15.15, sala E201.

27.01.2024 — Harmonogram sesji zimowej

Egzaminy:

  • Egzamin: 7.02.2024, 14.15–15.45, sale E201 i E301.
  • Egzamin poprawkowy 1: 12.02.2024, 14.15–15.45, sale E201 i E301.
  • Egzamin poprawkowy 2: 14.02.2024, 18.15–19.45, sale E201 i E301.

Przypominam, że do pierwszego egzaminu (7.02) mogą przystąpić jedynie osoby, które uzyskały zaliczenie ćwiczeń w pierwszym terminie.

Kolokwia poprawkowe (dotyczy grup 1.2, 1.5–1.7):

  • Kolokwium poprawkowe 1: 7.02.2024, 12.15–13.45, sala E301,
  • Kolokwium poprawkowe 2: 9.02.2024, 16.15–17.45, sala E301.

15.01.2024 — Zadanie dodatkowe 2

Oto drugie zadanie do zaprogramowania dla chętnych.

Treść zadania: reprezentacja_elfowa.pdf.

Punktacja: Za rozwiązanie zadania można otrzymać maksymalnie 20 pkt., przy czym:

  • 12 pkt. za poprawną odpowiedź dla wejścia:
1
2
3
4

3
50000
100000
150000
  • 8 pkt. za wyjaśnienie matematyczne istoty rozwiązania.

Rozwiązania (kod źródłowy programu, odpowiedź dla powyższych danych i ewentualnie wyjaśnienie) należy wysłać na mój adres e-mail (tytuł: „Zadanie dodatkowe 2”) do północy 28 stycznia 2024. Prosiłbym o stosowanie jednego ze „standardowych” języków, powiedzmy C/C++/C#/Python/Java/JavaScript/Rust.

Powodzenia!

14.11.2023 — Zadanie dodatkowe

Przygotowałem dla Państwa zadanie do zaprogramowania, za które można zdobyć dodatkowe punkty. Oczywiście zadanie jest dla chętnych, ale wszystkich namawiam do jego przemyślenia.

Treść zadania: wiadomosc.pdf.

Punktacja: Do odkodowania są trzy pliki:

Łącznie za rozwiązanie zadania można uzyskać 20 pkt., przy czym:

  • za odkodowanie pliku messages7.in można uzyskać 2 pkt.,
  • za odkodowanie pliku messages13.in można uzyskać 4 pkt.,
  • za odkodowanie pliku messages16.in można uzyskać 6 pkt.,
  • za wyjaśnienie matematyczne istoty rozwiązania można uzyskać 8 pkt.

Rozwiązania (kod źródłowy programu, odkodowane wiadomości i ewentualnie wyjaśnienie) należy wysłać na mój adres e-mail do 30 listopada 2023. Prosiłbym o stosowanie jednego ze „standardowych” języków, powiedzmy C/C++/C#/Python/Java/JavaScript/Rust.

Uzyskane punkty będą dodane do Państwa wyników z ćwiczeń. Podobnych zadań w trakcie semestru będzie kilka, więc istnieje możliwość otrzymania nawet oceny 5.0 (z ćwiczeń i egzaminu) wyłącznie za rozwiązanie zadań dodatkowych.

Powodzenia!

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ń.

Kontakt

Strona przedmiotu w MS Teams: link (kod dostępu: 2erl5ey).

Wszelkie pytania lub komentarze (dotyczące treści wykładu, zadań, kolokwiów, egzaminu, etc.) proszę zgłaszać przez stronę zespołu. Zachęcam do używania kanału ogólnego — skorzysta na tym na pewno więcej osób.

Konsultacje

Adam Gregosiewicz

  • Czwartek, 8.15–9.45, Pentagon, pok. 3 (PE3).

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

Ponadto, jak wspomniałem wyżej, zachęcam do korzystania z zespołu teamsowego. To najlepszy sposób na uzyskanie pomocy.

Materiały

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

Z powodu godzin dziekańskich (dziękujemy naszym kochanym Władzom Dziekańskim) pierwszy wykład sie nie odbył.

Tydzień 2 — 13.10.2023

Informacje organizacyjne. Podstawowe pojęcia logiki. Podstawowe wiadomości o funktorach zdaniotwórczych. Funktory XOR, NAND i NOR. Prawa rachunku zdań.

Materiały:

Literatura:

  • [2] rozdz. 9 i [3] rozdz. 2.

Materiały dodatkowe:

  • Bardzo dobre notatki poświęcone rachunkowi zdań z ważniaka.
  • Dużo sensownych zadań z logiki można znaleźć w książce W. Marka i J. Onyszkiewicza Elementy logiki i teorii mnogości w zadaniach.

Tydzień 3 — 20.10.2023

Pojęcie tautologii oraz spełnialności. Koniunkcyjna i dysjunkcyjna postać normalna. Twierdzenie o istnieniu równoważnych formuł CNF i DNF dla dowolnej formuły logicznej. Zupełność zbioru funktorów. Twierdzenie o zupełności funktorów NAND i NOR. Funkcje zdaniowe i ich wykresy. Pojęcie kwantyfikatora.

Materiały:

Literatura:

  • [2] rozdz. 10 i 12.

Materiały dodatkowe:

  • Dużo sensownych zadań z logiki można znaleźć w książce W. Marka i J. Onyszkiewicza Elementy logiki i teorii mnogości w zadaniach.

Tydzień 4 — 27.10.2023

Własności kwantyfikatorów. Zmienne wolne i związane. Podstawy teorii mnogości. Konstruktory zbiorów, podstawowe operacje na zbiorach. Prawa rachunku zbiorów i ich dowodzenie.

Materiały:

Literatura:

  • [2] rozdz. 5 i [3] rozdz. 1.

Materiały dodatkowe:

  • W. Marek i J. Onyszkiewicz, Elementy logiki i teorii mnogości w zadaniach.

Tydzień 5 — 3.11.2023

Dowodzenie praw rachunku zbiorów. Para uporządkowana i iloczyn kartezjański. Antynomia Russella. Problem stopu. Bramki logiczne i budowa sumatorów.

Materiały:

Literatura:

  • [1] rozdz. 8.2–8.3 (problem stopu, antynomia Russella)
  • [2] rozdz. 11 i [3] rozdz. 10 (bramki logiczne).

Materiały dodatkowe:

Tydzień 6 — 10.11.2023

Bramki logiczne i sumatory. Złożoność obliczeniowa. Problem P=NP.

Materiały:

Materiały dodatkowe:

Tydzień 7 — 17.11.2023

Zasada indukcji matematycznej.

Materiały:

Literatura:

  • [2] rozdz. 3–4 i [3] rozdz. 4.

Materiały dodatkowe:

Tydzień 8 — 24.11.2023

Relacje i ich podstawowe własności. Relacje porządku, elementy wyróżnione.

Materiały:

Literatura:

  • [2] rozdz. 14 i [3] rozdz. 3.
  • W. Marek i J. Onyszkiewicz, Elementy logiki i teorii mnogości w zadaniach.

Tydzień 9 — 1.12.2023

Kresy zbiorów uporządkowanych. Relacje równoważności. Zasada abstrakcji.

Materiały:

Literatura:

  • [2] rozdz. 14 i [3] rozdz. 3.5.
  • W. Marek i J. Onyszkiewicz, Elementy logiki i teorii mnogości w zadaniach.

Tydzień 10 — 8.12.2023

Podzielność liczb całkowitych. Twierdzenie o dzieleniu z resztą. Funkcje podłogi i sufitu. Algorytm dzielenia z resztą. Niezmienniki pętli i twierdzenie o niezmiennikach. Dowód poprawności algorytmu dzielenia z resztą. Największy wspólny dzielnik i jego własności. Naiwny algorytm znajdowania NWD.

Materiały:

Literatura:

  • [3] rozdz. 3.6 i 4.6.

Tydzień 11 — 15.12.2023

Twierdzenie i algorytm Euklidesa. Dowód poprawności algorytmu Euklidesa oraz analiza jego złożoności. Tożsamość Bézouta. Rozszerzony algorytm Euklidesa.

Materiały:

Literatura:

  • [3] rozdz. 4.6.

Tydzień 12 — 12.01.2024

Kongruencje i ich podstawowe własności. Działania w zbiorach reszt. Małe twierdzenie Fermata. Funkcja Eulera. Rozwiązywanie kongruencji liniowych.

Materiały:

Literatura:

  • [2] rozdz. 30, [3] rozdz. 3.6, [1] rozdz. 9.6–9.7.

Tydzień 13 — 19.01.2024

Element odwrotny względem relacji przystawania. Istnienie i jedyność elementu odwrotnego. Rozwiązywanie układów kongruencji. Chińskie twierdzenie o resztach. Systemy resztowe. Wprowadzenie do kryptografii.

Materiały:

Literatura:

  • [3] rozdz. 4.6, [1] rozdz. 9.9.

Tydzień 14 — 19.01.2024

Problem dystrybucji klucza. Protokół Diffiego-Hellmana. Problem logarytmu dyskretnego. Kryptosystem RSA. Wstęp do teorii grafów. Podstawowe rodziny grafów.

Materiały:

Literatura:

  • [2] rozdz. 31.

Zainteresowanym historią oraz podstawami kryptografii polecam przystępne książki:

  • Steven Levy, Rewolucja w kryptografii,
  • Simon Singh, Księga szyfrów. Zdecydowanie więcej szczegółów teoretycznych można znaleźć na przykład w książce:
  • Neal Koblitz, Algebraiczne aspekty kryptografii.

Tydzień 15 — 26.01.2024

Podstawowe pojęcia teorii grafów. Problem mostów królewieckich. Grafy eulerowskie. Twierdzenie Eulera charakteryzujące grafy eulerowskie. Algorytm Fleury’ego. Grafy hamiltonowskie. Poszukiwanie najkrótszej ścieżki w grafie skierowanym z wagami. Algorytm Dijkstry.

Materiały:

Literatura:

  • [3] rozdz. 6.

Zestawy zadań

Każdy zestaw zadań podzielony jest na dwie lub trzy częśći: A, B i (czasami) C. 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. Zachęcam też do otwartej dyskusji o wszystkich zadaniach w naszym zespole teamsowym.

Kolokwia

Kolokwia z lat ubiegłych można znaleźć na archiwalnych stronach przedmiotu.