801

Re: Шлях на математичну вершину

zearn.org - безкоштовний інтерактивний курс з математики від дитячого садка до ~8 класу.
Щоб було безкоштовно, потрібно ведучому класу вказати що він/вона - parent.

802

Re: Шлях на математичну вершину

FakiNyan написав:
lucas-kane написав:

Для того, щоб переставити елементи місцями, їх потрібно порівняти. Ось це порівняння може давати 2 випадки (a>b) або (a<b). А f(n) - кількість кроків до завершення алгоритму... Ось тобі і 2^f(n) >= n!

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

Що оте 2^f(n) взагалі таке? От нехай у нас є бульбашкове сортування, маємо 5 елементів, і 25 кроків, бо O(n^2). Якщо це 5 відмінних елементів, то загальна кількість пермутацій 120, бо 5!. 2^25 - це дофіга, але дофіга чого саме?

Так точно вирахувати, як ти хочеш так не вийде (це так не працює). Шукай за темами BIG O (Дональд Кнут), оцінка складності алгоритмів, аналіз алгоритмів

803

Re: Шлях на математичну вершину

FakiNyan написав:
lucas-kane написав:

Для того, щоб переставити елементи місцями, їх потрібно порівняти. Ось це порівняння може давати 2 випадки (a>b) або (a<b). А f(n) - кількість кроків до завершення алгоритму... Ось тобі і 2^f(n) >= n!

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

Що оте 2^f(n) взагалі таке? От нехай у нас є бульбашкове сортування, маємо 5 елементів, і 25 кроків, бо O(n^2). Якщо це 5 відмінних елементів, то загальна кількість пермутацій 120, бо 5!. 2^25 - це дофіга, але дофіга чого саме?

Можливих результатів порівнянь. Насправді, як ви правильно зауважили, їх менше, але це тільки тому, що там є зайві.
Спробую так це описати. Є алгоритм сортування, який використовує функцію для порівняння. Нехай функція не просто повертає bool (менше чи ні), а записує цей bool - що в файл, що на екран. І там виникає послідовність True/False чи 1/0. Кожна послідовність однозначно описує процес сортування. Скільки таких послідовностей може бути в принципі? 2^(довжина послідовності). Ось про це мова.

Подякували: mamkin haker, FakiNyan2

804

Re: Шлях на математичну вершину

оцей чувак детально пояснив, там навіть інтеграли використовуються (щоб знайти  n log n)
https://www.youtube.com/watch?v=WffUZk1pgXE

Подякували: mamkin haker, leofun012

805

Re: Шлях на математичну вершину

Numberphile - Нове відкритя про 12и_гранник (видиво, en)
Подякували: P.Y.1

806

Re: Шлях на математичну вершину

FakiNyan написав:

Хтось оце може пояснити мені, як вони порахували найменшу необхідну кількість операцій для сортування масиву з унікальними числами?

Тут вони кажуть, що це буде n*log_2(n).
..

Знайшли відповідь? поділіться з іншими, може комусь згодиться.

звідки вони взяли те  2^(f(n))

Не знаю їх ланцюжок роздумів і як її використовують, але сама функція не важка. Це відображення n -> m, де кількість можливих результатів - n^m, 2^(f(n)).
Якщо на пальцях : у вас є два унікальних значення (ліво - право, або (0,1)). Необхідно знайти скільки можливих комбінацій (0,1) довжино 2 : (0,0),(0,1),(1,0),(1,1). тобто 2^2=4, якщо довжина 3 то 2^3=8, (0,0,0),(0,0,1)..ітд.

До цієї кількості операцій можна спробувати дійти самому якщо спробувати реалізувати один з алгоритмів сортування(merge, quick..).
Якщо сортувати бульбашкою масив розміром n, то там один цикл n в іншому циклі n (є деяка оптимізація в кінці, але то таке..) тому його швидкість(швидше повільність) буде О(n^2).
Уявімо що ви хочете відсортувати масив в два рази більше, значить швидкість буде О((2n)^2)=О(4n^2), а чи не простіше 2 рази відсортувати зліва і зправа, щоб операцій було хоч не в 2 рази більше але точно не в 4?! Є такі алгоритми, і в ідеальному випадку вони працюють наче на повному бінарному дереві (завжди відбувається розбиття і в ідеальному випадку на середині (вибір pivot у quick)).
А як ми знаємо, якщо в повному бінарному дереві n елементів, то глибина дерева буде log_2(n).
Ось звідки взялось n*log_2(n).

Подякували: leofun011

807

Re: Шлях на математичну вершину

Квадрат можна нарізати так щоб з отриманих частин зібрати круг, і наоборот. Я не знав що таке взагалі можливо.

Passe-Science - нова не періодична плитка (видиво, fr)

808

Re: Шлях на математичну вершину

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

math.ucla.edu - Квадратура круга Бореля (сторінка, en)

І знайшов видиво, де детально пояснено як вдалось побудувати такий роклад :

Passe-Science - Квадратура круга Тарського з демо (видиво, fr)

809

Re: Шлях на математичну вершину

Послідовність Морзе-Туе 01101001.. - не очікував побачити там дзета-функцію.. гарний результат.
https://wikimedia.org/api/rest_v1/media/math/render/svg/c86839ac7944330fb8b82dbdd6c87ae80f99f6f2