Grafy rzadkie
Informacje ogólne
Kod przedmiotu: | 1000-2M12GRZ |
Kod Erasmus / ISCED: |
11.3
|
Nazwa przedmiotu: | Grafy rzadkie |
Jednostka: | Wydział Matematyki, Informatyki i Mechaniki |
Grupy: |
Przedmioty obieralne dla informatyki Przedmioty obieralne na studiach drugiego stopnia na kierunku bioinformatyka |
Strona przedmiotu: | https://www.mimuw.edu.pl/~mp248287/sparsity2/ |
Punkty ECTS i inne: |
6.00
|
Język prowadzenia: | angielski |
Rodzaj przedmiotu: | monograficzne |
Wymagania (lista przedmiotów): | Matematyka dyskretna 1000-212bMD |
Założenia (opisowo): | Wiedza z 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. |
Tryb prowadzenia: | w sali |
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. Uogólnione liczby chromatyczne: kombinatoryka, aspekty algorytmiczne, zastosowania (2 wykłady). 3. Kolorowania o małej głębokości drzewiastej: kombinatoryka i zastosowania (1 wykład) 4. Problem sprawdzania modelu dla logiki pierwszego rzędu na klasach o ograniczonej ekspansji (1 wykład) 5. Złożoność sąsiedztw (1 wykład) 6. Quasi-szerokość i gra w Rozdzielacza (1-2 wykłady) 7. Wymiar Vapnika-Chervonenkisa i elementy teorii stabilności (2 wykłady) 8. Wielomianowa ekspansja i separatory: zastosowania dla algorytmów aproksymacyjnych (1-2 wykłady) |
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 uczenia się: |
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%). Przedmiot można zaliczać w ramach studiów doktoranckich jako przedmiot metodologiczny. Wówczas dodatkowym warunkiem zaliczenia jest rozwiązanie co najmniej jednego z trudniejszych zadań z prac domowych, określonych przez prowadzących jako zadania "badawcze". |
Zajęcia w cyklu "Semestr letni 2023/24" (w trakcie)
Okres: | 2024-02-19 - 2024-06-16 |
Przejdź do planu
PN WT ŚR CZ PT WYK-MON
CW
|
Typ zajęć: |
Ćwiczenia, 30 godzin
Wykład monograficzny, 30 godzin
|
|
Koordynatorzy: | Michał Pilipczuk | |
Prowadzący grup: | Michał Pilipczuk, Wojciech Przybyszewski, Szymon Toruńczyk | |
Lista studentów: | (nie masz dostępu) | |
Zaliczenie: | Egzamin |
Właścicielem praw autorskich jest Uniwersytet Warszawski.