EMBER_CLI_FASTBOOT_BODY

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

The course meets the formal recommendations of Stepik
Video Player is loading.
Current Time 0:00
/
Duration 0:00
Loaded: 0%
Progress: 0%
Stream Type LIVE
Remaining Time -0:00
 
1x
Play
To watch this video please visit https://stepik.org/lesson//step/

About the course

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

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

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

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

Instructors

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

Reviews

Alexey Kholodkov December 24, 2017 link
4
Прекрасный обзорный курс - рассматривается большое количество разнообразных тем. Курс имеет низкую планку входа - все необходимое объясняется по ходу. При этом с самого начала задачи вовсе не так тривиальны - многие из них заставили поломать голову. Для меня курс оказался сложным из-за формата большинства заданий - эссе. Недостаточно просто выбрать правильный ответ - приходилось его тщательно расписывать и обосновывать. И это здорово способствует лучшему пониманию материала! Странной показалась разбивка материала по неделям. Некоторые были совсем короткие, другие казались перегруженными. Из-за этого было тяжело дозировать нагрузку. Также некоторые лекции выглядели вырванными из контекста, будто изначально предполагалось больше лекций, но не все они попали в курс. Больше всего не понравилось, что во многих заданиях эссе были не очень хорошо описаны критерии оценки, что вызывало сложности при проверке решений. Этой части курса стоит уделить больше внимания. Большое спасибо авторам за проделанную работу! Очень хочется увидеть продолжение.
5
Курс для меня показался довольно сложным и сложность возрастала с каждой неделей и количество решенных задач с каждой новой неделей только падало) Нагрузка в курсе на мой взгляд не очень хорошо сбалансирована, на одних неделях задач совсем немного, а на других раза в 2 больше) Тем не менее курс был очень интересным и я узнал для себя много нового и полезного. Хочу сказать большое спасибо команде курса и особенно Александру Шеню и Александру Куликову. Видел, что в предыдущем запуске курса были модули "Ликбез по арифметике: числа, остатки, алгоритм Евклида" и "Криптография", странно, что они не попали в этот курс, может они будут в продолжении курса? И будет ли продолжение? Было бы интересно. Знаю, что на курсере есть целая специализация по дискретной математике к которой Александр Шень и Александр Куликов тоже приложили руку, но жаль, что она на английском и без русских субтитров( А так было бы интересно пройти эту специализацию. Похоже придется учить английский)
5
Получился довольно разнообразный курс, касающийся нескольких больших тем. Основными, пожалуй, были исчисление резолюций и NP-полнота. Думаю, что я ожидал рассмотрения сложности несколько с другой стороны (та же master-теорема упомянута, но не раскрыта подробно), но получилось здорово. Особенно порадовало, что преподаватель на связи и быстро отвечает на (глупые) вопросы. Как уже сказали, стоило бы добавить материал про машину Тьюринга, так как она достаточно активно используется в доказательствах. Насчёт сложности курса - пожалуй, совмещать его с каким-то ещё не получится, если темы незнакомые и хочется разобраться в них как следует. Команде курса большое спасибо! Жду следующих частей
Video Player is loading.
Current Time 0:00
/
Duration 0:00
Loaded: 0%
Progress: 0%
Stream Type LIVE
Remaining Time -0:00
 
1x
Play
To watch this video please visit https://stepik.org/lesson//step/
4.7 All reviews

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

Expected time to complete:
41 hours
Language:
Русский
Certificate:
Computer Science центр
Certificate details
Certificate condition: 40 points
With distinction: 80 points

About the course

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

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

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

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

Requirements

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

Target audience

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

This course is entirely free. All content is available now.