EduTranslator

Научные работы со всего мира

Рубрика: Математика

Математика фільму «21»

Оригінал тексту під авторством Jeff Moehlis доступний за посиланням.

Фільм «21» це історія студентів МТІ (Массачусетський технологічний інститут), які «зчитували карти», щоб збільшити вірогідність свого виграшу у казино граючи в Блекджек. Недивно, що у цьому фільмі майже всі математики. Найбільш очевидним являється «підрахунок карт», який заснований на методах, що був опублікований в книзі «Удар Дилера» Едварда Торпа, 1962 року. Обговорення методу і математики «підрахунку карт» детально описані на інших різноманітних сайтах. На цьому ж сайті, ви зможете дізнатися про деякі математичні ідеї, які теж згадуються у фільмі. Я сподіваюсь, що це збільшить не лише ваше задоволення від перегляду фільму, але і бажання вчити математику!

Послідовність Фібонначі

В фільмі «21», коли Бен Кемпбел (грає Джим Стерджесс) святкую своє день народження, торт каже:

0, 1, 1, 2, 3, 5, 8, 13, …

Це перші терміни із послідовності Фібонначі, котрі були використані в якості прикладу в книзі «Книга Абака», що була опублікована в 1202 році Леонардо Фібонначі. Виходить, що спочатку записувалися числа «0, 1», а потім вираховувалося кожне наступне число як сума двох попередніх чисел із цієї серії. Таким чином, третій номер в цій серії 1 = 1+0, четвертий номер 2 = 1+1, п’ятий номер 3 = 2+1 і т.д. Наступний номер на торті буде 21 = 13+8, до 21-го Дня народження Бена. Розумно, чи не так? (хммм, «21» пов’язане з Блекджеком чи віком Бена). Бену доведеться почекати, поки він не досягне 34 = 21+13 для свого наступного «дня народження Фібонначі».

Можна виявити інші послідовності Фібоначчі, вказавши різні числа в перших двох позиціях. Наприклад, послідовність Фібонначі, що починається з «2, 5», являється:

2, 5, 7, 12, 19, 31, 50, …

Проблема Монті Холла

Розглянемо наступну варіацію фінального раунду класичного телевізійного ігрового шоу «Давайте поб’ємось обзаклад»:

Є троє дверей, і за одними із них – автомобіль, а за вдома іншими – кози. Якщо ви оберете одні двері з автомобілем позаду них, то виграєте автомобіль. Тепер скажіть, що ви обираєте двері 1. Потім господар Монті Холла відкриє або двері 2, або двері 3, за якими знаходиться коза. (Він знає, що знаходиться за кожними дверима, і ніколи не відкриває двері, за якими знаходиться автомобіль). Монті тепер дає вам вибір: ви можете триматися дверей 1, або ж перелаштуватися до інших дверех. Що ви маєте робити? І чи має це взагалі вже якесь значення?

Аналогічне питання ставиться і Бену Кемпбелу (грає Джим Стерджесс) професором Міккі Розою (грає Кевін Спейсі) в фільмі «21». Без вагань Бен відповідає на це запитання вірно, що переконує професора Розу в тому, що Бен буде являтися чудовим доповненням до їхньої «команди зчитування карт». Перед тим як читати далі, спробуйте дати відповідь на це питання самостійно.

Хтось вирішує цю проблему, порівнюючи вірогідність вибору автомобіля, якщо ви тримаєтеся вашого початкового вибору автомобіля, якщо ви зміните своє рішення після того, як Монті відриє одні двері. Зверніть увагу, що автомобіль має рівну вірогідність того, що 1/3 знаходиться за дверима 1,2 і 3.

По-перше, припустимо, що ваша стратегія полягає в тому, щоб притримуєтесь вашого початкового вибору, а саме двері 1. Тоді ви виграєте тільки тоді, якщо автомобіль і справді знаходиться за дверима 1. Тобто, вірогідність вашого виграшу складає 1/3.

Далі, припустимо, що ваша стратегія полягає в тому, щоб змінити двері. Тут потрібно розібрати три моменти:

  • Якщо автомобіль знаходиться за дверима 1, Монті відкриє двері 2 і 3, щоб відкрити для вас козу. Ви перелаштовуєтесь на двері 2 чи двері 3, і в будь-якому разі ви переходите до дверей за якими знаходяться кози (пам’ятайте, що автомобіль знаходиться за дверима 1).
  • Якщо автомобіль знаходиться за дверима 2, Монті відкриє двері  3. Це тому, що він завжди відкриває двері, за якими знаходиться коза, і звичайно він не може вам відкрити двері 1, тому що це був ваш початковий вибір. Виходить, що ви можете перейти до дверей 2, за якими знаходиться автомобіль. Бінго! Ти переміг!
  • Якщо автомобіль знаходиться за дверима 3, Монті відкриє двері 2. Це тому, що він завжди відкриває двері, за якими знаходиться коза, і він не може відкрити вам двері 1, тому що це був ваш початковий вибір. Виходить, що ви можете перейти до дверей 3, за якими знаходиться автомобіль. Бінго! Ти переміг!

Саме тому, якщо ваша стратегія полягає в тому, щоб перейти від одних дверей до інших, ви виграєте 2/3 = 1/3 + 1/3 часу. (пам’ятайте, вірогідність 1/3, що автомобіль знаходиться за будь-якими конкретними дверима). Таким чином, найкраща стратегія полягає в зміненні дверей – розраховані вірогідності вказують на те, що ви маєте в два рази більше шансів виграти, якщо зробите саме так. Правильна відповідь Бена у фільму «21» вказує на те, що він саме та людина, котра потрібна для «зчитування карт». Це показує не лише той факт, що він розумний, але і демонструє факт його розуміння, що краще йти далі з вибором, який дає тобі максимальні шанси на перемогу. Розуміння цього має важливе значення для успіху «зчитування карт» у грі Блекджек.

