Доказательства

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