Module also offered within study programmes:
General information:
Name:
Kombinatoryka dla programistów (Combinatorics for Software Developer)
Course of study:
2015/2016
Code:
BIT-1-605-s
Faculty of:
Geology, Geophysics and Environmental Protection
Study level:
First-cycle studies
Specialty:
-
Field of study:
Applied Computer Science
Semester:
6
Profile of education:
Academic (A)
Lecture language:
Polish
Form and type of study:
Full-time studies
Course homepage:
 
Responsible teacher:
dr Onderka Zdzisław (zonderka@agh.edu.pl)
Academic teachers:
dr Onderka Zdzisław (zonderka@agh.edu.pl)
Module summary

Description of learning outcomes for module
MLO code Student after module completion has the knowledge/ knows how to/is able to Connections with FLO Method of learning outcomes verification (form of completion)
Social competence
M_K001 Student posiada umiejętność i zdolność do samokształcenia IT1A_K01 Execution of laboratory classes
Skills
M_U001 Student implementuje algorytm kombinatoryczny z zastosowaniem odpowiednich struktur danych IT1A_U12, IT1A_U16, IT1A_U10 Execution of exercises
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 Execution of laboratory classes
Knowledge
M_W001 Student definiuje i formułuje podstawowe własności pojęć kombinatorycznych IT1A_W01, IT1A_W04 Test
M_W002 Student objaśnia algorytmy kombinatoryczne IT1A_W01, IT1A_W08, IT1A_W09 Test,
Execution of laboratory classes
M_W003 Student dobiera odpowiednie struktur danych dla algorytmów kombinatorycznych IT1A_W01, IT1A_W09 Participation in a discussion
FLO matrix in relation to forms of classes
MLO code Student after module completion has the knowledge/ knows how to/is able to Form of classes
Lecture
Audit. classes
Lab. classes
Project classes
Conv. seminar
Seminar classes
Pract. classes
Zaj. terenowe
Zaj. warsztatowe
Others
E-learning
Social competence
M_K001 Student posiada umiejętność i zdolność do samokształcenia - - - - - - + - - - -
Skills
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 - - - - - - + - - - -
Knowledge
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 + - - - - - + - - - -
Module content
Lectures:

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

Practical classes:

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

Student workload (ECTS credits balance)
Student activity form Student workload
Summary student workload 80 h
Module ECTS credits 3 ECTS
Participation in lectures 15 h
Realization of independently performed tasks 20 h
Participation in practical classes 30 h
Preparation for classes 15 h
Additional information
Method of calculating the final grade:

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

Prerequisites and additional requirements:

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

Recommended literature and teaching resources:

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

Scientific publications of module course instructors related to the topic of the module:

Additional scientific publications not specified

Additional information:

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