EMBER_CLI_FASTBOOT_BODY

Введение в теоретическую информатику

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

Anonymous 15023239 October 30, 2017 link
Rated:  4
Познавательный курс, помогает, например, готовиться к кандидатскому минимуму по спец. 01.01.09 (не заменяет, конечно, классические учебники, но дополняет и облегчает вхождение в сложные темы). Рассказан интересно и понятным языком, без зубодробительных формализмов. Из минусов: во-первых, некоторые темы раскрыты ну очень кратко, а то и почти никак - например, теория игр; во-вторых, слишком много заданий с рецензией, которые никто не проверяет из-за малого на данный момент числа слушателей. Надеюсь, минусы будут устранены в новом, переделанном варианте курса - авторы обещают разбить его на несколько более маленьких курсов и дополнить новой информацией и задачами. Удачи авторам!
Rated:  5
Достаточно интересно, профессиональный курс. Но Показалось очень много интерактива (сдача решения на проверку другим ученикам и преподавателю): проверка затягивается, рецензии идут по месяцу - баллов не хватает на получение сертификата (про "с отличием" молчу вообще). Темы интересны, с точки зрения подачи материала - неплохо, информативно
Rated:  5
Так как оценку курса нельзя градировать с половинами звезд, то пусть это будет все-таки 5, хотя мне бы хотелось оценить именно в 4+. Курс безусловно интересный, но это даже не введение, а знакомство с теоретической информатикой. Введение обычно бывает кратким и в достаточной степени сухим, знакомство выходит более насыщенным, но не погружающимся в основы. Тем, кто начинает курс, я бы порекомендовал ознакомиться с главами 3-5 в других источниках, так как в данном курсе не хватает некой формальности и точности в их изложении. Если кому-то пришлось застопориться на них, то можно пропустить и пробовать проходить курс дальше. По крайней мере мне это помогло, материал в большей степени опирается на первые две главы. Вообще какие-то познания в любой из изложенных здесь тем упростят задачу понимания сути курса, который просто собирает довольно большой пласт математики и информатики в краткий экскурс, потому что разбираться в каждой теме с нуля в таком сжатом формате довольно затруднительно. Также не стоит пугаться заданий-эссе, большая часть ответов на них строится на интуитивных догадках, а не строгих математических обоснованиях, то есть понимания сути вполне достаточно для ответа. Тех, кого смущают опечатки и ошибки лектора на первых уроках, могу порадовать, примерно с пятого урока их уже не будет до конца курса. Вероятно, будь побольше заинтересованных слушателей, то курс действительно вышел бы на отлично, и все недочеты сгладились бы в комментариях ровно как в первых двух главах!
Play
To watch this video please visit https://stepik.org/lesson//step/
4.7 All reviews

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

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

About the course

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

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

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

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

Requirements

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

Target audience

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

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