Ответы пользователя по тегу Дискретная математика
  • Как решить эту задачу со множествами?

    @Mercury13
    Программист на «си с крестами» и не только
    1. ВЕРНО. A \cap C \in A \in B \in B \cup D (прости уж, что пишу тэгами TeX).
    3. ВЕРНО, следует из законов логики.
    5. UPD. Всё-таки ВЕРНО, тут надо действовать через x. Пусть $x \in A \cap C$, тогда $x \in A$ и $x \in C$. А значит, $x \in B$ и $x \in D$. Дальше понятно? Точно так же можно решить и 3.
    Ответ написан
  • Как решить уравнение х*х-2=3y в целых числах?

    @Mercury13
    Программист на «си с крестами» и не только
    x делится на 3: 9z² − 2 = 3y. Справа делится на 3, слева нет.
    Иначе: (x−1)(x+1) = 3y + 1. Хотя бы один из множителей кратен трём. Всё наоборот: слева делится на 3, справа нет.
    Дальше уже, по-моему, доказательство не упростить.
    Ответ написан
  • Что такое проекция на множество узлов в графе?

    @Mercury13
    Программист на «си с крестами» и не только
    Двудольный граф можно представить как соответствие R ⊆ A×B. Тогда проекция двудольного графа на долю A (или B) — это те вершины из A (или из B), из которых идёт ребро.
    Ответ написан
  • Как и где можно применить дискретную математику в программировании?

    @Mercury13
    Программист на «си с крестами» и не только
    В программу дискретной математики моего факультета входили…
    • теория множеств
    • теория графов
    • комбинаторика
    • алгебра логики, исчисление высказываний
    • теория автоматов

    Теория множеств — это основа ВСЕЙ университетской математики. Не зря её повторяли ещё и на муть-анализе.
    К тому же в теории множеств есть два классных понятия — отношение эквивалентности и отношение порядка. Операции == и <= перегружать приходилось?
    Соответствие везде определённое, функциональное, сюръективное, инъективное, биективное. Теория баз данных. Допустим у нас есть сотрудник и телефон, как они соотносятся? У всех ли сотрудников есть телефоны? Бывает ли у сотрудника два телефона? У всех ли телефонов есть сотрудники? Бывает ли у телефона два сотрудника? Ну а биективное — это соответствие «1:1».

    Теория графов — понятное дело, в алгоритмах на сетях. Создание, уничтожение, обход, поиск пути…

    Комбинаторика — это а) количество элементов в том или ином конечном множестве; б) способы перебрать их все. Например, мне реально приходилось перебирать комбинации из N элементов не более чем по M. Нерекурсивно.

    Алгебра логики — это основа работы компьютеров. Когда булевское условие многоэтажное — как записать его в понятном виде и как его упростить?

    Теория автоматов — это крайне упрощённый принцип работы процессоров. Поэтому если надо написать предельно простого вида виртуальную машину — см. конечные автоматы. А также автомат Мура — это лексический анализатор в любом языке программирования.
    Ответ написан
  • План подготовки для поступления в Яндекс ШАД?

    @Mercury13
    Программист на «си с крестами» и не только
    Алгоритмы. Немного олимпиадного программирования ОЧЕНЬ не помешает. Алгоритмы там предлагают несложные, но очень нетривиальные, надо чувствовать, как решить задачу. Элементы сложности алгоритмов. Две задачи из восьми гарантированно будут.

    Алгебра и дискретная математика. Первый курс, всё скопом, без доказательств. Линейные уравнения, квадратичные формы, матрицы, собственные векторы, жорданова форма, перестановки, графы, теория множеств, комбинаторика, алгебра логики…

    Интегралы (не слишком «злые», но приёмы «подстановка», «по частям» и «тригонометрический интеграл» всё же освоить стоит). Интеграл средней сложности — постоянный гость в ШАДý. Может быть и ещё одна задача из мутьанализа — но это как повезёт и задача будет гарантированно нетривиальная, но решающаяся на «том, что помнишь с института» — дифференцирование, ряды Тейлора, основы топологии, простейшие пределы, правило Лопиталя. Вспомни, как берутся простейшие двойные интегралы, может попасться, например, на теории вероятностей.

    ФКП. Самое начало. Аналитических функций и рядов Лорана точно не будет. А вот то, что в комплексном поле многочлен n-й степени имеет n корней, знать надо.

    Теория вероятностей. Непрерывные и дискретные вероятности. Нечто несложное, почти что на уровне кубиков и карт, но одна-две из восьми будет. Хотя статистика — важная часть ШАДа, на экзамене не требуют. И пекла типа белых шумов и интегралов Ито не будет. Хотя что-то типа дискретной марковской цепи — а вдруг, хотя знакомые мне три экзамена не было.

    Школьные олимпиадные задачи. Возможна одна.

    Итого.
    Две — алгоритмы.
    Одна-две — вероятность.
    Одна — интеграл.
    Две-три — что угодно из школьной математики, дискретной математики, матанализа, алгебры, ФКП…

    P.S. Очень хороший приём, который мне помог. Конечно, вам придётся держать скан какого-нибудь справочника или распечатку Википедии (это не возбраняется, но электроника запрещена — впрочем, калькулятора задачи не требуют). Печатайте на одной стороне, вторую — на черновик!
    Ответ написан
  • Как доказать выводимость формул в исчислении высказываний?

    @Mercury13
    Программист на «си с крестами» и не только
    Любая тождественно истинная формула выводима. Любая выводимая формула тождественно истинна.
    Первый курс университета.
    Так что — либо вывести из десятка аксиом, либо доказать тождественную истинность.
    Ответ написан