В 1990 році аналогічне питання з’явилося в листі у колонці «Запитайте Мерілін», котру вела Мерілін вос Савант, в секції «Парад» (її можна було знайти в деяких недільних гахетах). Мерілін дала правильну відповідь, але багато читачів (в тому числі і професори математики) вважали, що відповідь була неправильною. Так що, ви не сильно переймайтеся, якщо ви також дали невірну відповідь, коли відповідали на це питання самі. Але ж тепер ви все знаєте!

Метод Ньютона-Рафсона

Із класу алгебри можна згадати, що рівняння

Задається квадратною формулою

Уявімо, що замість цього ви хочете знайти значення для х, котре вирішує загальне алгебраїчне рівняння f(x) = 0.

Таке значення для х називається коренем f(x). За винятком спеціальних варіантів f(x), таких як f (x) = a x2 + b x + c, як зазначено вище, неможна знайти корінь за допомогою алгебраїчних операцій.

В фільму «21» професор Міккі Роза ( у виконанні Кевіна Спейсі) читає лекцію про метод Ньютона-Рофсона для находження коренів f(x). Це було розроблено безпосередньо Ісааком Ньотоном і Джозефом Рафсоном в 1600-х роках. Ідея полягає в тому, що для того аби зробити припущення для кореня рівняння (назвемо його х0) і потім використати це припущення для створення значення х (назвемо його х1), котре (сподіваюсь) буде ще ближче до кореня, ніж початкове припущення. Це робиться шляхом малювання дотичної функції f(x) при x=x0 і взяття до уваги х1 в значенні для х, при якому ця пряма лінія проходить через нуль. (Для тих із нас, хто знається на вимірюваннях, зрозуміє, що ця дотична лінія визначається похідною f(x). Повторюючи цю процедуру знову і знову, щоб генерувати х2, х3, і т.д., один (сподіваюсь) отримує значення, котрі все краще і краще приближують до кореня. Я продовжую говорити «сподіваюсь», тому що метод Ньотона-Рафсона не завжди успішний, хоча це , скоріше за все, буде тільки якщо ви зробити хороший початковий вибір. Цей малюнок ілюструє цей метод:

Цей метод був розроблений задовго до того, як існували комп’ютери, але виявився ідеальним для реалізації на комп’ютері: використовують цей цикл для генерації послідовних значень xn.

Підрахунок карт

Хороше обговорення про «підрахунку карт» для гри у Блекджек, ви зможете знайти у цій Вікіпедія статті.

Число Мерсенна від Каліфорнійського університету у Лос-Анджелесі

Оригінал тексту під авторством Edson Smith доступний за посиланням.

У серпні 2008 року на одному з комп’ютерів, що належать до
Програми обчислень (PIC) факультету математики
Каліфорнійського університету у Лос-Анджелесі , було виявлено
нове число Мерсенна. Виявляється, це число є найбільшим,
відомим у світі простим числом. Тому відкриття викликало такий
великий інтерес. Намагаючись заощадити час та енергію кожного,
я подумав, що виставлю інформацію в Інтернеті у форматі FAQ.
Оскільки деякі питання, що я отримав, надійшли від людей, які не
мають технічних знань (включаючи дітей), ці FAQ часто не є
технічним. Хоча ви все одно повинні знати, що таке прості числа.
Однак, змушений попередити: хоча я працюю на факультеті
математики, я системний адміністратор, а не математик! Якщо ви
шукаєте серйозну інформацію про Число Марсенна, пропоную
вам відмінний веб-сайт Кріса Колдвелла Числа Мерсенна: історія,
теореми та списки. Інші цікаві сайти: сторінка Вольфрама про
Числа Мерсенна і цікаві цифри та назви Числа Марсенна від
Лендона Курта Нолла.
А тепер, до питань!

П: Що ж таке Число Мерсенна?

В: Якщо коротко, є такий підклас натуральних чисел під назвою
Числа Мерсенна. Вони названі на честь Марена Марсенна,
математика 17-го сторіччя. На момент написання, існує менш ніж
50 відомих чисел Мерсенна.
Усі числа Мерсенна виглядають як 2^P -1, де P — відоме натуральне
число. Перше число Мерсенна — 3, тому що 2 ^2 -1 = 3. Зауважте, що
показник P є простим числом, у цьому випадку 2. Наступне число Мерсенна — 7, оскільки 2 ^3 — 1 = 7, де P є простим числом 3. Далі
йде 31 (2^ 5 — 1), потім 127 (2^ 7 — 1), 8191 (2^ 13 — 1) та 131071 (2^ 17 — 1).
Як бачите, після декількох перших чисел, числа Мерсенна стають
більше дуже швидко. Ось гарна табличка з відомими числами
Мерсенна, що надасть певну перспективу.

Найменші з цих цифр були відомі ще за часів античності, але
навіть у 1951 році було виявлено лише 12. За останні 50 років ще
кілька десятків було виявлено за допомогою комп’ютерів.
Нещодавно відкриті числа Мерсенна надзвичайно великі, з
мільйонами цифр. Число Мерсенна від Каліфорнійського
університету у Лос-Анджелесі має близько 12,9 мільйонів цифр у
довжину.

Зауважте, що всі числа Мерсенна є простими числами, але не всі
прості числа — числа Мерсенна.

П: Що таке число Мерсенна від Каліфорнійського
університету у Лос-Анджелесі? Чому воно таке особливе?

В: Число Мерсенна від Каліфорнійського університету у Лос-
Анджелесі — це перше число, яке має понад 10 мільйонів цифр.
Воно було відкрито 23 серпня 2008 року на факультеті
математики Каліфорнійського університету у Лос-Анджелесі.
Всі числа Мерсенна особливі, оскільки вони дуже рідкісні, але ця
особливість привернула особливу увагу, оскільки вона претендує
на приз (див. нижче).

Число Мерсенна від Каліфорнійського університету у Лос-
Анджелесі — 243112609 — 1. Фактичне число — 12 978 189 цифр.
Якщо ви дуже зацікавлені, Лендон Курт Нолл, який вже давно
досліджує число Мерсенна, зрозробив його ось тут . Якщо ви ну,
дуже-дуже зацікавлені, він також надає ціле число англійською
мовою (всі 328 мегабайт) тут .

П: Це перше число Мерсенна від Каліфорнійського
університету у Лос-Анджелесі?

В: Взагалі-то, це восьме число Мерсенна від Каліфорнійського
університету у Лос-Анджелесі!

У 1952 р. Професор Рафаель Робінсон знайшов 5 нових чисел
Мерсенна, використовуючи Західний автоматичний комп’ютер
(SWAC) стандартів Каліфорнійського університету у Лос-
Анджелесі, один з найшвидших комп’ютерів свого часу. Були
відкриті 13те та 17те числа Мерсенна, і кожне мало сотні цифр.
Робінсонові числа Мерсенна були знайдені першими за 75 років, і
були першими, які були відкриті за допомогою цифрового
комп’ютера.

У 1961 році, математик Каліфорнійського університету у Лос-
Анджелесі, Олександр Гурвіц, відкрив 19те та 20те число
Мерсенна за допомогою комп’ютерного центру IBM 7090
Каліфорнійського університету у Лос-Анджелесі. Кожне з цих
чисел мало понад 1200 цифр.

І тепер, через 47 років, традиція Каліфорнійського університету у
Лос-Анджелесі знаходити числа Мерсенна продовжується!
П: Хто шукає числа Мерсенна? І як вони їх знаходять?
В: Тисячі людей, використовують десятки тисяч комп’ютерів та
беруть участь у Широкомасштабному проекті добровільних
обчислень з пошуку простих чисел Мерсенна (GIMPS) —
організоване зусилля, присвячене пошуку чисел Мерсенна. Це
одне з багатьох поточних зусиль у сфері розподілених обчислень, і, можливо, найбільш успішне.

Пошук дуже добре організований. Добрі люди в Primenet
координують ці зусилля протягом останніх 12 років і надають
відмінну програму Prime95 для всіх, хто хоче її запустити. Вони
стежать за тим, які номери було протестовано та забезпечують стійкий потік неперевірених кандидатів у спільноту GIMPS.

Учасники GIMPS оцінюються відповідно до їх продуктивності.
Ви можете знайти нас під назвою UCLA_Math. Ми, як правило,
десь між 40-м і 55-м місцями в рейтингу.

Для того, щоб перевірити лише один номер кандидата, у машини
може зайняти місяць. Але використовуючи силу окремих
комп’ютерів, підключених до інтернету по всьому світі, можна
досягнути швидшого прогресу.

П: Які шанси знайти число Мерсенна?

В: згідно з проектом GIMPS, можливість того, що будь-яке число кандидата буде числом Мерсенна, складає 1 з 150 000.
П: Як насправді тестують числа, щоб виявити, що вони є
числами Мерсенна?

В: Існує багато чисел форми 2 ^P — 1, але не всі з них — числа
Мерсенна. Існує декілька прийомів для перевірки цих чисел, щоб
побачити, що це числа Мерсенна. Але початковим методом
вважається спроба розкласти коефіцієнт показника кандидата P, а
потім спробувати розкласти коефіцієнт числа кандидата, 2^P-1,
використовуючи малі числа.

Існує 75-річний алгоритм під назвою тест Лукаса-Лемера, який
всіма визнаний як найкращий інструмент для тестування чисел
Мерсенна. Програма Prime95 постійно використовує цей метод, а
також деякі інші. Пояснення виходить за обсяги цього документа,
але зацікавлений читач може більше дізнатися тут.

П: Гаразд, навіщо люди шукають числа Мерсенна? Для чого
вони потрібні?

В: З тих же причин, коли люди піднімаються в гори, плавають
невідомими морями і досліджують космос. Це виклик! Цікаво
доторкнутися до обчислювальної математики та шукати щось невідоме, те, чого як ви вважаєте не існує. Як бонус, на відміну
від старих дослідників, ми сидимо в зручних офісних стільцях,
під час наших пошуків!

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

Дослідник простих чисел Кріс Колдвел досліджує цю тему більш
глибоко у своїй статті «Чому люди знаходять ці прості числа?»

П: Окрім виклику, чому ви вирішили приймати участь?

В: Як це було на багатьох інших сайтах, ми зрозуміли, що наша
велика (75 місць) PIC / Математична комп’ютерна лабораторія
використовувала лише частину наявної потужності центрального
процесора. Замість того, щоб дозволити всім цим циклам
витрачати енергію даремно, ми розглянули ряд розподілених
обчислювальних проектів, визначивши, що GIMPS найкраще
підходить для нас. Окрім того, що GIMPS є математичним
проектом, ми виявили, що він дуже добре написаний та не
заважав недосвіченим комп’ютерним користувачам (це не
відносилось до іншого програмного забезпечення, яке ми
досліджували).

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

П: Що ви зробили для зауску? Чи було важко?

В: Програмне забезпечення GIMPS Prime95 дуже легке з точки
зору системної адміністрації. Його легко встановити, і воно не
потребує технічне обслуговування.

Програмне забезпечення Prime95 регулярно оновлює інформацію
про стан обробки на центральних комп’ютерах Primenet. Якщо
машина, на якій вона працює, ламається, то обчислення знов
почнуть працювати там, де вони зупинилися, після ввімкнення
комп’ютера. Якщо окремий блок не працює протягом тривалого
часу, Primenet поверне номер і призначить його іншому
користувачеві. А також призначить новий номер, коли машина
знов буде працювати.

П: Як працює верифікація?

В: Коли число Марсенна знайдене, формальне оголошення не
проводиться, поки незалежна сторона не підтвердить цю вимогу.
З винятково великими числами, такими як ці, завжди є невелика
можливість обчислювальних проблеми з використаним
алгоритмом, або з процесором самого комп’ютера (класичний
приклад — проблема з рухомую комою Intel).

Через ці потенційні проблеми, числа Марсенна завжди
перевіряються з використанням абсолютно іншого алгоритму на
комп’ютері з іншою архітектурою. Перевірка може тривати два
тижні або довше.

П: Коли відбулося відкриття? Який комп’ютер це був?

В: Число Мерсенна від Каліфорнійського університету у Лос-
Анджелесі зареєстрували 23 серпня 2008 року на комп’ютері під
назвою zeppelin.pic.ucla.edu, Dell Optiplex 745 з операційно/
системою Windows XP та процесором Intel Core 2 Duo E6600, що
працює на частоті 2,4 ГГц. Назва «zeppelin»; була частиною нашої
класичної серії Rock Band комп’ютерів.

П: А що там з приводу призових грошей?

В: Electronic Frontier Foundation (EFF), перша організація
інтернет-цивільних свобод, спонсує нагороди «Cooperative Computing Awards«. Ці нагороди мають на меті «заохочувати
звичайних користувачів Інтернету робити внесок у вирішення
величезних наукових проблем», а також надавати призові гроші за
досягнення певних орієнтирів.

EFF має постійну винагороду в розмірі 100 000 доларів США за
відкриття першого простого числа з 10 мільйонами цифр. Число
Мерсенна від Каліфорнійського університету у Лос-Анджелесі
має майже 12,9 мільйонів цифр і відповідає критеріям нагороди.
Як тільки офіційні результати будуть опубліковані в відповідному
журналі, приз віддадуть. Це вібудеться в 2009 році найближчим
часом.

За попередньою угодою, лише 50% нагороди належить
першовідкривачеві простого числа з 10 мільйоннами цифр. 25%
призначено на благодійність, і, зважаючи на колективну природу
GIMPS, основну частину від 25% віддадуть першовідкривачам
інших чисел Мерсенна, при цьому невелика сума переходить до
GIMPS.

П: А що це я чую про плакат? Чи буде такий для числа
Мерсенна від Каліфорнійського університету у Лос-
Анджелесі?

В: Роками компанія під назвою Perfectly Scientific, створює
плакат найбільшого просто числа, відомого на даний час. Плакат
для M44, випущений у 2006 році, використовував надзвичайно
малі шрифтів, щоб стиснути 9,8 мільйона цифр на одному постері
розміром 29 дюймів на 40. Компанія запропонувала ювелірну
лупу разом з плакатом, щоб його можна було прочитати.

Річард Краандалл з Perfectly Scientific нещодавно зв’язався зі
мною, для того щоб повідомити, що плакат числа Мерсенна від
Каліфорнійського університету у Лос-Анджелесі тепер можна придбати. Він коштує $ 99, без рамок і доступний на веб-сайті Perfect Scientific.

П: Як щодо інших нещодавно відкритих чисел Мерсенна?

В: Через два тижні після того як було відкрито число Мерсенна
від Каліфорнійського університету у Лос-Анджелесі, інші 10
мільйонів цифр плюс чисел Мерсенна були виявлені Гансом-
Майклом Елвініче у Німеччині. Розміром у 11.2 мільйони цифр,
десь на 10% менше від числа Мерсенна від Каліфорнійського
університету у Лос-Анджелесі.

Це не перший випадок, коли числа Мерсенна були виявлені поза
порядком. У 1988 році Колквіт і Уельс виявили менше число
Мерсенна, ніж попередні два, відкриті у 1983 і 1985 роках.
На момент написання даного матеріалу число Мерсенна від
Каліфорнійського університету у Лос-Анджелесі вважається 46-м
числом Мерсенна (названим «M46» спільнотою, що шукає числа
Мерсенна), хоч і було виявлено 45м. Число Елвініче — це M45, але
було відкрите 46-м.

Ще одним ускладнення — не всі потенційні прості числа між M39
(відкрите у 2001 році) та число Мерсенна від Каліфорнійського
університету у Лос-Анджелесі були перевірені. І в майбутньому
вони можуть бути знайдені в ширшому діапазоні. Якщо так й
буде, число Мерсенна від Каліфорнійського університету у Лос-
Анджелесі отримає «просування» до M47.

Я щиро дякую всім людям, які допомогли мені з цим документом.
Дякую Селу Зап’єн та Мері Маргарет Сміт за їх відмінну
коректуру, і Джиму Картеру за допомогу зі структурою та
організацією. Я особливо хочу подякувати Роберту Джонсону,
який переконався, що кожне висловлювання, яке я зробив, було
дійсним і який обережно виправив мої численні непорозуміння.
Ці FAQ створені та розроблені Едсоном Смітом. Остання правка
липень, 2018.

Самостоятельно пересекающиеся сферы

Оригинал статьи представлен на сайте http://www.unf.edu/~ddreibel/research/sphere.html под авторством Daniel Dreibelbis.

В касательной (bitangency) погружного S с замкнутой поверхности M в R4 представляет собой пары точек (Р, Q) такая, что S(р) не равно s(q), а отрезок протянут между (p) и S(q) лежит в касательной плоскости S на P, и касательной плоскости S на Q. Для поверхности в четвертом пространство, мы рассчитываем конечное число bitangencies.

Снимки имеют проекцию погружения сферы в четыре пространства, заданную картой:

(x, y, z) -> (x, y, x2 + xz, yz)

где x2 + y2 + z2 = 1. На этих снимках мы проецируем вниз первую ось.

Это погружение пересекает себя ровно один раз, а именно, когда (x, y, z) равно (0, 0, 1) и (0, 0, -1). Окраски поверхности пропорциональна значению X (т. е. высота поверхности в первом направлении оси), так что вы можете сказать, что есть двойная точка, по середине двойная кривая (это кривая, на самом деле охватывает четыре раза, как можно заключить из окантованные картины), эта поверхность также имеет четыре касательные, две из которых представлены черными линиями, две из которых с двойной щипок моменты, происходящие на обоих концах средней двойной кривой.

Один из вопросов, который мы можем задать, — это связь между касательными поверхности в четырех пространствах и битангенциями ее проекции вниз в три пространства. Любая касательная в четвертом пространстве должна проектироваться в пространстве 3, и будет частью двухмерного комплекта касательных. Чтобы определить, является ли пара точек (p, q) касательной поверхности в четырех пространствах, мы должны спроецировать поверхность вниз по двум векторам, так что плоскость, натянутая этими двумя векторами, стала поперечной касательным плоскостям в p и q. Если обе спроецированные поверхности имеют касательные между p и q, то (p, q) — это касательные поверхности в четырех пространствах. Кроме того, если нам посчастливится спроецировать вниз секущую линию битангенции, то одно из касательных направлений в каждой точке разрушится, и на проецируемой поверхности будут точки сжатия как в p, так и в q. Кроме того, эти точки сжатия будут происходить в одной и той же точке в трех пространствах. Поэтому, если наша проецируемая поверхность имеет две точки сжатия в одном и том же месте, то соответствующая пара точек является bitangency. В этом случае нам нужна только одна проекция, чтобы найти битагенцию. Наша проецируемая поверхность имеет две из этих двойных точек сжатия.

Цікавыя задачы з картай

Арыгінал артыкула.

Дон Кнут працуе над 4-ым Томам Мастацтва камп’ютэрнага праграмавання. Адна з глаў, аб двайковых вырашальных дыяграмах і іх ужываннях, прадмет, які я знаходжу вельмі цікавым. Кнут паказвае, што разнастайнасць цікавых задач з тэорыі графаў можна закадаваць, як булевы формулы, а адукаваныя ДВД прадстаўляюць усе магчымыя рашэнні задачы. Часцей ёсць нейкі крытэрый аптымізацыі, і тады значна лягчэй выбраць «самае лепшае» рашэнне з ДВД простым дынамічным праграмуючым алгарытмам.

Тут мы паказваем прыклад выкарыстання графаў, якія прадстаўляюць 48 мяжуючых штатаў з кропкай перасячэння на кожным штаце і грань паміж двума штатамі, калі яны падзяляюць мяжу. На кожнай карце, калі вы націснеце на малюнак, адкрыецца дакумент у фармаце SVG. Вось граф, на якім размешчаны кропкі на сталіцах штатаў:

Туры па сталіцах

Выкажам здагадку, што вы хочаце наведаць 48 сталіц штатаў з умовай, што Вы праедзеце адзін штат толькі адзін раз. (Іншымі словамі, вы хочаце знайсці гамільтанаў шлях на графе.) Як відаць на карце вышэй, калі вы пойдзеце па самым прамым шляху паміж сталіцамі, то вы часцей будзеце перасякаць іншыя штаты, або, у выпадку напрамкі з Лензінга, Мічыган у Мэдысан, Вісконсін, вы праедзеце праз возера Мічыган. Замест гэтага Вы павінны выбраць самы кароткі шлях, які будзе звязваць два штата адной гранню. Давайце назавем такі шлях турам па сталіцах. Вось дыяграма мажлівага маршруту паміж штатамі:

Грунтуючыся на простым аналізе плюс спробах Кнута, мы можам сказаць наступнае:

  • Усе туры павінны пачынацца або заканчвацца ў Мэне, паколькі ў Мэна адзіны сусед. Мы скарыстаемся Мэнам, як пачатковай кропкай.
  • Усе туры павінны заканчвацца за межамі Нью-Ёрка, паколькі гэта кропка сучлянення.
  • Усяго 68,656,026 розных тураў па сталіцах.

Вось самы кароткі тур па сталіцах, усяго 11,698 міль:

Вось самы доўгі тур па сталіцах, усяго 18, 040 міль:

Каляровы граф

Іншы цікавы клас задач ўключае ў сябе колеру карты. Правіла ў тым, каб ніякія мяжуючыя штаты не мелі адзін колер. Вядомая тэарэма аб чатырох колерах сцвярджае, што любы планарны граф можа мець да чатырох колераў.

Паколькі ДВД шыфруе ўсі магчымыя рашэнні ў булевы формулы, мы можам лёгка вылічыць, колькі ёсць рашэнняў. Для зафарбоўвання графа мы прыводзім у парадак нашы падлікі, каб выключыць сіметрыі з-за адвольнага прызначэння велічыні каляровай характарыстыкі (4! сіметрычных выпадку для 4 колераў).

Каб зафарбаваць мяжуючыя 48 штатаў, існуе 533,816,322,048 магчымых спосабаў. (Гэта ½ колькасці, прадстаўленага Кнутам, паколькі яго карта ўключае ў сябе Вашынгтон ДіСі, як 49-ы «штат», і ён можа быць запоўнены любым з двух колераў, не выкарыстаных для Мэрылэнда і Вірджыніі). Вось некалькі цікавых прыкладаў асаблівага зафарбоўвання:

  • Збалансаванае зафарбоўванне, дзе кожны колер выкарыстоўваецца ў дакладнасці для 12 штатаў. Існуе 12,554,677,864 такіх зафарбоўванняў, што, на здзіўленне вышэй 2,4% усіх магчымых зафарбоўванняў.

  • *Незбалансаванае зафарбоўванне, дзе адзін з колераў (зялёны) выкарыстоўваецца так мала, як гэта магчыма (2 штата). Ёсць усяго толькі 288 спосабаў зафарбаваць карту так, каб адзін колер выкарыстоўваўся двойчы.

  • *Незбалансаванае зафарбоўванне, у якім адзін колер (жоўты) выкарыстоўваецца так часта, як гэта магчыма (18 штатаў). Ёсць 71,002,368 спосабаў зафарбаваць карту так, каб адзін колер выкарыстоўваўся 18 разоў.

  • Камбінаванне абодвух. Зафарбоўванне, выкарыстоўваючы колер 2, 13, 15 і 18 разоў. Гэтая паслядоўнасць: 1) злева направа, выкарыстоўваючы кожны колер у паслядоўнасці самую малую колькасць раз і 2) справа налева, выкарыстоўваючы кожны колер у паслядоўнасці самую вялікую колькасць разоў. Ёсць 24 такіх рашэнні.

 

