[Stepik] Доказательства, ChatGPT и Python (Александр Куликов, Иван Павлов)

​

На вашем экране — современный интерактивный курс-учебник по основам дискретной математики.

Зачем изучать дискретную математику?

Вот как ChatGPT отвечает на этот вопрос. Мы сами бы не сформулировали это лучше, поэтому просто присоединяемся к ответу.

Изучение дискретной математики важно по нескольким причинам.
1 Фундамент компьютерных наук. Дискретная математика обеспечивает математические основы для многих концепций в компьютерных науках, включая алгоритмы, структуры данных, криптографию, теорию автоматов и многое другое.
2 Развитие логического мышления. Эта область способствует развитию абстрактного и критического мышления, улучшает навыки решения проблем и способность к аналитическому мышлению.
3 Применение в различных областях. Дискретная математика находит применение в разнообразных областях, таких как криптография, разработка компьютерных игр, теория сетей, оптимизация и многие другие.
4 Теоретический фундамент для вычислительных систем. Она помогает понять, как работают компьютеры на более глубоком уровне, включая обработку данных, хранение информации и передачу данных.
5 Решение конкретных задач. В отличие от непрерывной математики, дискретная математика часто занимается конкретными, раздельными объектами, что делает ее незаменимой при моделировании реальных систем, где объекты четко определены и разделены.
6 Основа для научных исследований. Для студентов и исследователей, занимающихся компьютерными науками, электроникой, математическим моделированием и смежными областями, знание дискретной математики является ключевым для понимания и проведения научных исследований.

Изучение дискретной математики обеспечивает студентам и профессионалам важные инструменты и концепции, которые применимы во многих технических и научных областях.

А нужно ли сегодня изучать дискретную математику, раз у нас теперь есть ChatGPT?
На сегодняшний день ChatGPT умеет не только отлично помогать с рутинными делами, но даже и решать математические задачи! При этом прямо под чатом, где мы общаемся с ChatGPT, написано: "ChatGPT can make mistakes. Consider checking important information." И действительно, мы увидим много базовых задач из дискретной математики, для которых ChatGPT выдаёт решение, похожее на правильное, но при этом даже близко не являющееся правильным. Таким образом, умение отличать правильное доказательство от неправильного стало ещё более актуальным. В этом курсе мы вместе прокачаем этот навык!

Что именно покрывает этот курс?
В этом курсе мы с вами будем изучать доказательства в дискретной математике. Доказательства важны и нужны во всех разделах компьютерных наук: нужно доказывать корректность программ, алгоритмов, протоколов, а также оценки на их эффективность. Мы познакомимся с распространёнными типами доказательств (доказательства существования, оптимальности, корректности; метод математической индукции; оценки скорости роста), а также узнаем, как доказательства классифицируются в компьютерных науках с вычислительной точки зрения (увидим примеры интерактивных и вероятностно проверяемых доказательств).

В будущем мы планируем сделать продолжение этого курса, покрывающее другие большие сюжеты дискретной математики — комбинаторику, теорию вероятностей, теорию графов и логику.

Что же делает этот курс современным?
Мы активно будем использовать Python и ChatGPT. На сегодняшний день эти современные инструменты нужны и полезны людям самых разных профессий — далеко не только тем, кто изучает технические науки. Python мы будем использовать для решения различных задач из области компьютерных наук и для интерактивных примеров. A ChatGPT нам поможет научиться критически оценивать готовые решения.

А что делает этот курс интерактивным?
- Вы не просто будете изучать идеи дискретной математики. Мы предложим вам решить много задач. По каждой задаче мы дадим вам обратную связь по вашему решению и обсудим эталонное.
- Вы будете общаться с однокурсниками, преподавателями и ChatGPT. Будем учиться друг у друга, будем вместе разбираться, какие решения являются правильными, а какие — нет.
- Вы будете решать интерактивные головоломки, запускать написанный нами код на Python и писать свой.

Но зачем в курсе по математике нужен код?
- Применения: примеры на Python покажут вам широкий спектр применений идей дискретной математики на практике.
- Интерактивные примеры: код можно использовать как интерактивные примеры: скопируйте код, измените в нём параметры, запустите — и посмотрите, что получилось.
- Более глубокое понимание: программируя конкретную идею, вы разберётесь во всех её деталях.

Но почему Python, а не какой-нибудь другой язык?
У Python есть несколько преимуществ.
- Высокоуровневый язык. Довольно просто начать писать код на Python, даже если вы до этого никогда не программировали. Код легко читаемый и компактный.
- Интерактивный режим. Python можно использовать как интерактивный язык для общения с компьютером (REPL: read-eval-print loop).
- Батарейки в комплекте. Есть много библиотек, которые позволят нам в пару строк кода нарисовать граф или график, сгенерировать случайную последовательность и так далее.

Это частично объясняет, почему Python так популярен для прототипирования программ, а также в таких областях, как машинное обучение, науки о данных и веб-разработка. Недостатки у Python тоже есть: высокоуровневость Python делает его более медленным. Нас это пугать не будет, поскольку мы будем рассматривать короткие куски кода, где производительность будет не особо важна.

Чему вы научитесь
- Разберётесь с основными идеями дискретной математики — конструктивными и неконструктивными доказательствами, методом математической индукции, доказательствами корректности алгоритмов, оценками скорости роста функций.
- Будете активно использовать Python и ChatGPT. Использование этих двух инструментов делают работу более эффективной в самых разных областях.
- Решите много задач — как теоретических, так и прикладных. Мы поможем вам с каждой задачей: и дадим обратную связь по вашему решению, и расскажем наше решение.
- Напишете эффективные программы на Python для задач из разных областей компьютерных наук.
- Потренируетесь критически оценивать ответы ChatGPT. Для этого мы вместе посмотрим на много решений задач от ChatGPT и найдём в половине из них ошибки.
- Пообщаетесь (в комментариях и на форумах решений) как с однокурсниками, так и с преподавателями.

Для кого этот курс
Для всех, кто хочет разобраться в математических основах компьютерных наук.

Начальные требования
Знание математики на школьном уровне.