Cel kształcenia i wykaz literatury

Główny cel kształcenia: Głównym celem kształcenia, w ramach tego przedmiotu, jest zapoznanie studentów z wybranymi algorytmami generowania, wszystkich lub z pewnymi ograniczeniami, typowych obiektów kombinatorycznych.

Ogólne informacje o zajęciach: W ramach tego modułu kształcenia studentom zostaną przedstawione algorytmy z obszaru szeroko pojętej kombinatoryki, wraz z ich praktycznymi implementacjami. Umiejętność generowania wszystkich obiektów kombinatorycznych danego rodzaju może pomóc rozwiązać jakiś problem poprzez przeglądnięcie wszystkich możliwych rozwiązań i wybranie najlepszego. W ten sposób można wyznaczyć dokładną, optymalną wartość zadanej funkcji celu, jeżeli tylko liczba obiektów kombinatorycznych do wygenerowania i przejrzenia nie jest zbyt duża.

Wykaz literatury, wymaganej do zaliczenia zajęć

Literatura wykorzystywana podczas zajęć wykładowych

1	T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein	Wprowadzenie do algorytmów	Wydawnictwo Naukowe PWN.	2012
2	A.V. Aho,J.E. Hopcroft, J.D. Ullman	Projektowanie i analiza algorytmów	Wydawnictwo Helion.	2003.
3	E. Donald Knuth	Sztuka programowania Tom 4. Zeszyt 2. Generowanie wszystkich krotek i permutacji Gandalf.com.pl	WNT.

Literatura wykorzystywana podczas zajęć ćwiczeniowych/laboratoryjnych/innych

1	Antoni Szczepański	Biblioteka kombinatoryczno-grafowa dla programu Maxima	opracowanie własne.	2022
2	Antoni Szczepański	Pliki tekstowe z komputerowo wygenerowanymi obiektami kombinatorycznymi	Opracowanie własne.	2016

Literatura do samodzielnego studiowania

1

W. Lipski

Kombinatoryka dla programistów

WNT.

2007

Wymagania wstępne w kategorii wiedzy/umiejętności/kompetencji społecznych

Wymagania formalne: wpis na trzeci semestr studiów inżynierskich na kierunku Informatyka

Wymagania wstępne w kategorii Wiedzy: Posiada wiedzę na temat podstawowych obiektów kombinatorycznych. Potrafi je rozróżniać i zna zależności matematyczne określające liczbę takich obiektów.

Wymagania wstępne w kategorii Umiejętności: Student powinien posiadać umiejętność algorytmicznego i kombinatorycznego myślenia. Może przydać się znajomość języka programowania Python.

Wymagania wstępne w kategorii Kompetencji społecznych: Wytrwałość w dążeniu do celu. Pracowitość i systematyczność.

Efekty kształcenia dla zajęć

MEK	Student, który zaliczył zajęcia	Formy zajęć/metody dydaktyczne prowadzące do osiągnięcia danego efektu kształcenia	Metody weryfikacji każdego z wymienionych efektów kształcenia	Związki z KEK	Związki z PRK
01	zna wybrane algorytmy generowania permutacji, kombinacji, wariacji, bez powtórzeń i z powtórzeniami, bez ograniczeń i z ograniczeniami.	wykład, laboratorium	raport pisemny	K_W01+ K_U01+ K_U02+ K_K07+	P6S_KO P6S_UW P6S_WG
02	zna algorytmy generowania podziałów liczby, w porządku leksykograficznym i antylesykograficznym	wykład, laboratorium	raport pisemny	K_W01+ K_U01+ K_U02+ K_K07+	P6S_KO P6S_UW P6S_WG
03	zna algorytmy generowania podziałów zbioru, nieuporządkowanych i uporządkowanych	wykład, laboratorium	raport pisemny	K_W01+ K_U01+ K_U02+ K_K07+	P6S_KO P6S_UW P6S_WG
04	zna algorytmy generowania wszystkich ciągów iloczynu kartezjańskiego oraz wszystkich systemów reprezentantów ciągu podzbiorów	wykład, laboratorium	raport pisemny	K_W01+ K_U01+ K_U02+ K_K07+	P6S_KO P6S_UW P6S_WG
05	zna zwyczajną i wykładniczą funkcje tworzące jako matematyczne narzędzia badania ciągów liczbowych	wykład, laboratorium	raport pisemny	K_W01+ K_U01+ K_U02+ K_K07+	P6S_KO P6S_UW P6S_WG

