Politechnika Warszawska - Centralny System UwierzytelnianiaNie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

Matematyka 1 - Wstęp do matematyki

Informacje ogólne

Kod przedmiotu: 103A-CBxxx-ISP-MAT1 Kod Erasmus / ISCED: (brak danych) / (brak danych)
Nazwa przedmiotu: Matematyka 1 - Wstęp do matematyki
Jednostka: Wydział Elektroniki i Technik Informacyjnych
Grupy: ( Matematyka )-Cyberbezpieczeństwo-inż.-EITI
( Przedmioty techniczne )---EITI
Punkty ECTS i inne: 4.00
Język prowadzenia: polski
Jednostka decyzyjna:

103000 - Wydział Elektroniki i Technik Informacyjnych

Kod wydziałowy:

MAT1

Numer wersji:

1

Skrócony opis:

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.

Pełny opis:

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.
  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. 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. Algebry Boole’a, zastosowania w układach logicznych. Bramki tranzystorowe.
  2. Zasada włączeń i wyłączeń.
  3. Zasada indukcji matematycznej jako metoda dowodzenia twierdzeń. Zasada minimum. Zastosowania w dowodzeniu poprawności algorytmów - zadanie o wieży z Hanoi. Liczby Fermata.
  4. Rekursja jako metoda definiowania obiektów.
  5. Splot ciągów.
  6. Zadania o podziale.
  7. Twierdzenie Picka.
  8. Kod Prufera – jak zapamiętać drzewo, kod Hufmana - kompresja danych.
  9. Sito Eratostenesa, algorytm Euklidesa, NWW i NWD.
  10. Diagramy automatów skończonych.



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. Łamigłówki logiczne.
  2. Wybrane zadania stosujące wzór włączeń i wyłączeń.
  3. Liczby Fibonacciego.
  4. Problemy upakowania. Zasada szufladkowa Dirichleta.
  5. Kwadraty łacińskie.
  6. Twierdzenie o czterech barwach i kolorowanie grafów.
  7. Algorytmy rozpoznawania pierwszości.


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

Literatura:

  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.

Metody i kryteria oceniania:

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.

Zajęcia w cyklu "rok akademicki 2019/2020 - sem. zimowy" (w trakcie)

Okres: 2019-10-01 - 2020-02-21
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 15 godzin, 60 miejsc więcej informacji
Projekt, 15 godzin, 60 miejsc więcej informacji
Wykład, 15 godzin, 60 miejsc więcej informacji
Koordynatorzy: Agata Pilitowska
Prowadzący grup: Agata Pilitowska
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

112000 - Wydział Matematyki i Nauk Informacyjnych

Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Politechnika Warszawska.