З перспектывы праграм зафарбоўвання графа, карта 48-мі штатаў ЗША адносна простая. Паглядзіце вэб-старонку Граф МакГрегора, каб убачыць больш складаныя карты.

Последовательность Фибоначчи, Спирали и Золотое сечение

Оригинал текста представлен на сайте Математического факультета, Университета Темпл (автор Dan Reich).

Последовательность Фибоначчи имеет определенный числовой образец, который возник как ответ на упражнение в самом первом алгебраическом тексте в высшей школе. Эта модель оказалась интересной и её значение выходит за пределы того, что представлял её создатель. Она может быть использована как модель или описание невероятного количества феноменов в математике и науке, искусстве и природе.  Математические идеи последовательности Фибоначчи дали миру, к примеру, понятие золотого сечения, спиралей и самоподобных кривых, и это всё уже давно ценится за их очарование и красоту, но никто так и не может объяснить, почему они так явно переплетаются в мире искусства и природы.

История началась в Пизе, Италия 1202 год. Леонардо Пизано Биголло был молодым человеком в возрасте двадцати лет, членом одной важной семьи торговцев в Пизе. В своих путешествиях по Ближнему Востоку он был очарован математическими идеями, которые пришли на запад из Индии через арабские страны. Когда он вернулся в Пищу, он опубликовал свои идеи в книге по математике под названием Книга Абака, которая стала поворотной вехой в Европе. Леонардо, которого с тех пор знают под именем Фибоначчи, стал самым знаменитым математиком средневековья.  Его книга открывала математические методы в торговле, но сейчас вспоминается, в основном, благодаря двум моментам. Один из них был явно важен в те времена, а второй казался незначительным.

