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

Matematyka dyskretna

Informacje ogólne

Kod przedmiotu: 1000-212bMD Kod Erasmus / ISCED: 11.001 / (0540) Matematyka i statystyka
Nazwa przedmiotu: Matematyka dyskretna
Jednostka: Wydział Matematyki, Informatyki i Mechaniki
Grupy: Przedmioty obowiązkowe dla I roku informatyki
Przedmioty obowiązkowe dla II roku (4. semestr) JSIM - wariant 3I+4M
Przedmioty obowiązkowe dla II roku (4. semestr) JSIM - wariant 3M+4I
Punkty ECTS i inne: 7.50
zobacz reguły punktacji
Język prowadzenia: polski
Rodzaj przedmiotu:

obowiązkowe

Wymagania (lista przedmiotów):

Analiza matematyczna inf. I 1000-211bAM1
Geometria z algebrą liniową 1000-211bGAL
Podstawy matematyki 1000-211bPM

Skrócony opis:

Aparat matematyczny niezbędny do układania i analizy algorytmów: elementy kombinatoryki, teorii grafów i teorii liczb.

Pełny opis:

* Indukcja matematyczna i rekurencje

* Sumy skończone

* Współczynniki dwumianowe

* Permutacje i podziały

* Funkcje tworzące i ich zastosowania

* Metody zliczania

- enumeratory

- zasada włączania-wyłączania

* Asymptotyka:

- notacja asymptotyczna (O,\Omega, \Theta, o, \omega)

- twierdzenie o rekurencji uniwersalnej

* Elementarna teoria liczb:

- podzielność, liczby pierwsze, rozkład na czynniki pierwsze

- NWD i algorytm Euklidesa

* Arytmetyka modularna:

- małe twierdzenie Fermata i twierdzenie Eulera

- chińskie twierdzenie o resztach

- rozwiązywanie równań modularnych

* Elementy kryptografii: test Millera-Rabina i system RSA

* Grafy:

- ścieżki, drzewa i cykle

- cykle Eulera i Hamiltona

- grafy dwudzielne, skojarzenia i twierdzenie Halla

- planarność

- kolorowanie grafów

Literatura:

1. R.L.Graham, D.E.Knuth, O.Patashnik, Matematyka Konkretna, Państwowe Wydawnictwo Naukowe, Warszawa 2013.

2. W.Lipski, Kombinatoryka dla programistów, Wydawnictwa Naukowo-Techniczne 2004.

3. Z.Palka, A.Ruciński, Wykłady z kombinatoryki, Wydawnictwa Naukowo-Techniczne 2009

4. R.J.Wilson, Wprowadzenie do teorii grafów, Państwowe Wydawnictwo Naukowe, Warszawa 2012.

Efekty kształcenia:

Wiedza

1. Ma wiedzę w zakresie kombinatoryki, teorii grafów i elementarnej teorii liczb dającą matematyczne podstawy projektowania algorytmów (K_W01).

2. Rozumie i potrafi stosować notację asymptotyczną (K_W01).

3. Rozumie rolę i znaczenie konstrukcji rozumowań matematycznych (K_W01, K_W02).

Umiejętności

1. Potrafi analizować i rozwiązywać proste problemy z zakresu matematyki dyskretnej (K_U01).

2. Potrafi zrozumieć i stosować formalny opis obiektów matematycznych (K_U01, K_U03).

Kompetencje

1. Zna ograniczenia własnej wiedzy i rozumie potrzebę dalszego kształcenia (K_K01).

2. Potrafi precyzyjnie formułować pytania, służące pogłębieniu własnego zrozumienia danego tematu lub odnalezieniu brakujących elementów rozumowania (K_K02).

Metody i kryteria oceniania:

Kolokwia, egzamin pisemny.

Zajęcia w cyklu "Semestr letni 2018/19" (zakończony)

Okres: 2019-02-16 - 2019-06-08
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 60 godzin więcej informacji
Wykład, 45 godzin więcej informacji
Koordynatorzy: Adam Malinowski
Prowadzący grup: Paweł Górecki, Mirosław Kowaluk, Adam Malinowski, Marcin Małogrosz, Wanda Niemyska, Oskar Skibski, Tomasz Wąs
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin

Zajęcia w cyklu "Semestr letni 2019/20" (jeszcze nie rozpoczęty)

Okres: 2020-02-17 - 2020-06-10
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 60 godzin więcej informacji
Wykład, 45 godzin więcej informacji
Koordynatorzy: Adam Malinowski
Prowadzący grup: Kunal Dutta, Małgorzata Gałązka, Paweł Górecki, Mirosław Kowaluk, Adam Malinowski, Marcin Małogrosz, Oskar Skibski, Tomasz Wąs
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Warszawski.