Uniwersytet Warszawski - Centralny System Uwierzytelniania
Strona główna

Wybrane zagadnienia teorii grafów

Informacje ogólne

Kod przedmiotu: 1000-2M12WTG
Kod Erasmus / ISCED: 11.3 Kod klasyfikacyjny przedmiotu składa się z trzech do pięciu cyfr, przy czym trzy pierwsze oznaczają klasyfikację dziedziny wg. Listy kodów dziedzin obowiązującej w programie Socrates/Erasmus, czwarta (dotąd na ogół 0) – ewentualne uszczegółowienie informacji o dyscyplinie, piąta – stopień zaawansowania przedmiotu ustalony na podstawie roku studiów, dla którego przedmiot jest przeznaczony. / (0612) Database and network design and administration Kod ISCED - Międzynarodowa Standardowa Klasyfikacja Kształcenia (International Standard Classification of Education) została opracowana przez UNESCO.
Nazwa przedmiotu: Wybrane zagadnienia teorii grafów
Jednostka: Wydział Matematyki, Informatyki i Mechaniki
Grupy: Przedmioty monograficzne dla III - V roku informatyki
Przedmioty obieralne dla informatyki
Przedmioty obieralne na studiach drugiego stopnia na kierunku bioinformatyka
Strona przedmiotu: http://www.mimuw.edu.pl/~malcin/dydaktyka/2018-19/grafy/
Punkty ECTS i inne: 6.00 Podstawowe informacje o zasadach przyporządkowania punktów ECTS:
  • roczny wymiar godzinowy nakładu pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się dla danego etapu studiów wynosi 1500-1800 h, co odpowiada 60 ECTS;
  • tygodniowy wymiar godzinowy nakładu pracy studenta wynosi 45 h;
  • 1 punkt ECTS odpowiada 25-30 godzinom pracy studenta potrzebnej do osiągnięcia zakładanych efektów uczenia się;
  • tygodniowy nakład pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się pozwala uzyskać 1,5 ECTS;
  • nakład pracy potrzebny do zaliczenia przedmiotu, któremu przypisano 3 ECTS, stanowi 10% semestralnego obciążenia studenta.

zobacz reguły punktacji
Język prowadzenia: angielski
Rodzaj przedmiotu:

monograficzne

Skrócony opis:

Na wykładzie omówimy szereg zagadnień ze współczesnej teorii grafów w ujęciu klasycznym (niealgorytmicznym).

Pełny opis:

Na wykładzie omówimy szereg zagadnień ze współczesnej teorii grafów w ujęciu klasycznym, bez opisywania czy implementowania algorytmów.

1. Ekspandery. Definicja, konstrukcje, zastosowania (szkice dowodów: L=SL oraz twierdzenia PCP).

2. Teoria minorów. Tw. Robertsona-Seymoura, przykłady. Twierdzenia dekompozycyjne. Strukturalne parametry grafów (treewidth i inne).

3. Kolorowania. Metoda dischargingu. Tw. o czterech barwach. Tw. Brooksa, tw. Vizinga. Grafy doskonałe.

Literatura:

Książki:

Reinhard Diestel, Graph Theory, Springer-Verlag 2005. Wersja elektroniczna: http://diestel-graph-theory.com/GrTh.html

Bela Bollobas, Modern Graph Theory, Springer 1998.

Mike Krebs, Anthony Shaheen, Expander Families and Cayley Graphs: A Beginner's Guide, Oxford University Press, USA, 2011.

Artykuły poglądowe i materiały dydaktyczne dostępne w sieci, między innymi:

Shlomo Hoory, Nathan Linial, Avi Wigderson, Expander Graphs and Their Applications, Bulletin of AMS 2006.

http://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf

Michael A. Nielsen, Introduction to Expander Graphs, 2005.

http://www.qinfo.org/people/nielsen/blog/archive/notes/expander_graphs.pdf

Laszlo Lovasz, Graph Minor Theory, Bulletin of AMS 2005.

http://www.ams.org/bull/2006-43-01/S0273-0979-05-01088-8/S0273-0979-05-01088-8.pdf

Petr Hlineny, Discharging Technique in Practice.

http://kam.mff.cuni.cz/~kamserie/serie/clanky/2000/s475.ps

Efekty uczenia się:

Wiedza:

Ma zaawansowaną wiedzę z trzech działów na pograniczu matematyki i informatyki:

* teoria minorów i jej zastosowania w algorytmice

* ekspandery i spektralna teoria grafów

* kolorowania grafów

(K_W01, K_W02)

W szczególności, po zajęciach student jest w stanie zrozumieć zaawansowane użycie ww. technik w studiowanym materiale (np. artykule naukowym) oraz rozpoznać potrzebe użycia tych technik w własnej pracy.

Umiejętności:

* potrafi zaaplikować nowe techniki we własnej pracy badawczej (K_U01)

* potrafi korzystać z tekstów źródłowych i podręczników w języku angielskim (K_U14)

Kompetencje

* rozumie potrzebę systematycznego zapoznawania się z czasopismami naukowymi i popularnonaukowymi w celu poszerzania i pogłębiania wiedzy (K_K08).

* potrafi precyzyjnie formułować pytania, służące pogłębieniu własnego zrozumienia danego tematu lub odnalezieniu brakujących elementów rozumowania (K_K02).

Metody i kryteria oceniania:

Będą 3 serie prac domowy, po 4 zadania każda, na podstawie których będzie wyznaczony modyfikator do oceny z egzaminu z przedziału [-1,+1.5]. Dodatkowo, po każdym wykładzie będzie do rozwiązania krótki test przez Moodle; zaliczenie wszystkich testów w terminie jest warunkiem dopuszczenia do egzaminu w pierwszym terminie. Egzamin ustny, na ocenę.

Przedmiot można zaliczać w ramach studiów doktoranckich jako przedmiot "metodologiczny"; wówczas dodatkowym warunkiem zaliczenia jest rozwiązanie co najmniej jednego najtrudniejszego (ostatniego) zadania z jednej z serii prac domowych.

Zajęcia w cyklu "Semestr letni 2022/23" (jeszcze nie rozpoczęty)

Okres: 2023-02-20 - 2023-06-18

Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć:
Ćwiczenia, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Michał Pilipczuk
Prowadzący grup: Michał Pilipczuk, Marek Sokołowski
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Warszawski.
ul. Banacha 2
02-097 Warszawa
tel: +48 22 55 44 214 https://www.mimuw.edu.pl/
kontakt deklaracja dostępności USOSweb 6.8.0.0-2a4334331 (2022-08-26)