Moduł oferowany także w ramach programów studiów:
Informacje ogólne:
Nazwa:
Matematyka dyskretna
Tok studiów:
2014/2015
Kod:
IIN-1-107-s
Wydział:
Informatyki, Elektroniki i Telekomunikacji
Poziom studiów:
Studia I stopnia
Specjalność:
-
Kierunek:
Informatyka
Semestr:
1
Profil kształcenia:
Ogólnoakademicki (A)
Język wykładowy:
Polski
Forma i tryb studiów:
Stacjonarne
Strona www:
 
Osoba odpowiedzialna:
prof. zw. dr hab. Wojda Adam Paweł (wojda@agh.edu.pl)
Osoby prowadzące:
dr hab. Meszka Mariusz (meszka@agh.edu.pl)
Krótka charakterystyka modułu

Opis efektów kształcenia dla modułu zajęć
Kod EKM Student, który zaliczył moduł zajęć wie/umie/potrafi Powiązania z EKK Sposób weryfikacji efektów kształcenia (forma zaliczeń)
Wiedza
M_W001 Zna i rozumie podstawowe pojęcia, twierdzenia i metody dotyczące matematyki dyskretnej IN1A_W03, IN1A_W01 Egzamin,
Kolokwium,
Odpowiedź ustna
M_W002 Potrafi ocenić trudność problemów z zakresu matematyki dyskretnej oraz zna najważniejsze nierozstrzygnięte hipotezy IN1A_W01 Egzamin,
Kolokwium,
Odpowiedź ustna
M_W003 Zna podstawowe typy zagadnień praktycznych wykorzystujących wybrane modele kombinatoryczne IN1A_W03, IN1A_W01 Egzamin,
Kolokwium,
Odpowiedź ustna
Umiejętności
M_U001 Potrafi ze zrozumieniem przedstawić poznane zagadnienia IN1A_U01 Egzamin,
Kolokwium,
Odpowiedź ustna
M_U002 Potrafi samodzielnie przeprowadzić ścisłe rozumowanie z wykorzystaniem zdobytej wiedzy IN1A_U01 Egzamin,
Kolokwium,
Odpowiedź ustna
M_U003 Potrafi wykorzystać elementy wiedzy z matematyki dyskretnej w projektowaniu i budowie systemów informatycznych IN1A_U05, IN1A_U01, IN1A_U02 Egzamin,
Kolokwium,
Odpowiedź ustna
Kompetencje społeczne
M_K001 Potrafi krytycznie ocenić stopień zrozumienia przez siebie postawionego problemu i braki elementów rozumowania IN1A_K04, IN1A_K01 Egzamin,
Odpowiedź ustna
Matryca efektów kształcenia w odniesieniu do form zajęć
Kod EKM Student, który zaliczył moduł zajęć wie/umie/potrafi Forma zajęć
Wykład
Ćwicz. aud
Ćwicz. lab
Ćw. proj.
Konw.
Zaj. sem.
Zaj. prakt
Zaj. terenowe
Zaj. warsztatowe
Inne
E-learning
Wiedza
M_W001 Zna i rozumie podstawowe pojęcia, twierdzenia i metody dotyczące matematyki dyskretnej + + - - - - - - - - -
M_W002 Potrafi ocenić trudność problemów z zakresu matematyki dyskretnej oraz zna najważniejsze nierozstrzygnięte hipotezy + + - - - - - - - - -
M_W003 Zna podstawowe typy zagadnień praktycznych wykorzystujących wybrane modele kombinatoryczne + + - - - - - - - - -
Umiejętności
M_U001 Potrafi ze zrozumieniem przedstawić poznane zagadnienia + + - - - - - - - - -
M_U002 Potrafi samodzielnie przeprowadzić ścisłe rozumowanie z wykorzystaniem zdobytej wiedzy + + - - - - - - - - -
M_U003 Potrafi wykorzystać elementy wiedzy z matematyki dyskretnej w projektowaniu i budowie systemów informatycznych + + - - - - - - - - -
Kompetencje społeczne
M_K001 Potrafi krytycznie ocenić stopień zrozumienia przez siebie postawionego problemu i braki elementów rozumowania + + - - - - - - - - -
Treść modułu zajęć (program wykładów i pozostałych zajęć)
Wykład:

  1. Wprowadzenie. Zasada pudełkowania i przykłady jej zastosowań. Elementy teorii Ramsey’a.
  2. Funkcje i rozmieszczenia. Permutacje. Metody generowania permutacji.
  3. Zbiory, podzbiory i multizbiory. Generowanie podzbiorów.
  4. Zasada włączania-wyłączania. Nieporządki.
  5. Podziały zbioru i liczby. Liczby Stirlinga.
  6. Zależności rekurencyjne. Rozwiązywanie liniowych równań rekurencyjnych o stałych współczynnikach.
  7. Funkcje tworzące; przykłady wykorzystania. Liczby Catalana.
  8. Pojęcia wstępne teorii grafów. Izomorfizm grafów. Spójność.
  9. Droga Eulera. Cykle i ścieżki Hamiltona.
  10. Grafy dwudzielne. Drzewa. Grafy planarne.
  11. Kolorowanie wierzchołków i krawędzi w grafach. Zawężenie zagadnień kolorowania do poznanych rodzin grafów.
  12. Konfiguracje kombinatoryczne. Systemy Steinera.
  13. Inne konfiguracje. Kwadraty łacińskie.
  14. Zliczanie obiektów kombinatorycznych.

Ćwiczenia audytoryjne:

Rozwiązywanie problemów dotyczących treści przekazywanych na kolejnych wykładach.

Nakład pracy studenta (bilans punktów ECTS)
Forma aktywności studenta Obciążenie studenta
Sumaryczne obciążenie pracą studenta 120 godz
Punkty ECTS za moduł 4 ECTS
Udział w wykładach 30 godz
Udział w ćwiczeniach audytoryjnych 30 godz
Samodzielne studiowanie tematyki zajęć 40 godz
Przygotowanie do zajęć 20 godz
Pozostałe informacje
Sposób obliczania oceny końcowej:

Do uzyskania pozytywnej oceny końcowej (OC) niezbędne jest uzyskanie pozytywnej oceny z egzaminu (E), przy czym warunkiem dopuszczenia do egzaminu jest pozytywna ocena zaliczenia ćwiczeń audytoryjnych (A). Ocena końcowa jest średnią ważoną obliczaną na podstawie wzoru:
OK = 0.8 * E + 0.2 * A.

Wymagania wstępne i dodatkowe:

Nie podano wymagań wstępnych lub dodatkowych.

Zalecana literatura i pomoce naukowe:
  1. W. Lipski, Kombinatoryka dla programistów, WNT 2007.
  2. J. Jaworski, Z. Palka, J. Szymański, Matematyka dyskretna dla informatyków, WN UAM, 2008.
  3. R.A. Brualdi, Introductory combinatorics 5th Edition, Prentice Hall 2010.
Publikacje naukowe osób prowadzących zajęcia związane z tematyką modułu:

Nie podano dodatkowych publikacji

Informacje dodatkowe:

Brak