Важный факт: он донес до внимания Европы индуистскую систему написания чисел. Европейские торговцы и ученые все еще цеплялись за использование старых римских цифр;  современная математика была бы невозможна без этого изменения на индуистскую систему, которую мы сейчас называем арабскими цифрами, так как эта система пришла на запад через арабские земли.

Другой интересный факт: в списке головоломок Фибоначчи стоит такой вопрос:

Если пара кроликов размещены в закрытом пространстве, сколько кроликов родится там, если мы допустим, что каждый месяц пара кроликов производит на свет еще одну пару, а кролики начинают приносить приплод через несколько месяцев после рождения?

Этот, на первый взгляд, простой вопрос имеет как ответ определённое количество чисел, ныне известное как последовательность Фибоначчи, одна из самых интереснейших за всё время. Она была заново открыта в невероятном разнообразии форм в областях математики, далеко за пределами простой арифметики. Ее метод развития привел к далекогрядущим приложениям в области математики и информатики.

Но еще более удивительным является появление чисел Фибоначчи и их относительных коэффициентов, далеких от логической структуры математики: в природе и искусстве, в классических теориях красоты и пропорциях.

Рассмотрим самый простой пример геометрического возрастания – бесполого размножения, как, например, у амебы. Каждый организм распадается на два после интервала времени созревания, характерного для определенного вида. Этот интервал меняется случайным образом, но в рамках некоего диапазона соответственно внешним условиям, таким как температура, наличие полезных веществ и так далее. Мы можем представить себе упрощенную модель, в которой при идеальных условиях, все амёбы распадаются после периода взросления.

