Uniwersytet Warszawski - Centralny System Uwierzytelniania
Strona główna

Grafy rzadkie

Informacje ogólne

Kod przedmiotu: 1000-2M12GRZ
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: 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 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

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
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Ćwiczenia, 30 godzin więcej informacji
Wykład monograficzny, 30 godzin więcej informacji
Koordynatorzy: Michał Pilipczuk
Prowadzący grup: Michał Pilipczuk, Wojciech Przybyszewski, Szymon Toruńczyk
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 7.0.3.0-2b06adb1e (2024-03-27)