SylabUZ

Wygeneruj PDF dla tej strony

Matematyka dyskretna i matematyczne podstawy informatyki - opis przedmiotu

Informacje ogólne
Nazwa przedmiotu Matematyka dyskretna i matematyczne podstawy informatyki
Kod przedmiotu 11.0-WK-MATD-MDMPI-Ć-S14_pNadGenS3ESS
Wydział Wydział Matematyki, Informatyki i Ekonometrii
Kierunek Matematyka
Profil ogólnoakademicki
Rodzaj studiów drugiego stopnia z tyt. magistra
Semestr rozpoczęcia semestr zimowy 2019/2020
Informacje o przedmiocie
Semestr 1
Liczba punktów ECTS do zdobycia 7
Typ przedmiotu obowiązkowy
Język nauczania polski
Sylabus opracował
  • dr hab. Ewa Drgas-Burchardt, prof. UZ
Formy zajęć
Forma zajęć Liczba godzin w semestrze (stacjonarne) Liczba godzin w tygodniu (stacjonarne) Liczba godzin w semestrze (niestacjonarne) Liczba godzin w tygodniu (niestacjonarne) Forma zaliczenia
Ćwiczenia 30 2 - - Zaliczenie na ocenę
Wykład 30 2 - - Egzamin

Cel przedmiotu

Wykształcenie zdolności badania istnienia, oraz rozróżniania i przeliczania obiektów kombinatorycznych. Wskazanie możliwości wykorzystania tych zdolności, w celu szacowania wielkości danych i zasobów niezbędnych do rozwiązania danego problemu i badania jego złożoności.

Wymagania wstępne

Ukończone studia licencjackie z nauk matematyczno-przyrodniczych lub technicznych.

Zakres tematyczny

Wykład

  1. Elementy kombinatoryki: metody przeliczania obiektów kombinatorycznych oznaczonych i nieoznaczonych, twierdzenie Polya (12 godz.).
  2. Elementy teorii grafów: spójność, skojarzenia, twierdzenie Halla, cykle Hamiltona, kolorowanie wierzchołków i krawędzi grafów, zagadnienia ekstremalnej teorii grafów, Twierdzenie Turana i Ramseya (6 godz.).
  3. Metoda probabilistyczna Erdösa (6 godz.).
  4. Elementy teorii obliczeń: funkcje obliczalne, maszyny Turinga, tezy Churcha (6 godz.).

Ćwiczenia

  1. Elementy kombinatoryki: rozpoznawanie obiektów kombinatorycznych w zadaniu z treścią; odniesienia do pojęcia funkcji działającej na zbiorach skończonych, które są dowolne, różnowartościowe, „na”, malejące, niemalejące; wykorzystanie znanych wzorów w celu zliczenia rozpoznanych obiektów (5 godz.); stosowanie zasad: podziałowej, włączeń i wyłączeń, podwójnego zliczania, do obiektów kombinatorycznych oznaczonych (5 godz.); stosowanie twierdzenia Polya do zliczania obiektów kombinatorycznych nieoznaczonych (4 godz.).
  2. Elementy teorii grafów: rozpoznawanie pojęć teorii grafów w zadaniach z treścią, stosowanie znanych algorytmów teoriografowych w celu rozwiązania tych zadań (2 godz.); znajdowanie oszacowań małych liczb Ramseya, dowodzenie twierdzeń dotyczących grafów i liczb Ramseya z wykorzystaniem klasycznych technik dowodu poznanych na wykładzie (2 godz.).
  3. Metoda probabilistyczna Erdösa: dowodzenie faktów dotyczących struktur kombinatorycznych z wykorzystaniem metod: naiwnej, wartości oczekiwanej i Lokalnego Lematu Lovásza (6 godz.).
  4. Elementy teorii obliczeń: konstruowanie programów dla maszyn Turinga, badanie obliczalności funkcji (4 godz.).
  5. Kolokwium (2 godz.).

Metody kształcenia

Wykład konwersatoryjny, ćwiczenia dyskusyjne.

Efekty uczenia się i metody weryfikacji osiągania efektów uczenia się

Opis efektu Symbole efektów Metody weryfikacji Forma zajęć

Warunki zaliczenia

  1. Sprawdzian z zadaniami o zróżnicowanym stopniu trudności, pozwalający na ocenę czy i w jakim stopniu, student osiągnął wymienione efekty kształcenia głównie w zakresie umiejętności i kompetencji.
  2. Konwersacja podczas wykładu w celu weryfikacji wyższych poziomów efektów kształcenia w zakresie wiedzy i umiejętności.
  3. Egzamin pisemny i w razie konieczności egzamin ustny weryfikujący efekty kształcenia w zakresie wiedzy i kompetencji.

Na ocenę z przedmiotu składa się ocena z ćwiczeń (50%) i ocena z egzaminu (50%). Warunkiem przystąpienia do egzaminu jest uzyskanie pozytywnej oceny z ćwiczeń. Warunkiem zaliczenia przedmiotu jest uzyskanie pozytywnych ocen z ćwiczeń i z egzaminu.

Literatura podstawowa

  1. W. Lipski, W. Marek, Analiza kombinatoryczna, PWN, Warszawa, 1989.
  2. C.H. Papadimitriou, Złożoność obliczeniowa, WNT, Warszawa 2002 (seria Klasyka Informatyki).
  3. Diesel, Grach Theory, Springer-Verlag, Heidelberg, Gradule Test In Mathematics, Vol. 173.
  4. Kościelski, Teoria obliczeń, WUW, Wrocław, 1997.

Literatura uzupełniająca

  1. Z. Palka, A. Ruciński, Wykłady z kombinatoryki, cz. I, WNT, Warszawa, 1998.
  2. W. Lipski, Kombinatoryka dla programistów, WNT, 2005.
  3. K.A. Ross, Ch.R.B. Wright, Matematyka dyskretna, PWN, Warszawa, 1996.
  4. R.J. Wilson, Wprowadzenie do teorii grafów, PWN, 1998.

Uwagi


Zmodyfikowane przez dr Alina Szelecka (ostatnia modyfikacja: 14-03-2020 09:05)