Так, одна амёба становится двумя, две становятся четырьмя, потом 8, 16, 32 и так далее.

Мы получаем последовательность удвоения. Обратите внимание на рекурсивную формулу:

  • An =2An

Это, обычно, приводит к экспоненциальному росту, одной из характерных картин роста населения.

Теперь, в ситуации кролика Фибоначчи, есть фактор задержки; каждой паре необходимо какое-то время, чтобы вырасти. Таким образом, мы допускаем

  • время дозревания  = 1 месяц
  • время беременности = 1 месяц

Тут мы видим, что каждое поколение остаётся в рамках следующего и, помимо этого, каждая взрослая пара вносит пару детей. Число таких детских пар соответствует общему числу пар в предыдущем поколении. Символично

  • fn = количество пар во время месяца  n
  • fn = fn-1 + fn-2

Таким образом, мы получаем рекуррентную формулу, где каждое поколение определяется в терминах двух предыдущих поколений. Используя этот подход, мы можем последовательно вычислить  fn нужного количества поколений.

Таким образом, эта последовательность чисел 1,1,2,3,5,8,13,21,.. и рекурсивный способ построения до бесконечности есть решением головоломки Фибоначчи. Ничего сам Фибоначчи не могу предусмотреть, так это бесчисленного количества дополнительных задач, которые эти цифры и сам метод содержит в себе.

