Matematyka 1 - Wstęp do matematyki

103000 - Wydział Elektroniki i Technik Informacyjnych

MAT1

1

Głównym celem przedmiotu jest nauczenie studentów właściwego stosowania formalizmu matematycznego, poprawnego formułowania problemów matematycznych i technicznych, dobrego zrozumienia pojęcia dowodu matematycznego i zdobycie przez nich umiejętności dowodzenia prostych faktów. Ponadto w ramach przedmiotu zostaną wprowadzone i omówione takie podstawowe pojęcia jak zbiór, relacja, funkcja. Zaprezentowane zostaną również wybrane zagadnienia kombinatoryczne, podstawowe problemy teorii grafów oraz teorii liczb.

Głównym celem przedmiotu jest nauczenie studentów właściwego stosowania formalizmu matematycznego, poprawnego formułowania problemów matematycznych i technicznych, dobrego zrozumienia pojęcia dowodu matematycznego i zdobycie przez nich umiejętności dowodzenia prostych faktów. Ponadto w ramach przedmiotu zostaną wprowadzone i omówione takie podstawowe pojęcia jak zbiór, relacja, funkcja. Zaprezentowane zostaną również wybrane zagadnienia kombinatoryczne, podstawowe problemy teorii grafów oraz teorii liczb.

Założeniem prowadzenia przedmiotu jest ukierunkowanie na kształcenie z wykorzystaniem wielu form i metod. Wykład będzie miał charakter informacyjny z elementami wykładu problemowego. Pojęcia o znacznym stopniu abstrakcji będą obrazowane przykładami praktycznymi. Na ćwiczeniach będą rozwiązywane zadania odnoszące się do tematów prezentowanych na wykładzie, jak i treści, które studenci będą musieli przygotować lub uzupełnić we własnym zakresie. Podczas tych zajęć wykorzystywany będzie system zeszyt.online oraz różnorodne prezentacje multimedialne. W ramach zajęć projektowych studenci, w 4-osobowych grupach, będą opracowywali zagadnienia nawiązujące, ilustrujące bądź rozszerzające wybrane tematy wprowadzone na wykładach i ćwiczeniach. Ponadto przygotują materiały z tego zakresu dla studentów z pozostałych grup projektowych.

Treść wykładu

1. Logika (2 godz.)
   Operatory logiczne, prawa rachunku zdań, tautologie, postać normalna formuł logicznych. Niesprzeczność, zupełność. Twierdzenie Godla. Rachunek kwantyfikatorów. Dowody. Złożoność algorytmów, zagadnienia P-NP.
2. Elementy teorii mnogości (1 godz.)
   Zbiory, antynomia Russella. Działania na zbiorach. Różne rodzaje nieskończoności. Hipotez continuum.
3. Funkcje i relacje (2 godz.)
   Relacja równoważności, podziały zbioru. Relacje porządkujące. Lemat Kuratowskiego – Zorna.
4. Elementy kombinatoryki (2 godz.)
   Permutacje i kombinacje. Rozkład permutacji na cykle, parzystość permutacji. Najważniejsze tożsamości kombinatoryczne. Współczynniki dwumianowe, trójkąt Pascala. Wybrane zadania stosujące wzór włączeń i wyłączeń.
5. Funkcje tworzące (2 godz.)
   Problemy zliczania. Zasada działania funkcji tworzących. Wyprowadzenie wzoru na liczby Catalana.
6. Metody teorii grafów (2 godz.)
   Podstawowe pojęcia. Problem mostów królewieckich. Grafy Eulera i Hamiltona. Grafy dwudzielne i planarne. Wzór Eulera. Twierdzenie o czterech barwach i kolorowanie grafów. Skojarzenia i twierdzenie Halla o małżeństwach.
7. Elementarna teoria liczb (2 godz.)
   Liczby pierwsze. Zasadnicze Twierdzenie Arytmetyki. Twierdzenie Wilsona i Małe Twierdzenie Fermata. Funkcja Eulera. Rozmieszczenie liczb pierwszych.
