Курс «Теоретическая информатика: сложность вычислений» на платформе Stepik научит вас замерять степень сложности алгоритмов и других объектов программирования.
Вы сможете создавать логические выражения и протоколы с криптографическими алгоритмами, писать коды и многое другое.
Вам подойдет этот курс, если вы:
- хотите использовать теорию информатики для практики;
- имеете опыт программирования;
- владеете школьным курсом математики;
- студент первого-второго курса технической специальности.
Ключевые навыки, которые вы освоите на этом курсе:
- отгадывание числа;
- сортировка;
- использование метода резолюций;
- решение переборных задач;
- выяснение класса;
- оптимизация перебора.
Учебная программа:
- введение: информация о курсе;
- деревья: отгадывание числа, сортировка, нахождение максимума;
- функциональные элементы: связки, сумма, полнота, оценка сложности, сравнение;
- логика высказываний: линейное программирование, формулы, принцип Дирихле, следование, нахождение вывода, исчисление резолюций;
- переборные задачи: задачи класса P и неразрешимые задачи;
- класс PSPACE: теорема Цермело, игры, выяснение класса.
В конце обучения выдается сертификат от Computer Science Center.