#How_to_заботать

How to заботать дискретную математику?

Важнейшая дисциплина, без которой невозможно поступить в ШАД, в магистратуру, сдать ГОС, написать олимпиаду. Да и без нее невозможно просто чувствовать себя уверенно в программировании, DS, ведь там постоянно применяются понятия и скромные навыки, приобретенные в курсе дискретной математике. Да и частенько, помимо алгосов, ее спрашивают на собесах: в тестовом задании или на интервью, особенно в зарубежных офисах Европы и США.
Как всегда все книжки в комментариях, там же делимся своими любимыми материалами и опытом по боту дискретки😎😎

1) Комбинаторика
Как нестранно, у большинства с этим по началу проблемы, ибо обычно рассказывают общий случай, выражая его формулами, а потом пытаются подогнать условие новой задачи под эти формулы. Такой подход просто ужасен!! Вместо того, чтобы решать задачу, студент просто думает: здесь размещение с повторением или нет— угадай мелодию. Чтобы не попасть под этот конвейер дебилов, стоит просто рассмотреть, как можно больше живых примеров, стараться выводить каждую конструкцию с нуля, а не заучивать формулы, особенно это важно начинающим, ибо основная сложность комбинаторной задачи— формализовать, понять какое перед нами множество, как говорят в теории вероятностей: найти пространство исходов.
В этом поможет классика: "Ленинградские математические кружки" (главы Комбинаторика-1 и Комбинаторика-2), где куча прикольных примеров и задач. Особенно обратите внимание на раздел "Шары и Перегородки", который очень часто встречается в прикладных задачах и который очень любят спрашивать, особенно на собесах в ШАДы.
Если тяжеловато идет, то можно начать с "Комбинаторики" Виленкина, где куча-куча и куча-куча примеров, задач, написано все подробно и понятно. Единственное большой объем, но при этом есть даже главы про производящие функции и задачи из орбиты.
Также любопытные задачи можно встретить и в "Первой научной" подборке от Михаила Абрамовича.
Отмечу также важность комбинаторики: без нее, например, не сможете решать задачи на дискретную вероятность или не сможете даже посчитать сложность многих алгоритмов.
2) Множества
Что множества можно представлять как кружочки знают еще с детского сада, но вот на формулу включений/исключений есть и нормальные задачи, да и любят спросить на олимпиадах явно или неявно, например, в суммировании вероятностей и мат ожидания. Чтобы не попасть в просак смотрим первую главу Виленкина.
3) Текстовые задачи, Индукция, Принцип Дирихле, Игры...
Просто смотрим все темы текстовых задач в "Ленинградских кружках". Все это необходимая база и есть в каждом вступительном, да и опять же просто на собесах. По остальным разделам тоже советую пробежаться, ибо они важные элементы математической культуры. Теории и задач оттуда хватит на маги и собесы с лихвой, особенно хорошо задачи гуглятся на problems.ru. Для тестов и интервью на собесах подойдет порешать последнюю текстовую задачу из ЕГЭ (это не шутка), например, тесты в Тинек так и составляются. В ШАДах же любят давать эти идеи на сюжетах из других дисциплин: линейной алгебры или мат анализа. Если уже успели разобраться с ними, то проблем не возникнет.
4) Графы
Для начала берем "Ленинградские кружки" разбирает разделы "Графы - 1" и "Графы - 2". Теории там совсем мало, просто знакомитесь с основными определениями и общими приемами. Для хайповых магистратур этого вполне хватит.
Для ШАДов далее можно взять Гашкова "Дискретная математика", где много примеров и прикладных задач, да и в принципе он покрывает весь курс дискретки в ВУЗе. Потом "Теорию Графов" Омельченко и "Материалы Московской сборной" главу 12, чтобы посмотреть на теорию Рамсея, случайные графы. Если хотите прямо сильную прокачку по теории, то можете взять "Теорию Графов" Уилсон (книга достойная + очень много задач и упражнений).