Moduł oferowany także w ramach programów studiów:
Informacje ogólne:
Nazwa:
Kombinatoryka dla programistów
Tok studiów:
2015/2016
Kod:
BIT-1-605-s
Wydział:
Geologii, Geofizyki i Ochrony Środowiska
Poziom studiów:
Studia I stopnia
Specjalność:
-
Kierunek:
Informatyka Stosowana
Semestr:
6
Profil kształcenia:
Ogólnoakademicki (A)
Język wykładowy:
Polski
Forma i tryb studiów:
Stacjonarne
Strona www:
 
Osoba odpowiedzialna:
dr Onderka Zdzisław (zonderka@agh.edu.pl)
Osoby prowadzące:
dr Onderka Zdzisław (zonderka@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 Student definiuje i formułuje podstawowe własności pojęć kombinatorycznych IT1A_W01, IT1A_W04 Kolokwium
M_W002 Student objaśnia algorytmy kombinatoryczne IT1A_W01, IT1A_W08, IT1A_W09 Kolokwium,
Wykonanie ćwiczeń laboratoryjnych
M_W003 Student dobiera odpowiednie struktur danych dla algorytmów kombinatorycznych IT1A_W01, IT1A_W09 Udział w dyskusji
Umiejętności
M_U001 Student implementuje algorytm kombinatoryczny z zastosowaniem odpowiednich struktur danych IT1A_U12, IT1A_U16, IT1A_U10 Wykonanie ćwiczeń
M_U002 Student osiada umiejętność wyszukiwania i właściwego wykorzystania algorytmów kombinatorycznych w naukach o ziemii IT1A_U14, IT1A_U07, IT1A_U15 Wykonanie ćwiczeń laboratoryjnych
Kompetencje społeczne
M_K001 Student posiada umiejętność i zdolność do samokształcenia IT1A_K01 Wykonanie ćwiczeń laboratoryjnych
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 Student definiuje i formułuje podstawowe własności pojęć kombinatorycznych + - - - - - - - - - -
M_W002 Student objaśnia algorytmy kombinatoryczne + - - - - - - - - - -
M_W003 Student dobiera odpowiednie struktur danych dla algorytmów kombinatorycznych + - - - - - + - - - -
Umiejętności
M_U001 Student implementuje algorytm kombinatoryczny z zastosowaniem odpowiednich struktur danych - - - - - - + - - - -
M_U002 Student osiada umiejętność wyszukiwania i właściwego wykorzystania algorytmów kombinatorycznych w naukach o ziemii - - - - - - + - - - -
Kompetencje społeczne
M_K001 Student posiada umiejętność i zdolność do samokształcenia - - - - - - + - - - -
Treść modułu zajęć (program wykładów i pozostałych zajęć)
Wykład:

1. Podstawowe definicje i własności grafów zorientowanych i niezorientowanych
2. Problem rozmieszczenia (algorytm rozmieszczenia n obiektów w m pudełkach)
3. Permutacje: rozkład na cykle, znak permutacji, złożenie, grupa permutacji, znak permutacji, transpozycje), algorytm znajdowania znaku permutacji, algorytmy generowania permutacji,
4. Podzbiory zbioru, podzbiory k-elementowe, współczynnik dwumianowy, generowanie podzbiorów, podziały zbioru – podstawa matematyczna i algorytmy
5. Liczby Sterlinga pierwszego i drugiego rodzaju (algorytmy generowanie)
6. Podziały liczby, funkcje tworzące (algorytmy, zastosowanie do wyznaczania liczby drzew binarnych o n wierzchołkach, liczby Catalana)
7. Grafy: reprezentacje w postaci struktur danych, algorytmy przeglądania, minimalne drzewo rozpinające, droga Eulera, droga Hamiltona, graf dwuspójny

Zajęcia praktyczne:

1. Podstawowe definicje i własności grafów zorientowanych i niezorientowanych – przykłady
2. Implementacja algorytmu rozmieszczenia n obiektów w m pudełkach)
3. Permutacje: rozkład na cykle, znak permutacji, złożenie, grupa permutacji, znak permutacji, transpozycje) – przykłady, implementacja algorytmu znajdowania znaku permutacji, implementacja algorytmu generowania permutacji,
4. Podzbiory zbioru, podzbiory k-elementowe, współczynnik dwumianowy – przykłady, implementacja algorytmu generowania podzbiorów, podziały zbioru – implementacja
5. Liczby Sterlinga pierwszego i drugiego rodzaju – implementacja algorytmów
6. Implementacja algorytmów dla podziału liczby i dla funkcji tworzących z zastosowaniem do wyznaczania liczby drzew binarnych o n wierzchołkach i liczb Catalana
7. Grafy: reprezentacje w postaci struktur danych – przykłady, implementacja algorytmów: przeglądania, minimalnego drzewa rozpinającącego, drogi Eulera, drogi Hamiltona. Graf dwuspójny

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

Ocena końcowa = 100% oceny z ćwiczeń, po uzyskaniu co najmniej oceny 3.0

Wymagania wstępne i dodatkowe:

Wymagane zaliczenie kursu Analizy matematycznej, Algebry liniowej, Algorytmów i struktur danych, Programowania w języku C/C++

Zalecana literatura i pomoce naukowe:

W. Lipski, Kombinatoryka dla programistów, WNT, 2007
R.J.Wilson, Wprowadzenie do teorii grafów, Państwowe PWN 2007
K.A.Ross, Ch.R.B.Wright, Matematyka Dyskretna, PWN. 2006
V.Bryant, Aspekty kombinatoryki, WWNT, 2007

Publikacje naukowe osób prowadzących zajęcia związane z tematyką modułu:

Nie podano dodatkowych publikacji

Informacje dodatkowe:

Wymagane od studenta zaimplementowanie niektórych algorytmów kombinatorycznych omawianych na wykładzie

Zaliczenie w pierwszym terminie na podstawie zaliczonych programów + dodatkowe 2 terminy zaliczenia,

udział „praktycznych” punktów ECTS: 1
udział „teoretycznych” punktów ECTS: 1