Его идея была более плодотворной, чем его кролики. Только лишь с точки зрения чистой математики – теории чисел, геометрии и так далее – сфера распространения его идеи была настолько масштабна, что целый профессиональный журнал был посвящен ему, Фибоначчи, ежеквартально.

Теперь давайте рассмотрим другую достаточно природную ситуацию, когда та же самая последовательность  «мистически» появляется. Возвращайтесь на 350 лет до 17-го столетия во Францию.

Блез Паскаль, молодой француз, учёный, который разрывается между геометрией и математикой и любовью к религии и теологии.  В одном из своих более мирских моментов он консультировался с одним профессиональным азартным игроком Шевальеде Мере Антуаном Гомбо. Шевалье задал Паскалю несколько вопросов про игру в кости и карты, а еще о правильном разделе выигрыша в незавершенной игре. Ответом Паскаля было изобретение абсолютно новой ветви математики, теории относительности. За эти годы, теория выросла в важный для науки, в том числе социальной, инструмент 20-го столетия. Его работа в большей степени опирается на набор чисел и теперь называется треугольником Паскаля.

Эта конфигурация имеет множество интересных и важных свойств:

  • Обратите внимание на лево-правую симметрию – это его собственное зеркальное отображение.
  • Обратите внимание на то, что в каждом рядке второе число подсчитывает ряды.
  • Обратите внимание на то, что в каждом ряду, 2-й+3-й подсчитывают количество чисел выше этой линии.

