Wierk - Wydział Informatyki, Elektroniczne Ramy Kwalifikacji

Wydział Informatyki
Kierunek studiów	Informatyka							Poziom i forma studiów	pierwszego stopnia inżynierskie stacjonarne
Specjalność / Ścieżka dyplomowania	---							Profil kształcenia	ogólnoakademicki
Nazwa przedmiotu	Teoria grafów							Kod przedmiotu	INF1TGR
								Rodzaj przedmiotu	obieralny
Forma zajęć i liczba godzin	W	Ć	L	P	Ps	T	S	Semestr	5
	26	30						Punkty ECTS	5
Przedmioty wprowadzające	Algebra liniowa z geometrią analityczną (INF1ALG), Matematyka dyskretna (INF1MDY),
Cele przedmiotu	Wprowadzenie do teorii grafów ze szczególnym uwzględnieniem: elementów algebraicznej teorii grafów, ekstremalnej teorii grafów, zagadnień kolorowania oraz zastosowań teorii grafów. Zapoznanie studentów z najważniejszymi rezultatami z historii teorii grafów oraz wybranymi nierozstrzygniętymi problemami.
Treści programowe	Wykład: 1. Podstawowe pojęcia teorii grafów 2. Charakteryzacje grafów eulerowskich i hamiltonowskich 3. Planarność i zagadnienia kolorowania w teorii grafów 4. Drzewa spinające grafów 5. Twierdzenie Kirhoffa i różne dowody twierdzenia Cayleya o drzewach spinających grafu pełnego 6. Metody algebraiczne w statystyce i ekonomii 7. Metody algebraiczne: kliki w grafach,zbiory niezależne, wyznaczniki i drogi w grafach skierowanych, wzór Gessela-Viennota 8. Metody algebraiczne: kliki w grafach,zbiory niezależne, wyznaczniki i drogi w grafach skierowanych (cd) 9. Elementy ekstremalnej teorii grafów: grafy bez cykli długości 3 i 4 10. Elementy ekstremalnej teorii grafów(cd): twierdzenie Turana 11. Grafy silnie regularne 12. Spektra grafów 13. Zaliczenie wykładu Pracownia specjalistyczna: 1. Podstawowe pojęcia teorii grafów 2. Charakteryzacje grafów eulerowskich i hamiltonowskich 3. Planarność i zagadnienia kolorowania w teorii grafów 4. Drzewa spinające grafów 5. Twierdzenie Kirhoffa i różne dowody twierdzenia Cayleya o drzewach spinających grafu pełnego 6. Metody algebraiczne w statystyce i ekonomii 7. Metody algebraiczne: kliki w grafach,zbiory niezależne, wyznaczniki i drogi w grafach skierowanych 8. Metody algebraiczne: kliki w grafach,zbiory niezależne, wyznaczniki i drogi w grafach skierowanych (cd) 9. Elementy ekstremalnej teorii grafów: grafy bez cykli długości 3 i 4 10. Elementy ekstremalnej teorii grafów(cd): twierdzenie Turana 11. Grafy silnie regularne 12. Grafy silnie regularne (cd) 13. Spektra grafów 14. Spektra grafów 15. Podsumowanie i zaliczenie pracowni specjalistycznej
Metody dydaktyczne	wykład problemowy, wykład informacyjny,
Forma zaliczenia	Wykład: zaliczenie pisemne Pracownia specjalistyczna: zaliczenie na podstawie projektów lub zadań wykonanych w ramach pracowni
Symbol efektu uczenia się	Zakładane efekty uczenia się								Odniesienie do kierunkowych efektów uczenia się
EU1	pojęcia i twierdzenia z zakresu teorii grafów wykorzystywane w jej zastosowaniach								INF1_W01 INF1_W14
EU2	istotę metod teorii grafów omówionych na zajęciach, zna zastosowania tych metod								INF1_W01 INF1_W14
EU3	wykonywać obliczenia korzystając z odpowiednich narzędzi informatycznych								INF1_U01 INF1_U13
EU4	prezentować wyniki wykonanych zadań lub projektów								INF1_U01 INF1_U13
Symbol efektu uczenia się	Sposób weryfikacji efektu uczenia się								Forma zajęć na której zachodzi weryfikacja
EU1	zaliczenie pisemne								W
EU2	zaliczenie pisemne								W
EU3	kontrola pracy na zajęciach, ocena projektów lub zadań								Ps
EU4	ocena projektów lub zadań wykonywanych w ramach pracowni Ps								Ps
Bilans nakładu pracy studenta (w godzinach)									Liczba godz.
Wyliczenie
	1 - Udział w wykładach								26
	2 - Udział w pracowni specjalistycznej								30
	3 - Przygotowanie do pracowni specjalistycznej								45
	4 - Konsultacje								4
	5 - Przygotowanie do zaliczenia wykładu								20
RAZEM:									125
Wskaźniki ilościowe									GODZINY	ECTS
Nakład pracy studenta związany z zajęciami wymagającymi bezpośredniego udziału nauczyciela									60 (1)+(2)+(4)	2.4
Nakład pracy studenta związany z zajęciami o charakterze praktycznym									95 (2)+(3)+(5)	3.8
Literatura podstawowa	1. R. J. Wilson, Wprowadzenie do teorii grafów, PWN, Warszawa 2000. 2. V. Bryant, Aspekty kombinatoryki, Wydawnictwo Naukowo-Techniczne, Warszawa 1997. 3. R. Diestel, Graph Theory, Springer-Verlag, New York 2010. 4. W. Lipski, Kombinatoryka dla programistów, Wydawnictwo Naukowo-Techniczne, Warszawa 2004. 5. M. Aigner, G. M. Ziegler, Dowody z Księgi, Wydawnictwo Naukowe PWN, Warszawa 2004.
Literatura uzupełniająca	1. R. L. Graham, D. E. Knuth, O. Patashnik, Matematyka konkretna, Wydawnictwo Naukowe PWN, Warszawa 1998. 2. K. A. Ross, C. R. Wright, Matematyka dyskretna, Wydawnictwo Naukowe PWN, Warszawa 2001.
Jednostka realizująca	Katedra Informatyki Teoretycznej								Data opracowania programu
Program opracował(a)	prof. dr hab. Piotr Grzeszczuk								2025.02.23