Serwisy internetowe Uniwersytetu Warszawskiego | USOSownia - uniwersyteckie forum USOSoweNie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

Grafy rzadkie

Informacje ogólne

Kod przedmiotu: 1000-2M12GRZ Kod Erasmus / ISCED: 11.3 / (0612) Database and network design and administration
Nazwa przedmiotu: Grafy rzadkie
Jednostka: Wydział Matematyki, Informatyki i Mechaniki
Grupy: Przedmioty monograficzne dla III - V roku informatyki
Przedmioty obieralne dla informatyki
Punkty ECTS i inne: 6.00
zobacz reguły punktacji
Język prowadzenia: angielski
Rodzaj przedmiotu:

monograficzne

Wymagania (lista przedmiotów):

Matematyka dyskretna 1000-212bMD

Założenia (opisowo):

Zaliczenie przedmiotów Algorytmika, Złożoność Obliczeniowa, oraz Logika dla Informatyków, będzie pomocna w niektórych częściach materiału, ale nie jest wymagana. Materiał ma małe przecięcie (ok. 1 wykładu) z przedmiotem Meta-algorytmy na Grafach, prowadzonym w semestrze letnim 2016/2017. Przecięcie dotyczy najbardziej podstawowych technik teorii grafów rzadkich.


Skrócony opis:

Przedmiot obejmuje wprowadzenie do teorii grafów rzadkich, dziedziny badawczej w teorii grafów. Materiał będzie obejmował kombinatoryczne własności abstrakcyjnych pojęć rzadkości, takich jak klasy o ograniczonej ekspansji i klasy nigdzie-gęste, a także szereg powiązań teorii z algorytmiką, teorią grafów ekstremalnych, oraz teorią modeli.

Uwaga: Przedmiot prowadzony w języku angielskim.

Pełny opis:

1. Mierzenie rzadkości, definicje klas o ograniczonej ekspansji i nigdzie-gęstych, relacje pomiędzy płytkimi minorami i płytkimi topologicznymi minorami (2-3 wykłady).

2. Quasi-szerokość i gra Splitter Game (1-2 wykłady)

3. Uogólnione liczby chromatyczne: kombinatoryka, aspekty algorytmiczne, zastosowania (2 wykłady).

4. Kolorowania o małej głębokości drzewiastej: kombinatoryka i zastosowania (1 wykład)

5. Złożoność sąsiedztw (1 wykład)

6. Zastosowania algorytmiczne dla złożoności parametryzowanej (2 wykłady)

7. Wielomianowa ekspansja i separatory: zastosowania dla algorytmów aproksymacyjnych (1-2 wykłady)

8. Zastosowania teorii stabilności (2 wykłady)

9. Nieskończone grafy rzadkie, ultraprodukty klas rzadkich (1 wykład)

Literatura:

J. Nešetřil, P. Ossona de Mendez, “Sparsity - Graphs, Structures, and Algorithms”.

Notatki z poprzedniej edycji przedmiotu.

Notatki i artykuły badawcze wskazane przez wykładowców.

Efekty kształcenia:

Wiedza:

Zna różne, równoważne definicje rzadkości grafów: klas o ograniczonej ekspansji oraz nigdzie-gęstych, rozumie związki pomiędzy tymi definicjami. Potrafi wskazać przykładowe zastosowania teorii grafów rzadkich ze szczególnym uwzględnieniem zastosowań w projektowaniu algorytmów parametryzowanych oraz aproksymacyjnych. (K_W01, K_W02)

Umiejętności:

Potrafi zastosować poznane własności kombinatoryczne pojęć rzadkości do rozwiązywania problemów matematycznych oraz algorytmicznych, również pojawiających się w pracy naukowej. (K_U02, K_U09)

Kompetencje:

Zna ograniczenia własnej wiedzy i rozumie potrzebę dalszego kształcenia, w tym zdobywania wiedzy pozadziedzinowej (K_K01). Potrafi precyzyjnie formułować pytania, służące pogłębieniu własnego zrozumienia danego tematu lub odnalezieniu brakujących elementów rozumowania (K_K02). Rozumie potrzebę systematycznego zapoznawania się z czasopismami naukowymi i popularnonaukowymi w celu poszerzania i pogłębiania wiedzy (K_K08).

Metody i kryteria oceniania:

Prace domowe (50%) oraz egzamin ustny (50%)

Zajęcia w cyklu "Semestr zimowy 2017/18" (zakończony)

Okres: 2017-10-01 - 2018-01-26
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 30 godzin więcej informacji
Wykład monograficzny, 30 godzin więcej informacji
Koordynatorzy: Michał Pilipczuk
Prowadzący grup: Michał Pilipczuk, Sebastian Siebertz
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Wymagania (lista przedmiotów):

Matematyka dyskretna 1000-212bMD

Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Warszawski.