Есть бесконечные вариации на эту тему.

Далее обратите внимание на то, что происходит, когда мы складываем числа в каждом ряде – мы получаем нашу удвоенную последовательность.

Теперь для удобства визуального восприятия нарисуем треугольник, выровненный по левому краю. Сложите цифры разных диагоналей…

И мы получаем  1, 1, 2, 3, 5, 8, 13,… последовательность Фибоначчи!

Фибоначчи не мог знать про эту связь между его кроликами и теорией вероятностей – теории не существовало ее 400 лет после его открытия.

Что действительно интересно в последовательности Фибоначчи, так это то, что его модель возрастания каким-то таинственным образом соответствует силам сдерживания роста огромного количества природных динамических систем. Абсолютно аналогично воссозданию кроликов, давайте рассмотрим родовое дерево пчелы – так мы смотрим на предков, а не на потомков. В упрощённой репродуктивной модели самец пчелы вылупливается из неоплодотворенного яйца, а потому у него есть только один из родителей, в то время как самка вылупливается из оплодотворенного яйца и имеет двух родителей. 

Обратите внимание на то, что оно выглядит, как график кролика, но в обратном времени. Самцы предков в каждом поколении создают последовательность Фибоначчи, как в целом это делают предки по женской линии. По дереву вы можете увидеть, что в обществе пчёл доминируют самки.

Самые известные и самые красивые примеры появления последовательности Фибоначчи в природе встречаются в разных цветах и деревьях, как правило, связанных с какой-то спиральной структурой. Например, листья на стебле цветка или ветки дерева что растет по-спирали, по цепи спиралей, которые новые листья создают дальше.  Представьте: у вас в руке ветка. Сосредоточьте внимание на её листьях и начните их считать. Посчитайте листья, а также количество витков вокруг ветки, пока не вернётесь в положение, соответствующее первому по счету листику, но по спирали дальше, чем первый виток. Оба номера будут числами Фибоначчи.

Например, для грушевого дерева 8 будет число листьев и  3 число витков. Вот еще несколько примеров:

Ответвления семьи Фибоначчи

Дерево     Листочки Витки

Вяз             2      1

Вишня               3      2

Бук             3      1

Тополь               5      2

Плакучая ива 8       3

Груша              8       3

Мигдаль 13       8

Вы можете прогуляться по парку и отыскать эту схему на растений и кустах достаточно легко.

Множество цветов предлагают прекрасное подтверждение мистики Фибоначчи. Маргаритка имеет центральное ядро, которое складывается из крошечных цветочков, расположенных в противоположных спиралях. Как правило, 21 собирается слева и 34 справа. Астра может иметь 13 спиралей слева и 21 справа. Подсолнух является ярчайшим примером; у него 55 спиралей в одну сторону и 89 в другую, а у лучших сортов 89 и 144.

Сосновые шишки также строятся по спирали, маленькие обычно имеют 8 спиралей в одну сторону и 13 в другую.  Интереснее всего то, что ананас, который состоит из смежных шестиугольников, имеет три вида спирали в трёх измерениях. Есть 8 вправо, 13 влево и 21 по вертикали – в тройной последовательности Фибоначчи.

Почему так происходит? Почему матушка природа нашла эволюционно преимущество в организации растительных структур в виде спиральных форм последовательности Фибоначчи?

Четкого ответа на этот вопрос у нас нет. В 1875 году математик Визнер продемонстрировал математическую схему того, как спиральное расположение листьев на ветке в пропорциях Фибоначчи было эффективным способом собрать максимальное количество  солнечного света благодаря нескольким листочкам – он утверждал, что это наилучший способ. Но в последнее время профессор ботаники по фамилии Корнельский из университета имени Карла Никласа решил проверить эту гипотезу в своей лаборатории; он обнаружил, что практически любое рациональное расположение листьев имеет ту же самую способность поглощать солнечный свет. Поэтому, мы всё ещё не слишком уверены насчёт света.

Но если мы рассмотрим этот вопрос с точки зрения природных моделей роста, я думаю, мы сможем начать понимать наличие спиралей и связь между ними и последовательностью Фибоначчи.

Спирали возникают из свойства роста, что называется самоподобным масштабированием – тенденцией до разрастания в размерах, но с поддержанием той же формы. Не все микроорганизмы растут по этой схеме. Мы видели, как взрослые люди не являются более крупной копией детей в масштабе: у детей большие головы, короткие ноги и более длинный торс относительно всего роста.

Но если мы посмотрим на оболочку моллюска, мы увидим измененную модель возрастания. По мере того, как моллюск наращивает новый слой, он создает новые части себя, всегда той же самой формы – если представить себе очень долгоживущего моллюска, их оболочка будет создавать спираль по кругу, расширяться, но на каждом уровне будет выглядеть одинаково.

