Prawdopodobieństwo w grafach

Informacje ogólne

Kod przedmiotu:	1000-1M19PNG
Kod Erasmus / ISCED:	11.1 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. / (0541) Matematyka Kod ISCED - Międzynarodowa Standardowa Klasyfikacja Kształcenia (International Standard Classification of Education) została opracowana przez UNESCO.
Nazwa przedmiotu:	Prawdopodobieństwo w grafach
Jednostka:	Wydział Matematyki, Informatyki i Mechaniki
Grupy:	Przedmioty monograficzne dla matematyki 2 stopnia Przedmioty obieralne na studiach drugiego stopnia na kierunku bioinformatyka
Punkty ECTS i inne:	(brak) 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:	Wykład będzie poświęcony procesom losowym na dyskretnych obiektach takich jak grafy, grupy skończone, permutacje, łańcuchy Markowa. Wśród omówionych tematów będą m.in. grafy losowe (model Erdosa-Renyi'ego, grafy d-regularne) i występujące w nich przejścia fazowe, błądzenia losowe i ich czasy mieszania, permutacje losowe, ekspandery i spektralna teoria grafów, a jeśli starczy czasu - związki między grafami skończonymi a nieskończonymi (granice grafów w sensie Benjaminiego-Schramma).
Pełny opis:	Wykład będzie poświęcony prawdopodobieństwu na dyskretnych strukturach takich jak grafy, grupy, permutacje. Jest to aktualnie żywo rozwijająca się tematyka mająca bliskie związki z kombinatoryką, teorią grup, fizyką statystyczną, informatyką teoretyczną. Poznamy wybrane metody probabilistyczne i geometryczne służące do analizy błądzeń losowych, łańcuchów Markowa, własności spektralnych grafów, przejść fazowych. Wśród omówionych tematów znajdą się m.in.: - podstawy teorii grafów losowych (model Erdosa-Renyi'ego, losowe grafy d-regularne, przejścia fazowe w grafach losowych) - czasy mieszania w łańcuchach Markowa (tasowanie kart, coupling, metody spektralne, cut-off) - permutacje losowe (proces wymiany i jego struktura cyklowa, rozkład Poissona-Dirichleta, metody z teorii reprezentacji) a jeśli czas nam na to pozwoli, to także: - spektralna teoria grafów (nierówność Cheegera, ekspandery, grafy Ramanujana) - granice grafów w sensie Benjaminiego-Schramma, podstawowe własności spektralne grafów nieskończonych W zależności od zainteresowań słuchaczy mogą pojawić się dodatkowe tematy (np. perkolacja na grafach skończonych, zastosowania non-backtracking random walk, związki z geometryczną teorią grup, metoda probabilistyczna w kombinatoryce). Wykład przewiduję raczej dla ambitniejszych studentów, czy może bardziej precyzyjnie - dla osób chcących włożyć trochę pracy w solidne nauczenie się czegoś, np. poprzez regularne rozwiązywanie prac domowych i spisywanie notatek z wykładu. W zamian obiecuję dobrą zabawę przy poznawaniu nowej matematyki.
Literatura:	R. Lyons, Y. Peres "Probability on Trees and Networks" G. Pete "Probability on Graphs and Groups" L. Saloff-Coste "Random Walks on Finite Groups" S. Janson, T. Łuczak, A. Ruciński "Random Graphs" D. Levin, Y. Peres "Markov Chains and Mixing Times" F. Chung "Spectral Graph Theory"
Efekty uczenia się:	Satysfakcja z poznania nowego kawałka matematyki. Poczucie dobrze spędzonego czasu. Znajomość problemów i metod występujących w rachunku prawdopodobieństwa na dyskretnych strukturach.

Przedmiot nie jest oferowany w żadnym z aktualnych cykli dydaktycznych.

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