0.1: Що таке дискретна математика?

Last updated
Save as PDF

Page ID: 64482

$ \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}}$

Template:MathJaxLevin

дис·бетонувати/диск.

Прикметник: Індивідуально роздільний і виразний.

Синоніми: роздільні - відокремлені - виразні - абстрактні.

Визначення дискретної математики важко, оскільки визначити математику важко. Що таке математика? Вивчення чисел? Частково, але ви також вивчаєте функції та лінії та трикутники та паралелепіпеди та вектори та... Або, можливо, ви хочете сказати, що математика - це сукупність інструментів, які дозволяють вирішувати завдання. Які проблеми? Гаразд, ті, які включають числа, функції, лінії, трикутники,... Яким би не було ваше уявлення про те, що таке математика, спробуйте застосувати до неї поняття «дискретний», як визначено вище. Деякі математики принципово стосується речей, які є окремо окремими і відмінними.

У класі алгебри або обчислення ви могли знайти певний набір чисел (можливо, набір чисел у діапазоні функції). Ви б представили цей набір як інтервал:$[0,\infty)$ це діапазон,$f(x) = x^2$ оскільки набір виходів функції всі дійсні числа 0 і більше. Цей набір чисел НЕ є дискретним. Цифри в наборі не розділені на багато взагалі. Насправді, візьміть будь-які два числа в наборі і між ними нескінченно багато більше, які також є в наборі. Дискретна математика все ще може запитати про діапазон функції, але набір не буде інтервалом. Розглянемо функцію, яка дає кількість дітей кожної людини, яка читає це. Що таке асортимент? Я припускаю, що це щось на$\{0, 1, 2, 3\}\text{.}$ кшталт Може бути 4 там теж. Але, звичайно, ніхто не читає цього, що має 1,32419 дітей. Цей набір дискретний, оскільки елементи роздільні. Також зверніть увагу, що входи до функції є дискретним набором, оскільки кожен вхід є окремою людиною. Ви б не розглядали дробові входи (ми не дбаємо ні про що$2/3$ між парою читачів).

Один із способів відчути предмет - розглянути типи проблем, які ви вирішуєте в дискретній математиці. Ось кілька простих прикладів:

Досліджуйте!

Примітка: По всьому тексту ви побачите Розслідувати! діяльність, подібна до цього. Відповідайте на запитання в них якнайкраще, щоб дати собі відчуття того, що буде далі.

Найпопулярніший математик у світі влаштовує вечірку для всіх своїх друзів. Як спосіб розбити речі, вони вирішують, що кожен повинен потиснути руку. Якщо припустити, що всі 10 людей на вечірці кожен потиснути руку кожній іншій людині (але не собі, очевидно) рівно один раз, скільки рукостискань відбувається?
На розминці конкурсу «All Star Hot Dog Eating Contest» Оскар, Ал з'їв один хот-дог. Потім Боб показав його, з'ївши три хот-доги. Щоб не переставати, Карл з'їв п'ять. Це тривало, коли кожен учасник з'їдав ще два хот-доги, ніж попередній учасник. Скільки хот-догів з'їв Зенон (26-й і останній учасник конкурсу)? Скільки хот-догів з'їли всі разом?
Після розкопок протягом тижнів, ви, нарешті, прибудете до похоронної камери. Кімната порожня за винятком двох великих скринь. На кожному вирізано послання (дивно англійською мовою):

$two-chests.svg$

Ви точно знаєте, що одне з цих повідомлень є правдою. Що робити?

Ще в минулі часи п'ять невеликих міст вирішили, що хочуть побудувати дороги, що безпосередньо з'єднують кожну пару міст. Хоча у міст було багато грошей, щоб будувати дороги так довго і звивисто, як вони хотіли, було дуже важливо, щоб дороги не перетиналися один з одним (оскільки знаки зупинки ще не були винайдені). Також не допускалися тунелі і мости. Чи можливо кожному з цих міст побудувати дорогу до кожного з чотирьох інших міст, не створюючи перехресть?

Однією з причин важко визначити дискретну математику є те, що це дуже широкий опис, який інкапсулює велику кількість предметів. У цьому курсі ми вивчимо чотири основні теми: комбінаторику (теорія способів поєднання речей; зокрема, як рахувати ці способи), послідовності, символічна логіка та теорія графів. Однак є й інші теми, які належать під дискретною парасолькою, включаючи інформатику, абстрактну алгебру, теорію чисел, теорію ігор, ймовірність та геометрію (деякі з них, особливо останні два, мають як дискретні, так і недискретні варіанти).

Зрештою, найкращий спосіб дізнатися, що дискретна математика - це зробити це. Давайте приступимо! Перш ніж ми зможемо почати відповідати на більш складні (і веселі) проблеми, ми повинні закласти певну основу. Почнемо з розгляду математичних тверджень, множин і функцій в рамках дискретної математики.