Adam Gregosiewicz
Adam Gregosiewicz

Matematyka dyskretna | I1S | semestr zimowy 2022/2023

Aktualności

5.02.2023 Wyniki drugiego kolokwium

Wyniki Państwa drugiego kolokwium umieszczę dzisiaj w naszej grupie teamsowej. Rozwiązania zadań z kolokwium znajdą Państwo na dole strony.

31.01.2023 Plan sesji

Egzaminy

  • Egzamin: 9.02.2023, 14.15, sale E201 i E301.
  • Pierwszy egzamin poprawkowy: 16.02.2023, 14.15, sale E201 i E301.
  • Drugi egzamin poprawkowy: 23.02.2023, 10.15, sala E301.

Oczywiście zgodnie z umową, otrzymanie oceny 4.5 lub 5.0 z ćwiczeń (w pierwszym terminie, nie w poprawce) zwalnia z egzaminu. Aby przystąpić do egzaminu w pierwszym terminie należy uzyskać zaliczenie ćwiczeń w pierwszym terminie (nie w poprawce).

Kolokwia (dla moich grup 1.5-1.7)

  • Drugie kolokwium: 3.02, 14.00, sala E201, grupy 1.5 i 1.6 oraz 3.02, 15.30, sala E201, grupa 1.7.
  • Pierwsze kolokwium poprawkowe: 9.02, 16.00, sala E301, grupy 1.5-1.7.
  • Drugie kolokwium poprawkowe: 13.02, godz. 16.00, sala E301, grupy 1.5-1.7.

21.12.2022 Rozwiązania zadań z kolokwium

Przygotowałem dla Państwa rozwiązania zadań z poniedziałkowego kolokwium. Linki znajdują się na dole strony. Wyniki kolokwium przekażę natomiast pod koniec tygodnia.

13.12.2022 Kolokwium dla grup 1.5, 1.6 i 1.7

Terminy pierwszego kolokwium:

  • Grupy 1.5 i 1.7: poniedziałek 19.12.2022, 18.15–19.45, Aula 1 (Wydział Mechaniczny).
  • Grupa 1.6: poniedziałek 19.12.2022, 16.15–17.45, sala E401 (Wydział Elektrotechniki i Informatyki).

Kolokwium będzie obejmowało rachunek zdań, kwantyfikatory, teorię mnogości i indukcję.

Uwaga. Podczas kolokwium trzeba mieć ze sobą tylko coś do pisania. Nie można korzystać z notatek, książek, telefonów, tabletów, smartwatchy etc., a praca musi być samodzielna.

Wykład

  • Czwartek, 12.15–14.00, sala E401 (grupy 1.7–1.10)
  • Piątek, 12.15–13.45, sala E201 (grupy 1.1–1.6)

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: 76r3m3c).

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

Konsultacje

Adam Gregosiewicz

  • Poniedziałek, 12.15–13.45, Pentagon, pok. 3.

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

Wykład 1 — 6.10.2022

Informacje organizacyjne. Podstawowe pojęcia logiki. Podstawowe wiadomości o funktorach zdaniotwórczych. Funktory XOR, NAND i NOR. Zupełność zbioru funktorów. Prawa rachunku zdań. Różne metody sprawdzania, czy formuła logiczna jest tautologią.

Literatura:

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

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.

Wykład 2 — 13.10.2022

Postacie normalne formuł logicznych (CNF i DNF). Twierdzenie o istnieniu formuły normalnej równoważnej zadanej formule. Spełnialność formuł. Problem SAT i P = NP.

Literatura:

  • [2] rozdz. 10.

Materiały dodatkowe:

Wykład 3 — 20.10.2022

Idea dowodów nie wprost. Funkcje zdaniowe jednej i wielu zmiennych. Kwantyfikatory. Wykresy funkcji zdaniowych. Podstawowe pojęcia (naiwnej) teorii mnogości. Prawa rachunku zbiorów. Różne metody dowodzenia równości zbiorów. Iloczyn kartezjański.

Literatura:

  • [3] rozdz. 2.3 (dowody nie wprost).
  • [3] rozdz. 13 i [2] rozdz. 12 (kwantyfikatory).
  • [3] rozdz. 1 i [2] rozdz. 5 (teoria mnogości).

Wykład 4 — 27.10.2022

Paradoksy naiwnej teorii mnogości. Antynomia Russella. Problem stopu. Zasada indukcji matematycznej. Proste przykłady zastosowania indukcji.

Literatura:

  • [3] rozdz. 4 i [2] rozdz. 3 i 4 (indukcja).

Materiały dodatkowe:

Wykład 5 — 3.11.2022

Zasada indukcji zupełnej. Mniej typowe przykłady zastosowania indukcji: ciągi zadane rekurencyjnie, równoważność systemów pozycyjnych o różnych podstawach, teoria grafów).

Literatura:

  • Zob. wykład 4.

Materiały dodatkowe:

Wykład 6 — 10.11.2022

Relacje. Podstawowe własności relacji. Relacje porządku częściowego i liniowego. Elementy wyróżnione i ich własności.

Literatura:

  • [3] rozdz. 3.1 i [2] rozdz. 14.

Materiały dodatkowe:

Wykład 7 — 17.11.2022

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

Literatura:

  • [3] rozdz. 3.5 i [2] rozdz. 14.

Wykład 8 — 24.11.2022

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

Literatura:

  • [3] rozdz. 3.6.

Wykład 9 — 1.12.2022

Największy wspólny dzielnik i jego własności. Naiwny algorytm znajdowania NWD. Twierdzenie i algorytm Euklidesa. Dowód poprawności algorytmu Euklidesa oraz analiza jego złożoności.

Literatura:

  • [3] rozdz. 4.6.

Wykład 10 — 8.12.2022

Tożsamość Bézouta. Rozszerzony algorytm Euklidesa. Wprowadzenie do kongruencji.

Literatura:

  • [3] rozdz. 4.6 i [1] rozdz. 9.2.

Wykład 11 — 15.12.2022

Własności kongruencji. Działania w zbiorach reszt. Rozwiązywanie kongruencji liniowych.

Literatura:

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

Notatki do wykładu

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

Poniżej znajdują się kolokwia, które przeprowadzałem dla grup 1.5–1.7: