1. SylabUZ
2. Wydział Matematyki, Informatyki i Ekonometrii
3. semestr zimowy 2023/2024
4. Computer science and econometrics - pierwszego stopnia z tyt. licencjata
5. Probabilistic Methods in Computer Science

Wygeneruj PDF dla tej strony

Probabilistic Methods in Computer Science - opis przedmiotu

Cel przedmiotu

Learning about the possibilities of using probabilistic methods in computer science.

Wymagania wstępne

Zapisz zmiany

Probability calculus, Discrete mathematics 1.

Zakres tematyczny

Lecture

1. The naive method and the expected value method in combinatorics, their algorithmic aspect (4 hours).

2. Local Lovász Lemma and its application (3 hours).

3. The method of conditional probabilities  in the problem of derandomization of algorithms (3 hours).

4. Las Vegas and Monte Carlo algorithms. Examples illustrating these types: Min-Cut, RandAuto, RandQS; performance analysis, random parameters, classification (6 hours).

5. Random game techniques estimating algorithm complexity (2 hours).

6. Complexity classes: RP, Co-RP, BPP, ZPP (2 hours).

7. Geometric algorithms: convex hull of points in the plane, binary divisions of the plane, diameter of a set of points (4 h).

8. Graph algorithms: pairs of shortest paths, generalization of the Min_Cut problem, minimum spanning tree (2 hours).

Exercises

1. Analysis of proofs of facts using naive method, expected value method and the Local Lovász Lemma based on English literature; clearly presentation of  evidences to other course participants (10 hours).

2. Based on derandomization method, the construction of deterministic algorithms for finding  combinatorial objects  whose existence is confirmed  by naive method and/or the expected value method (4 hours).

3. Proving simple relationships between complexity classes learned during classes (4 hours).

4. Team analysis of at least one contemporary article on the issues discussed during classes (10 hours).

5. Final test (2 hours).

Metody kształcenia

Conversation lecture, traditional lecture, discussion exercises.

Efekty uczenia się i metody weryfikacji osiągania efektów uczenia się

Opis efektu	Symbole efektów	Metody weryfikacji	Forma zajęć

Warunki zaliczenia

Conditions for passing classes:

1. Checking the level of students' preparation and their activity during the exercises.
2. Written work enabling the assessment of whether and to what extent the student has achieved the above-mentioned learning outcomes, mainly in terms of knowledge and skills.
3. Conversation during a lecture to verify higher levels of educational outcomes in terms of knowledge and skills.
4. Presentation of material prepared by the student independently and/or in a group.

   The grade for the course consists of the grade for the exercises (50%) and the grade for the exam (50%). The condition for taking the exam is obtaining a positive grade in the exercises. The condition for passing the course is obtaining positive grades in the exercises and the exam.

Literatura podstawowa

1. R. Motwani, P. Raghavan, Randomized Algorithms, Algorithms and Theory of Computation, Handbook, CRS Press 1998.
2. N. Alon, J.H. Spencer, The probabilistic Method in Interscience Series in Discrete Mathematics and Optimization, 2000.
3. M.O. Rabin, Probabilistic Algorithms for testing Primality, Journal of Number Theory 12(1), 1980.

Literatura uzupełniająca

1. J. Beck, An Algorithmic Paproch to the Lovász Local Lemma, in Random Structures and Algorithms, vol.2 (4) 1991.
2. R. Diestel, Random Graphs, in Graph Theory.

Uwagi

Zmodyfikowane przez dr Ewa Synówka (ostatnia modyfikacja: 10-04-2024 20:01)