(русский / in Russian) Основы вычислимости и теории сложности | Дмитрий Ицыксон (Basics of computability and complexity theory by Dmitry Itsykson)

# playlist (click the video's upper-left icon)

source: Лекториум              2013年6月16日
Это первая часть годового курса о вычислениях.Курс дает ответы на такие вопросы: Что такое алгоритм? Что такое эффективный алгоритм? Что такое доказательство? Как доказать, что нет алгоритма, который решит данную задачу? Как доказать, что что-то нельзя доказать? Как понять, что нет эффективного алгоритма для данной задачи? Что такое сложность объекта? Из курса можно узнать, что такое вычислимые функции, арифметическая иерархия, колмогоровская сложность, классы P, NP, PSPACE и пр., полиномиальная иерархия, схемная сложность, сложность с ограничением по памяти и многие другие интересные вещи.страница курса на сайте Computer Science Center
Подписывайтесь на канал: https://www.lektorium.tv/ZJA
Следите за новостями:
https://vk.com/openlektorium
https://www.facebook.com/openlektorium