Uwaga: W zależności od sytuacji epidemicznej, jeżeli nie będzie możliwości weryfikacji osiągniętych efektów uczenia się określonych w programie studiów w sposób stacjonarny w szczególności zaliczenia i egzaminy kończące określone zajęcia będą mogły się odbywać przy użyciu środków komunikacji elektronicznej (w sposób zdalny).

Treści kształcenia dla zajęć

Sem.	TK	Treści kształcenia	Realizowane na	MEK
3	TK01	Definicje podstawowych obiektów kombinatorycznych oraz wzory na wyznaczanie ich liczby. Permutacje bez powtórzeń i z powtórzeniami. Kombinacje bez powtórzeń i z powtórzeniami. Wariacje bez powtórzeń i z powtórzeniami. Liczby Stirlinga I i II rodzaju.	W1, L1	MEK01
3	TK02	Generowanie wszystkich permutacji bez powtórzeń w porządku leksykograficznym i antyleksykograficznym. Generowanie wszystkich permutacji przez minimalną liczbę transpozycji oraz minimalną liczbę transpozycji sąsiednich elementów. Generowanie permutacji z powtórzeniami. Generowanie losowej permutacji. Generowanie permutacji danego typu, tzn. o zadanym układzie cykli (np. tylko inwolucji albo tylko nieporządków). Generowanie permutacji z ograniczeniami na występowanie liczb na danych pozycjach.	W2, L2	MEK01
3	TK03	Generowanie wszystkich podzbiorów zbioru n-elementowego, wg kodu Graya oraz wg naturalnego kodu binarnego. Generowanie podzbiorów k-elementowych. Generowanie podzbiorów zbioru z powtórzeniami (generowanie kombinacji z powtórzeniami).	W3, L3	MEK01
3	TK04	Generowanie wszystkich podziałów liczby. Generowanie podziałów liczby na k składników albo o składnikach mniejszych od ustalonej wartości. Generowanie kompozycji liczby. Kompozycje silne i słabe.	W4, L4	MEK02
3	TK05	Generowanie podziałów zbioru na rozłączne podzbiory (na bloki) - podziały nieuporządkowane. Ciągi o ograniczonym wzroście. Generowanie podziałów zbioru o danym typie oraz podziałów na ustaloną liczbę bloków. Generowanie podziałów uporządkowanych. Generowanie wszystkich rozwiązań równania diofantycznego x1+x2+..xk = n.	W5, L5	MEK03
3	TK06	Generowanie ciągów binarnych o ustalonej liczbie zer i jedynek. Generowanie ciągów binarnych Fibonacciego oraz Catallana. Generowanie ciągów iloczynu kartezjańskiego oraz wszystkich transversal.	W6, L6	MEK04
3	TK07	Wykładnicza i zwyczajna funkcje tworzące. Zastosowania tych funkcji do zagadnień zliczania obiektów kombinatorycznych.	W7	MEK05

Nakład pracy studenta

Forma zajęć	Praca przed zajęciami	Udział w zajęciach	Praca po zajęciach
Wykład (sem. 3)		Godziny kontaktowe: 15.00 godz./sem.	Studiowanie zalecanej literatury: 7.00 godz./sem.
Laboratorium (sem. 3)		Godziny kontaktowe: 15.00 godz./sem.	Dokończenia/wykonanie sprawozdania: 15.00 godz./sem.
Konsultacje (sem. 3)
Zaliczenie (sem. 3)

Sposób wystawiania ocen składowych zajęć i oceny końcowej

Forma zajęć	Sposób wystawiania oceny podsumowującej
Wykład	Na podstawie sprawdzianu zaliczeniowego na wykładzie.
Laboratorium	na podstawie sprawozdań oraz kilku krótkich sprawdzianów
Ocena końcowa	średnia arytmetyczna dwóch ocen: końcowej z laboratoriów oraz końcowej z wykładów; przy czym obie muszą być co najmniej równe 3,0.

Przykładowe zadania

Wymagane podczas egzaminu/zaliczenia
(-)

Realizowane podczas zajęć ćwiczeniowych/laboratoryjnych/projektowych
(-)

Inne
(-)

Czy podczas egzaminu/zaliczenia student ma możliwość korzystania z materiałów pomocniczych : tak

Dostępne materiały : Notatki z wykładów i z laboratoriów.

Treści zajęć powiazane są z prowadzonymi badaniami naukowymi: nie