EMBER_CLI_FASTBOOT_BODY

Теоретическая информатика: сложность вычислений

Теоретическая информатика — раздел математики, связанный с логикой, алгоритмами, сложностью: там много несложных, но важных результатов, о некоторых мы попробуем рассказать. В этом разделе обсуждаются разные ситуации, когда можно измерять "сложность" того или иного алгоритма или объекта

Certificate Stepik

About this course

Слова «теоретическая информатика», а особенно их английский вариант (“theoretical computer science”), звучат странно — как «сухое плавание». Но в них есть смысл, причём не только для теоретиков: абстрактные конструкции и математические результаты, если они хорошо поняты, в нужный момент могут натолкнуть на решение вполне практической задачи.

Мы попытались отобрать простые и одновременно важные понятия и результаты, которые могут вам пригодиться. Некоторые из них совсем практические (скажем, инварианты циклов, коды с исправлением ошибок или криптографические протоколы), другие скорее указывают границы возможностей (скажем, результаты об алгоритмической неразрешимости или NP-полноте). Разделы достаточно независимы, так что если что-то не понравилось или показалось непонятным, можно идти дальше.

По большей части мы не используем сложной математики (а базовые результаты про целые числа мы напоминаем) и каких-то конкретных программистских навыков, но, конечно, некоторая математическая грамотность и программистский опыт не повредят.

Наконец, заранее просим прощения, если курс покажется вам неудачным — рассказывать что-то, не видя реакции, всегда трудно, и это скорее первый блин, чем результат многолетней практики.

Who is this course for

студенты младших курсов

По большей части мы не используем сложной математики (а базовые результаты про целые числа мы напоминаем) и каких-то конкретных программистских навыков, но, конечно, некоторая математическая грамотность и программистский опыт не повредят.

Meet the Instructors

User picture
Александр Шень
ЦССМШ -- Вторая школа -- мехмат МГУ -- аспирантура кафедры логики (В.А.Успенский) -- ИППИ РАН, LIF Marseille, LIRMM Montpellier (CNRS)
www.lirmm.fr/~ashen

Course content

О чём этот курс?
  1.  
     
Разрешающие деревья
Схемы из функциональных элементов
Пропозициональная логика
Переборные задачи и их сложность
Класс PSPACE
Ускорение перебора

Certificate

Computer Science центр

Student reviews

Прекрасный обзорный курс - рассматривается большое количество разнообразных тем. Курс имеет низкую планку входа - все необходимое объясняется по ходу. При этом с самого начала задачи вовсе не так тривиальны - многие из них заставили поломать голову. Для меня курс оказался сложным из-за формата большинства заданий - эссе. Недостаточно просто выбрать правильный ответ - приходилось его тщательно расписывать и обосновывать. И это здорово способствует лучшему пониманию материала! Странной показалась разбивка материала по неделям. Некоторые были совсем короткие, другие казались перегруженными. Из-за этого было тяжело дозировать нагрузку. Также некоторые лекции выглядели вырванными из контекста, будто изначально предполагалось больше лекций, но не все они попали в курс. Больше всего не понравилось, что во многих заданиях эссе были не очень хорошо описаны критерии оценки, что вызывало сложности при проверке решений. Этой части курса стоит уделить больше внимания. Большое спасибо авторам за проделанную работу! Очень хочется увидеть продолжение.
Курс для меня показался довольно сложным и сложность возрастала с каждой неделей и количество решенных задач с каждой новой неделей только падало) Нагрузка в курсе на мой взгляд не очень хорошо сбалансирована, на одних неделях задач совсем немного, а на других раза в 2 больше) Тем не менее курс был очень интересным и я узнал для себя много нового и полезного. Хочу сказать большое спасибо команде курса и особенно Александру Шеню и Александру Куликову. Видел, что в предыдущем запуске курса были модули "Ликбез по арифметике: числа, остатки, алгоритм Евклида" и "Криптография", странно, что они не попали в этот курс, может они будут в продолжении курса? И будет ли продолжение? Было бы интересно. Знаю, что на курсере есть целая специализация по дискретной математике к которой Александр Шень и Александр Куликов тоже приложили руку, но жаль, что она на английском и без русских субтитров( А так было бы интересно пройти эту специализацию. Похоже придется учить английский)
Получился довольно разнообразный курс, касающийся нескольких больших тем. Основными, пожалуй, были исчисление резолюций и NP-полнота. Думаю, что я ожидал рассмотрения сложности несколько с другой стороны (та же master-теорема упомянута, но не раскрыта подробно), но получилось здорово. Особенно порадовало, что преподаватель на связи и быстро отвечает на (глупые) вопросы. Как уже сказали, стоило бы добавить материал про машину Тьюринга, так как она достаточно активно используется в доказательствах. Насчёт сложности курса - пожалуй, совмещать его с каким-то ещё не получится, если темы незнакомые и хочется разобраться в них как следует. Команде курса большое спасибо! Жду следующих частей

Share this course