logo
Karta przedmiotu
logo

Optymalizacja dyskretna

Podstawowe informacje o zajęciach

Cykl kształcenia: 2021/2022

Nazwa jednostki prowadzącej studia: Wydział Matematyki i Fizyki Stosowanej (p.prakt)

Nazwa kierunku studiów: Inżynieria i analiza danych

Obszar kształcenia: nauki ścisłe

Profil studiów: praktyczny

Poziom studiów: pierwszego stopnia

Forma studiów: stacjonarne

Specjalności na kierunku: inżynieria i analiza danych

Tytuł otrzymywany po ukończeniu studiów: inżynier

Nazwa jednostki prowadzącej zajęcia: Zakład Matematyki Dyskretnej

Kod zajęć: 12330

Status zajęć: obowiązkowy dla programu inżynieria i analiza danych

Układ zajęć w planie studiów: sem: 4 / W15 P15 / 2 ECTS / Z

Język wykładowy: polski

Imię i nazwisko koordynatora: dr Paweł Bednarz

Terminy konsultacji koordynatora: https://pawelbednarz.v.prz.edu.pl/konsultacje

semestr 4: mgr Adrian Michalski , termin konsultacji https://amichalski.v.prz.edu.pl/konsultacje

Cel kształcenia i wykaz literatury

Główny cel kształcenia: Celem kształcenia jest zapoznanie studentów z metodami optymalizacji dyskretnej i zastosowaniami tych metod do analizy danych.

Ogólne informacje o zajęciach: Moduł obejmuje przegląd algorytmów dokładnych i przybliżonych stosowanych w optymalizacji dyskretnej.

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 K. Ross, Ch. Wright Matematyka dyskretna PWN, Warszawa. 2012
2 R. J. Wilson Wprowadzenie do teorii grafów PWN, Warszawa. 2012
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 teorii grafów i matematyki dyskretnej.

Wymagania wstępne w kategorii Umiejętności: Potrafi zaimplementować algorytm w wybranym języku programowania.

Wymagania wstępne w kategorii Kompetencji społecznych: Umiejętność pracy w grupie.

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, projekt wykonanie projektu zespołowego, zaliczenie praktyczne przy komputerze K_W01+
K_W02+
K_W03+
K_U02+
K_U03+
K_K01+
K_K02+
K_K05+
P6S_KK
P6S_KO
P6S_UW
P6S_WG
02 Potrafi sformułować zagadnienie inżynierskie jako zagadnienie matematyki dyskretnej. wykład, projekt wykonanie projektu zespołowego, zaliczenie praktyczne przy komputerze K_W01+
K_W02+
K_W03+
K_U02+
K_U03+
K_K01+
K_K02+
K_K05+
P6S_KK
P6S_KO
P6S_UW
P6S_WG
03 Potrafi zbudować model problemu i rozwiązać problem przy pomocy metod optymalizacji dyskretnej. wykład, projekt wykonanie projektu zespołowego, zaliczenie praktyczne przy komputerze K_W01+
K_W02+
K_W03+
K_U02+
K_U03+
K_K01+
K_K02+
K_K05+
P6S_KK
P6S_KO
P6S_UW
P6S_WG
04 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, projekt wykonanie projektu zespołowego, zaliczenie praktyczne przy komputerze K_W01+
K_W02+
K_W03+
K_U02+
K_U03+
K_K01+
K_K02+
K_K05+
P6S_KK
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
4 TK01 Upakowania i pokrycia. Zagadnienie plecakowe. Postacie zagadnienia i jego zastosowania. Algorytm redukcji. Metody dokładne. Algorytmy przybliżone. Zastosowania. W1-W2, MEK01 MEK02 MEK03 MEK04
4 TK02 Zagadnienia pokrycia. Postacie zagadnienia i jego zastosowania. Algorytmy redukcji. Metoda przeglądu pośredniego dla zagadnienia rozbicia zbioru. Zastosowania. W3-W4, MEK01 MEK02 MEK03 MEK04
4 TK03 Optymalizacja na sieciach. Komputerowa reprezentacja sieci. Problemy najkrótszych dróg. Problem minimalnego drzewa rozpinającego. Zastosowania. W5-W6, MEK01 MEK02 MEK03 MEK04
4 TK04 Problem maksymalnego przepływu w sieci. Problem najtańszego przepływu. Zastosowania. W7-W8, MEK01 MEK02 MEK03 MEK04
4 TK05 Najliczniejsze skojarzenie. Zastosowania. W9-W10, MEK01 MEK02 MEK03 MEK04
4 TK06 Problem komiwojażera. Algorytmy podziału i ograniczeń. Algorytmy przybliżone. Zastosowania. W11-W12, MEK01 MEK02 MEK03 MEK04
4 TK07 Kolorowanie i szeregowanie. Zastosowania. W13-W15, MEK01 MEK02 MEK03 MEK04
4 TK08 Wykonanie projektu w zespołach dwuosobowych. Tematyka projektów związana z tematyką wykładów podana na pierwszych zajęciach do wyboru przez studentów. Na projekt składa się: opis problemu, algorytm (pseudokod), skrypt wykonywalny, wyniki i dokumentacja użytkownika. P1-P15 MEK01 MEK02 MEK03 MEK04

Nakład pracy studenta

Forma zajęć Praca przed zajęciami Udział w zajęciach Praca po zajęciach
Wykład (sem. 4) Przygotowanie do kolokwium: 5.00 godz./sem.
Godziny kontaktowe: 15.00 godz./sem.
Projekt/Seminarium (sem. 4) Przygotowanie do zajęć projektowych/seminaryjnych: 10.00 godz./sem.
Godziny kontaktowe: 15.00 godz./sem..
Konsultacje (sem. 4)
Zaliczenie (sem. 4)

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.
Projekt/Seminarium Warunkiem zaliczenia jest uzyskanie w sumie co najmniej 50% punktów z projektu (36 pkt) oraz testu z wykładu (24 pkt).
Ocena końcowa Ocena końcowa jest oceną z zajęć projektowych.

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 : nie

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