Вот, где возникает Фибоначчи – мы можем построить огромного моллюска, начиная с размера 1, последовательно создавать новые размеры, в соответствии с последовательностью Фибоначчи.

Запуск через центр с гладкой кривой даст нам спираль моллюска = подсолнуха по спирали.

Это особая спираль – содель кривой, которая сохраняет форму на всех уровнях ( если представить, что она бесконечна).  Её называют равноугольной, поскольку радиальная линия от центра всегда создает один и тот же угол кривой. Эта кривая была известна Архимеду в древней Греции, самому великому геометру всех времён.

Мы действительно должны думать об этой кривой как о спирали внутрь до бесконечности, также, как и наружу. Это сделать непросто; вы можете визуализировать циркуляцию воды вокруг крошечного сливного отверстия, который по спирали приближается к центру, но никогда не падает всередину. Этот эффект иллюстрируется классической загадкой:

Четыре жука стоят на четырёх углах квадрата. Они голодные (или одинокие) и в то же время каждый из них видит жука видит жука в другом углу и начинает ползти к нему. Что произойдет?

Картина рассказывает историю, как они ползут навстречу к друг другу по спирали в центр, постоянно создавая всё более маленькую площадь, вращаясь вокруг. И всё же они настигают друг друга! Это не парадокс, потому что длина этой спирали конечна. Они прослеживают ту же логарифмическую спираль.

Теперь, поскольку все спирали самоподобны, они выглядят одинаково в любом масштабе – масштаб не имеет значения. Важно, что эти спирали имеют фиксированную часть, определяющую их форму. Оказывается, что эта часть такая же, как пропорции последовательных записей Фибоначчи: 5:3, 8:5,13:8 и так далее. 

Пропорции Фибоначчи

По ходу того, как мы двигаемся дальше в последовательности, пропорции смежных терминов начинают приближаться к фиксированному граничному значению 1.618034… Это очень известное соотношение с долгой и уважаемой историей; золотая середин Эвклида и Аристотеля, божественная пропорция да Винчи считаются наикрасивейшими и наиважнешими понятиями. Это число имеет более интригующие свойства, чем Вы можете представить.

Путем простых вычислений мы видим, что если отнять 1, мы получим .618.. Если мы прибавим 1, мы получим 2.618… его площадь.

Используя эту золотую пропорцию за основу, мы можем построить чёткую формулу для чисел Фибоначчи.

Но у греков была своя визуальная точка зрения касательно золотой середины. Они задавали вопрос: какой самый природный и наиболее пропорционально выраженный способ разделить линию на две части? Они назвали это разделением. Греки четко понимали, что идеал должен соответствовать пропорциям между частным и целым. Это даёт точную пропорцию f.

Формирование прямоугольника с секциями линий придает визуально приятную форму, которая стала основой искусства и архитектуры. Эта эстетичная форма была принята выдающимися художниками эпохи Возрождения в живописи, и она всё ещё остаётся с нами сегодня.

Формування прямокутника з секціями лінії як сторонами надає візуально приємної форми, яка стала основою мистецтва й архітектури. Ця естетична форма була прийнята визначними художниками епохи Відродження в живописі, і вона все ще залишається з нами сьогодні.

Dan Reich (Ден Райх)

Математический факультет, Университет Темпл

Розмальовування графіка Макгрегора

У квітневому номері 1975 року, Мартін Гарднер — американський науковий співробітник у колонці «Математичні ігри» опублікував список 6 основних математичних відкриттів 1974 р, які «з тієї чи іншої причини були недостатньо висвітлені як науковому співтовариству, так і громадськості в цілому». Одним з них був планарний граф з 110 вузлів, приписаний Вільяму МакГрегору з Уонпінгерс Фолз, штат Нью-Йорк. За його твердженням, граф не можна було забарвлювати менш ніж 5 кольорами, тим самим спростовуючи ще не підтверджену гіпотезу про те, що 4 кольори було достатньо, аби намалювати будь-який плоский граф. Те, що багато читачів не оцінили, це був місяць публікації випуску. Детальніше про цю історію можна знайти тут.

Читать далее

Цена труда. Теория

Как это ни удивительно, но до настоящего времени находятся люди, разделяющие мнение Карла Маркса о том, что труд не товар, и поэтому у него цены нет. Так, автор одного из современных учебников по экономике труда утверждает буквально следующее: «Труд – это процесс, который объективно не может быть объектом купли-продажи» [2, с. 326]. Из чего автоматически следует вывод: ни цены, ни стоимости у труда быть не может!

Читать далее

Теория цены товара

Введение

Рассмотрим основные определения цены, циркулирующие в современном обществе, и укажем их главные недостатки. С позиций, разумеется, новой теории стоимости [4].

Определение первое: «Цена [price] – количество денег, уплачиваемых за единицу товара» [1].
Совершенно очевидно, что в такой трактовке цена отождествляется с количеством денег и мыслится, поэтому, как абсолютная величина. И это подтверждается всегда тем, что цену люди обычно измеряют только в единицах денег. И гораздо реже указывают правильные единицы – в виде отношения единиц денег к единицам товара.

Читать далее

Соотносительная теория стоимости

Введение

Предметом настоящей теории является меновая стоимость. В силу того, что в современной экономической науке нет единства мнений ни по одному из главных вопросов, вызываемых этим, казалось бы, простым объектом. Нет единого понимания ни в том, что такое есть меновая стоимость; ни в том, чем определяется ее величина.

Одни толкуют эту стоимость как «возможность приобретения других предметов, которую дает обладание данным» [3, с. 88]; другие – как «отношение между двумя вещами в конкретном месте и в конкретное время» [2, с. 120]. А третьим она  «представляется в виде количественного соотношения, в виде пропорции, в которой потребительные стоимости одного рода обмениваются на потребительные стоимости другого рода» [1, с. 44].

Читать далее