Cel kształcenia i wykaz literatury

Główny cel kształcenia: Zapoznanie studentów z wybranymi metodami optymalizacji dyskretnej

Ogólne informacje o zajęciach: Tematyka zajęć została wybrana przez studentów.

Wykaz literatury, wymaganej do zaliczenia zajęć

Literatura wykorzystywana podczas zajęć wykładowych

1	M.Kubale (red)	Optymalizacja dyskretna. Modele i metody kolorowania grafów	PWN Warszawa.	2002
2	M. Sysło, N. Deo, J. Kowalik	Algorytmy optymalizacji dyskretnej	PWN, Warszawa.	1999
3	A. Włoch, I. Włoch	Matematyka dyskretna- podstawowe metody i algorytmy teorii grafów	Oficyna Wydawnicza Politechniki Rzeszowskiej, Rzeszów.	2004
4	N. Deo	Teoria grafów i jej zastosowania w technice i informatyce	PWN, Warszawa.	1980

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

1

R.J. Wilson

Wprowadzenie do teorii grafów

PWN, Warszawa.

2000

Literatura do samodzielnego studiowania

1

R. Diestel

Graph Theory

Springer-Verlag, Heidelberg New York.

2005

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

Wymagania formalne: Student spełnia wymagania formalne określone w regulaminie studiów

Wymagania wstępne w kategorii Wiedzy: Znajomość podstaw matematyki dyskretnej, kombinatoryki i teorii liczb

Wymagania wstępne w kategorii Umiejętności: Student zna, rozumie i potrafi stosować pojęcia z zakresu matematyki dyskretnej.

Wymagania wstępne w kategorii Kompetencji społecznych: Student posiada umiejętność samodzielnego i zespołowego uczenia się, ma świadomość poziomu własnej wiedzy oraz rozumie potrzebę samokształcenia.

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 podstawowe metody optymalizacji dyskretnej.	wykład, ćwiczenia	zaliczenie cz. pisemna, wykonanie projektu zespołowego	K_W01+ K_W02++ K_W03+ K_W04+ K_W05+ K_W06+ K_U01+ K_K01+	P6S_KK P6S_UK P6S_WG P6S_WK
02	Potrafi zbudować model problemu i rozwiązać problem przy pomocy metod optymalizacji dyskretnej.	wykład, ćwiczenia	zaliczenie cz. pisemna, wykonanie projektu zespołowego	K_W02+ K_W03+ K_W04+ K_W05+ K_W06+ K_U01+ K_K01+	P6S_KK P6S_UK P6S_WG P6S_WK
03	Potrafi używać algorytmów dokładnych i przybliżonych do wykonywania obliczeń, generowania obiektów kombinatorycznych lub tworzenia modelu w stopniu podstawowym.	wykład, ćwiczenia	zaliczenie cz. pisemna, wykonanie projektu zespołowego	K_W01+ K_W04+ K_W05+ K_K01+	P6S_KK P6S_WG P6S_WK

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
5	TK01	Przypomnienie podstawowych definicji i twierdzeń teorii grafów. Wprowadzenie do teorii digrafów. Digrafy ważone. Metody przeszukiwania grafów. Przeszukiwanie wszerz (BFS) przeszukiwanie w głąb (DFS). Zagadnienie plecakowe. Problem pokrycia zbioru. Problemy najkrótszych dróg. Problem minimalnego drzewa rozpinającego. Problem maksymalnego przepływu w sieci. Problem najtańszego przepływu. Problem komiwojażera. Algorytmy podziału i ograniczeń. Kolorowanie grafów. Szeregowanie zadań. Problem chińskiego listonosza, wyznaczanie maksymalnego skojarzenia w grafie dwudzielnym.	W01-W30, C01-C15	MEK01 MEK02 MEK03

Nakład pracy studenta

Forma zajęć	Praca przed zajęciami	Udział w zajęciach	Praca po zajęciach
Wykład (sem. 5)		Godziny kontaktowe: 30.00 godz./sem.	Uzupełnienie/studiowanie notatek: 6.00 godz./sem.
Ćwiczenia/Lektorat (sem. 5)	Przygotowanie do ćwiczeń: 15.00 godz./sem.	Godziny kontaktowe: 15.00 godz./sem.
Konsultacje (sem. 5)	Przygotowanie do konsultacji: 6.00 godz./sem.	Udział w konsultacjach: 3.00 godz./sem.
Zaliczenie (sem. 5)

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

Forma zajęć	Sposób wystawiania oceny podsumowującej
Wykład	Zaliczenia wykładu dokonuje się na podstawie obecności na wykładach.
Ćwiczenia/Lektorat	Warunkiem zaliczenia ćwiczeń jest uzyskanie co najmniej 50 punktów. Punkty można zdobyć za: - kolokwium (48pkt), - przedstawienie (maksymalnie 7) prezentacji wybranych zagadnień optymalizacyjnych w grupach co najwyżej dwuosobowych (do 10pkt za wykonanie samych obliczeń do konkretnego problemu, do 25pkt za napisanie programu/skyptu w matlabie) - dodatkowe aktywności (do 10pkt każda)
Ocena końcowa	Ocena końcowa jest oceną z ćwiczeń.

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 : Dwie kartki A4 zapisane dowolną treścią.

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

1	P. Bednarz; M. Pirga	On Proper 2-Dominating Sets in Graphs	2024
2	P. Bednarz	Relations between the existence of a (2 − d)-kernel and parameters γ2(G), α(G)	2022
3	P. Bednarz	On (2-d)-Kernels in the Tensor Product of Graphs	2021
4	P. Bednarz; A. Michalski	On Independent Secondary Dominating Sets in Generalized Graph Products	2021
5	P. Bednarz; N. Paja	On (2-d)-Kernels in Two Generalizations of the Petersen Graph	2021