Принцип Диріхле. Презентація до уроку.

Опис документу:
Маю надію ,що цей матеріал згодиться Вам.Намагалась підібрати та розробити інформацію,яка може бути максимально корисною й для загального розвитку вчителя.Дуже дякую за перегляд та зацікавлення моїми розробками.

Відображення документу є орієнтовним і призначене для ознайомлення із змістом, та може відрізнятися від вигляду завантаженого документу. Щоб завантажити документ, прогорніть сторінку до кінця

Перегляд
матеріалу
Отримати код
Опис презентації окремими слайдами:
Принцип Диріхле
Слайд № 1

Принцип Диріхле

Йоганн Петер Густав Лежен Діріхле (нім . Johann Peter Gustav Lejeune Dirichlet; *13 лютого 1805, Дюрен, Франція, зараз Німеччина — 15 травня 1859, ...
Слайд № 2

Йоганн Петер Густав Лежен Діріхле (нім . Johann Peter Gustav Lejeune Dirichlet; *13 лютого 1805, Дюрен, Франція, зараз Німеччина — 15 травня 1859, Геттінген, Ганновер) — німецький математик, відомий значним внеском до математичний аналіз, теорію функцій комплексної змінної та теорію чисел. Діріхле вперше формалізував ідею в 1834 році під назвою Schubfachprinzip («принцип шухляди» або «принцип полку»). З цієї причини він також зазвичай званий принципом коробки Дірихле, принципом ящика Діріхле або просто принципом Дірихле — ім'я, яке може також ставитися до принципу мінімуму для гармонійних функцій. Оригінальна назва «шухляда» до сих пір використовується у французькій мові («principe des tiroirs»).

При́нцип Діріхле́ (також принцип коробок Діріхле, принцип голубів і кліток) — комбінаторне твердження, сформульоване німецьким математиком Петером ...
Слайд № 3

При́нцип Діріхле́ (також принцип коробок Діріхле, принцип голубів і кліток) — комбінаторне твердження, сформульоване німецьким математиком Петером Діріхле. Зображення голубів у комірках. Тут n = 10 голубів у m = 9 комірках. Оскільки 10 більше ніж 9, принцип Діріхле каже, що щонайменше одна комірка міститиме більш ніж одного голуба

Найчастіше в україномовній і російськомовній літературі використовується неформальне формулювання з кролями і клітками. В англомовній літературі ча...
Слайд № 4

Найчастіше в україномовній і російськомовній літературі використовується неформальне формулювання з кролями і клітками. В англомовній літературі частіше у формулюванні присутні голуби (звідси поширена назва pigeonhole principle). Найпоширеніше наступне формулювання цього принципу: Припустимо, деяке число кроликів розсаджені в клітках. Якщо число кроликів більше, ніж число кліток, то хоч би в одній з кліток буде більше одного кролика.

Загальніше формулювання: Припустимо, m кроликів розсаджені в n клітках. Тоді хоч би в одній клітці міститься не менше  m\n кроликів, а також хоч би...
Слайд № 5

Загальніше формулювання: Припустимо, m кроликів розсаджені в n клітках. Тоді хоч би в одній клітці міститься не менше  m\n кроликів, а також хоч би в одній іншій клітці міститься не більше m\n кроликів

Також є такі альтернативні формулювання принципу Діріхле. Якщо n об'єктів розподілені по m місцях та якщо n > m, то якесь місце отримує, принаймні,...
Слайд № 6

Також є такі альтернативні формулювання принципу Діріхле. Якщо n об'єктів розподілені по m місцях та якщо n > m, то якесь місце отримує, принаймні, два об'єкти. (еквівалентне формулювання 1) Якщо n об'єктів розподілені по m місцях таким чином, що на жодному місці не має більше одного об'єкта, то кожне місце отримує рівно один об'єкт. Якщо n об'єкти розподілені по m місцях та якщо n < m, то на якомусь місці немає об'єкта. (еквівалентне формулювання 3) Якщо n об'єкти розподілені по m місцях таким чином, що жодне місце не отримує об'єкт, то кожне місце отримує рівно один об'єкт.

Принцип має кілька узагальнень і може бути виражена різними способами. Зокрема, для натуральних чисел  k та m, якщо n = km + 1 об'єкти розподілені ...
Слайд № 7

Принцип має кілька узагальнень і може бути виражена різними способами. Зокрема, для натуральних чисел  k та m, якщо n = km + 1 об'єкти розподілені серед m множин, то принцип Діріхле стверджує, що принаймні одна з множин буде містити щонайменше, до k + 1 об'єктів. Для довільного n і m це узагальнююче до k + 1 = ⌊ (n — 1) / m⌋ + 1, де ⌊ … ⌋ функція взяття цілої частини від виразу (n — 1) / m.

Приклади застосування 10 друзів відправили один одному святкові листівки. Кожний із них відправив 5 листівок. Довести, що якихось двоє друзів відпр...
Слайд № 8

Приклади застосування 10 друзів відправили один одному святкові листівки. Кожний із них відправив 5 листівок. Довести, що якихось двоє друзів відправили листівки один одному. Доведення: кількість пар, що можна утворити з 10 друзів: C210 = 45. А всього відправлених листівок 5∙10=50. Отже, згідно з принципом Діріхле, на деякі з пар друзів припадає дві листівки. Картки пронумеровані послідовно цілими числа ми від 1 до 2n +1. Яку найбільшу кількість карток можна вибрати так, щоб жоден з номерів не дорівнював сумі якихось двох інших номерів карток? Розв'язання. Припустімо, що таких карток існує не менше ніж n+2. Розташуємо вибрані картки в порядку зростання їхніх номерів, віднімемо від усіх номерів найменший номер картки. Одержується n + 1 різних чисел, відмінних від 0. Тоді, згідно з принципом Діріхле, отримана множина має принаймні один спільний елемент із початковою. Це число відповідно буде сумою двох чисел. Легко перевірити, що для n + 1 картки з непарними номерами {1,3,5,…, 2n +1} умови задачі вже виконуються.

Принцип Діріхле застосовується в інформатиці. Наприклад, однакові елементи завжди можуть бути в геш-таблиці, так як число можливих ключів перевищує...
Слайд № 9

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

Узагальнення Найпопулярніша формулювання принципу Діріхле така: «Якщо в n клітинах сидить m зайців, причому m> n, то хоча б в одній клітці сидять п...
Слайд № 10

Узагальнення Найпопулярніша формулювання принципу Діріхле така: «Якщо в n клітинах сидить m зайців, причому m> n, то хоча б в одній клітці сидять принаймні двох зайців». На перший погляд навіть незрозуміло, чому це абсолютно очевидне зауваження є досить ефективним методом вирішення завдань. Справа в тому, що в кожній конкретній задачі нелегко буває зрозуміти, що ж тут «зайці» і «клітки» і чому зайців більше, ніж клітин. Вибір зайців і клітин часто неочевидний; далеко не завжди по виду завдання можна визначити, що слід скористатися принципом Діріхле. А головне, цей метод дає неконструктивну доказ (ми, природно, не можемо сказати, в який саме клітці сидять два зайці, а знаємо тільки, що така клітина є), а спроба дати конструктивну доказ, т. Е. Доказ шляхом явного побудови або вказівки необхідного об'єкта, може привести до набагато більших труднощів. 2. Деякі завдання вирішуються також методами, в якійсь мірі аналогічними принципом Діріхле. Сформулюємо відповідні затвердження (всі вони легко доводяться методом від противного). а) Якщо на відрізку довжиною 1 розташовано декілька відрізків. сума довжин яких більше 1, то принаймні два з них мають спільну точку. б) Якщо на окружності радіуса 1 розташовано декілька дуг, сума довжин яких більше 2p, то принаймні дві з них мають спільну точку. в) Якщо всередині фігури площею 1 розташовано кілька фігур, сума площ яких більше 1, то принаймні дві з них мають спільну точку

ЛітератуРА Ядренко М. Й. Принцип Діріхле.– Х.: Основа, 2005.– 96с. Чудаков Н. Г. Введение в теорию L-функций Дирихле. Андреев А. А., Горелов Г. Н. ...
Слайд № 11

ЛітератуРА Ядренко М. Й. Принцип Діріхле.– Х.: Основа, 2005.– 96с. Чудаков Н. Г. Введение в теорию L-функций Дирихле. Андреев А. А., Горелов Г. Н. и др. Принцип Дирихле. Brualdi, Richard A. (2010). Introductory Combinatorics (вид. 5th). Pentice Hall. ISBN 978-0-13-602040-0 Fletcher, Peter; Patty, C.Wayne (1987). Foundations of Higher Mathematics. PWS-Kent. ISBN 0-87150-164-3 Grimaldi, Ralph P. (1994). Discrete and Combinatorial Mathematics: An Applied Introduction(вид. 3rd). ISBN 978-0-201-54983-6 Herstein, I. N. (1964). Topics In Algebra. Waltham: Blaisdell Publishing Company. ISBN 978-1114541016.

Зверніть увагу, свідоцтва знаходяться в Вашому особистому кабінеті в розділі «Досягнення»