Skip to main content
LibreTexts - Ukrayinska

4: Бі'єкції та комбінаторні докази

  1. Last updated
  2. Save as PDF
  • Page ID
    64827

    • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)

    Ви можете згадати, що в Math 2000 ви дізналися, що два набори мають однакову кардинальність, якщо між ними є біекція. (Біекція - це функція один до одного, на.) Це призводить нас до ще одного важливого методу підрахунку множини: ми придумуємо біекцію між елементами невідомого множини та елементами множини, які ми знаємо, як рахувати. Ця ідея дуже тісно пов'язана з поняттям комбінаторного доказу, яке ми вивчимо в другій половині цієї глави.

    Крім: Хоча ми не будемо вивчати концепції\(P\) і\(NP\) взагалі в цьому курсі, ті з вас, хто вивчив ці ідеї в курсах інформатики можуть бути зацікавлені дізнатися, що більшість методів, що використовуються, щоб довести, що конкретна проблема в\(P\) або в\(NP\) пов'язані з методами, розглянутими в цьому розділі. Як правило, проблема\(X\) виявляється в\(NP\) (наприклад), починаючи з проблеми\(Y\), яка вже відома в\(NP\). Потім вчений використовує деякі розумні ідеї, щоб показати, що проблема\(Y\) може бути пов'язана з проблемою таким\(X\) чином, що якщо проблему можна\(X\) було б вирішити в поліноміальний час, це рішення дасть рішення проблеми\(Y\), все ще в поліноміальному часі. При цьому той факт,\(Y\) що\(X\) в\(NP\) силах бути\(NP\) і в. Одні і ті ж ідеї іноді можуть співвідносити кількість розв'язків задачі\(X\) з кількістю розв'язків задачі\(Y\).

    • 4.1: Підрахунок за допомогою відхилень
      Це може бути важко зрозуміти, як підрахувати кількість результатів для конкретної проблеми. Іноді можна буде знайти іншу проблему, і довести, що дві проблеми мають однакову кількість результатів. Якщо ми зможемо з'ясувати, як підрахувати результати для другої проблеми, то ми також вирішили першу проблему! Це може здатися нахабно очевидним інтуїтивно, але ця методика може забезпечити прості рішення проблем, які на перший погляд здаються дуже складними.
    • 4.2: Комбінаторні докази
      Коли ми дивилися на біекції, ми використовували цю ідею, щоб знайти простіший спосіб підрахувати щось, що здавалося складним. Але якщо ми насправді можемо знайти формулу, яка правильно підраховує відповідь на нашу проблему якимось складним способом, і ми також можемо знайти іншу формулу, яка правильно підраховує відповідь на ту саму проблему, дивлячись на неї по-іншому, тоді ми знаємо, що значення двох формул повинні бути рівними, незважаючи на їх різний зовнішній вигляд. Це ідея комбінаторного доказу.
    • 4.3: Резюме
      Ця сторінка містить короткий зміст тем, охоплених у розділі 4.