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 systematycznego 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ć za pomocą komputera jakiś problem brute-force'owo, tzn. 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.

Inne: http://www2.denizyuret.com/bib/kreher/donald1999combinatorial/combinatorialA.pdf

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: wiedza na temat definicji podstawowych obiektów kombinatorycznych; umiejętność ich rozróżniania i znajomość zależności matematycznych określających liczbę takich obiektów

Wymagania wstępne w kategorii Umiejętności: Student powinien posiadać umiejętność algorytmicznego i kombinatorycznego myślenia. Powinien również znać praktycznie język programowania Python, przynajmniej na poziomie podstawowym.

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 antyleksykograficznym	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

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. Generowanie wszystkich permutacji bez powtórzeń w porządku leksykograficznym i antyleksykograficznym. Generowanie wszystkich permutacji przez minimalna 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).	W1, L1	MEK01
3	TK02	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).	W2, L2	MEK01
3	TK03	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.	W3, L3	MEK02
3	TK04	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.	W4, L4	MEK03
3	TK05	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 reprezentantów ciągu podzbiorów, czyli transversal.	W5, L5	MEK04

Nakład pracy studenta

Forma zajęć	Praca przed zajęciami	Udział w zajęciach	Praca po zajęciach
Wykład (sem. 3)	Przygotowanie do kolokwium: 10.00 godz./sem.	Godziny kontaktowe: 10.00 godz./sem.	Uzupełnienie/studiowanie notatek: 5.00 godz./sem. Studiowanie zalecanej literatury: 10.00 godz./sem.
Laboratorium (sem. 3)	Przygotowanie do laboratorium: 10.00 godz./sem.	Godziny kontaktowe: 10.00 godz./sem.	Dokończenia/wykonanie sprawozdania: 20.00 godz./sem.
Konsultacje (sem. 3)		Udział w konsultacjach: 1.00 godz./sem.
Zaliczenie (sem. 3)	Przygotowanie do zaliczenia: 5.00 godz./sem.	Zaliczenie pisemne: 2.00 godz./sem.

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ń.
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 : z notatek sporządzonych w ramach wykładów oraz z własnych sprawozdań

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