Слова недетерминизм и случайность часто воспринимаются как синонимы. Однако в контексте моделей вычислений они означают совсем разное. И там, и там есть некоторое дерево вычислений, но при использовании случайности выбирается одна ветвь равновероятно, а при использовании недетерминизма все ветви обрабатываются параллельно. И случайность, и недетерминизм позволяют решать алгоритмические задачи эффективнее. Хотя мы и не умеем это доказывать: для недетерминизма это знаменитая проблема равенства классов P и NP, для случайности - классов P и BPP. В курсе будет рассказано об обеих моделях вычислений, дан обзор известных результатов с детальным разбором некоторых конструкций. Много внимания будет уделено вопросам сводимости и полноты.