8. Automaty skończone (2 godz.)
   Automaty deterministyczne i niedeterministyczne. Wyrażenia regularne. Model maszyny Turinga. Sieci Petriego.

Treść ćwiczeń
Ćwiczenia audytoryjne będą głównie nakierowane na ilustrację zadań i problemów poruszanych na wykładach. Zostaną omówione m.in. następujące zagadnienia:

1. Liczby zespolone. Interpretacje geometryczne. Postać algebraiczna, trygonometryczna, wykładnicza. Pierwiastkowanie liczb zespolonych, wzór Moivre'a.
2. Rozkład funkcji wymiernej na sumę ułamków prostych.
3. Zasada włączeń i wyłączeń.
4. Zasada indukcji matematycznej jako metoda dowodzenia twierdzeń. Zasada minimum. Zastosowania w dowodzeniu poprawności algorytmów - zadanie o wieży z Hanoi. Liczby Fermata.
5. Rekursja jako metoda definiowania obiektów.
6. Splot ciągów.
7. Zadania o podziale.
8. Problemy upakowania. Zasada szufladkowa Dirichleta.
9. NWW i NWD, algorytm Euklidesa.

Zakres projektu

W ramach projektu zespoły 4-osobowe opracują prezentacje zastosowań praktycznych zagadnień omawianych na wykładach lub na ćwiczeniach. W zakres tematyki projektów będą wchodziły między innymi:

1. Zastosowania w układach logicznych. Bramki tranzystorowe.
2. Kwadraty łacińskie. Ortogonalne kwadraty łacińskie.
3. Liczby Fibonacciego i inne ciągi zadane rekurencyjnie.
4. Permutacje i łamigłówki logiczne.
5. Kod Prufera - jak zapamiętać drzewo. Kod Graya i cykle hamiltonowskie.
6. Algorytmy rozpoznawania pierwszości. Sito Eratostenesa.
7. Algorytmy faktoryzacji liczb całkowitych.
8. Rozmieszczenie liczb pierwszych.
9. Liczby całkowite Gaussa.

Ponadto elementem projektu będzie przygotowanie materiałów z danego zakresu dla studentów z pozostałych grup projektowych.

1. L. Bogusz, P. Zarzycki, J. Zieliński, Łamigłówki logiczne, t. I i t. II, Gdańskie Wydawnictwo Oświatowe, Gdańsk 2000.
2. V. Bryant, Aspekty kombinatoryki, WNT, Warszawa 2007.
3. W. J. Gilbert, W. K. Nicholson, Algebra współczesna z zastosowaniami, WNT, Warszawa 2008.
4. W. Guzicki, P. Zakrzewski, Wykłady ze wstępu do matematyki, Wydawnictwo Naukowe PWN, Warszawa 2005.
5. N. Koblitz, Wykłady z teorii liczb i kryptografii, WNT, Warszawa 1995.
6. J. Kraszewski, Wstęp do matematyki, WNT, Warszawa 2007.
7. S.Y. Yan, Teoria liczb w informatyce, WNT, Warszawa, 2006.
8. M. Zakrzewski, Markowe wykłady z matematyki – matematyka dyskretna, Oficyna Wydawnicza GiS, Wrocław 2014.
9. M. Zakrzewski, Markowe wykłady z matematyki – teoria liczb, Oficyna Wydawnicza GiS, Wrocław 2017.

Inne:
Pakiety matematyczne oraz prezentacje internetowe do realizacji zadań zarówno teoretycznych jak i praktycznych w ramach wykładów, ćwiczeń i zajęć projektowych.

Sprawdzanie założonych efektów kształcenia realizowane jest przez:

• ocenę wiedzy i umiejętności rozwiązywania zadań na ćwiczeniach – ocenę aktywności na zajęciach i 1 kolokwium;
• ocenę wiedzy i umiejętności związanych z realizacją zadań projektowych – ocena prezentacji i raportu z przeglądu literatury;
• ocenę wiedzy i umiejętności wykazanych na egzaminie pisemnym o charakterze problemowym oraz – w przypadkach wątpliwości co do oceny – na egzaminie ustnym.