Serdecznie zapraszamy wszystkich studentów i doktorantów zainteresowanych teorią prawdopodobieństwa na cykl wykładów Probabilistic Analysis of Algorithms profesora Oleksandra Marynycha z Kijowskiego Uniwersytetu Narodowego im. Tarasa Szewczenki. Profesor Marynych jest uznanym specjalistą z zakresu losowych struktur rekurencyjnych.
Wykłady będą się odbywały od 24 maja do 23 czerwca w środy (14-16, sala B) oraz piątki (12-14, sala 601) w Instytucie Matematycznym Uniwersytetu Wrocławskiego.
Szczegółowy plan spotkań:
Środa, 24 maja, 14:15-16:00, sala B
Piątek, 26 maja, 12:15-14:00, sala 601
Środa, 7 czerwca, 12:15-14:00, sala 601
Piątek, 9 czerwca, 12:15-14:00, sala 601
Środa, 14 czerwca, 14:15-16:00, sala B
Piątek, 16 czerwca, 12:15-14:00, sala 601
Środa, 21 czerwca, 14:15-16:00, sala B
Piątek, 23 czerwca, 12:15-14:00, sala 601
Szczegółowy opis wykładu:
The classical analysis of algorithms is mainly concerned either with average or with extremal performance properties of computer algorithms. Assuming a random input, one usually asks, what is the average performance of an algorithm, or what is the worst (the best) performance? The probabilistic analysis of algorithms is a modern field lying in the intersection of probability theory and computer science that is used to analyze more delicate performance features of algorithms. Its methods and techniques allow one to answer questions like: what is the probability that the working time of an algorithm does not exceed a prescribed threshold? What is the confidence interval for the working time of an algorithm of a prescribed significance level?
The aim of the course is to explain how to formulate and answer the above questions and why they are useful. During the course a student will become acquainted both with mathematical machinery used in the field, as well as with various applications, including probabilistic analysis of sorting algorithms, search algorithms, graph algorithms and general divide-and-conquer algorithms.
Syllabus:
Lecture 1: The classic Quicksort Algorithm: where has the probabilistic analysis of algorithms started from?
Lecture 2: Required mathematical toolbox: spaces of probability measures and probability metrics. The Banach fixed-point theorem for probability measures.
Lecture 3-4: Divide-and-conquer paradigm. Random linear recurrences and their examples: variations of Quicksort, random trees, and leader-election procedures.
Lecture 5-6: The contraction method for linear random recurrences with non-degenerate limit equations and examples.
Lecture 7-8: The contraction method for linear random recurrences with degenerate limit equations and examples.