Обговорення користувача:Тарас Огар

Ласкаво просимо!

Основні засади Вікіпедії	Ласкаво просимо до україномовної Вікіпедії, Тарас Огар!
Для чого ми розвиваємо Вікіпедію	Вітаємо Вас як нового учасника україномовного розділу Вікіпедії. Сподіваємось на плідну співпрацю з Вами над спільним відкритим проєктом. Зверніть увагу на наріжні принципи участі: сміливо редагуйте, а в конфліктних ситуаціях, якщо такі виникнуть, завжди розраховуйте на добрі наміри опонента. Можете скористатися шпаргалкою, якщо Ви ще не знайомі з основами вікірозмітки. Якщо виникли запитання щодо проєкту або потрібні якісь підказки, пошукайте відповідь на сторінці Довідки. Якщо відповіді на Ваше питання там немає, поставте його у нашій Кнайпі чи комусь із постійних дописувачів. Кнопка вставки підпису у вікні редагування На сторінках обговорень бажано ставити автоматичний підпис за допомогою чотирьох тильд (~~~~) або за допомогою позначки підпису у вікні редагування (зображено на малюнку). У статтях, написаних або редагованих Вами, підпис не ставиться. Ви також можете розповісти про свої інтереси на сторінці інтересів користувачів. Якщо у Вас виникнуть додаткові питання, можете звернутися за порадою до будь-якого користувача з цієї категорії. Бажаємо успіхів та якнайбільше творчого задоволення! Irrespective of your language skills, you are welcome to create your own user page, add interwiki links, upload images, correct data, discuss problems, communicate & cooperate with the community. Please, use language templates from Вікіпедія:Вавилон or create your own ones. You can ask for our help on the Community Portal (help).
Як створити статтю
Як редагувати статті
Ілюстрування статей
Потренуйтеся тут!
Правила і настанови
Стиль оформлення статей
Авторські права
Довідка
Користувачі, що допоможуть Вам
Словничок вікітермінів

-- Automatic welcomer (обговорення) 18:35, 20 жовтня 2015 (UTC)

Стаття Комбінаторний аналіз

Шановний користувачу! Дякуємо, що ви зробили свій внесок до Вікіпедії, створивши статтю Комбінаторний аналіз. Проте ця стаття надто мала та/або недооформлена, щоби бути повноцінною енциклопедичною статтею. Якщо протягом трьох днів її не буде суттєво поліпшено (хоча б до рівня статті-заготовки), статтю буде вилучено. Якщо ви маєте намір доробити статтю, приберіть зі статті шаблон-попередження та поставте шаблон {{Edited}}. Із запитаннями можете звертатися до мене. — Zvr (обговорення) 14:06, 28 жовтня 2015 (UTC)

Фільтр очікує, що у користувача принаймн 10 редагувань. Додав виняток, спробуйте тепер. Про всяк випадок додаю сюди також втрачений текст.

Довге обговорення

Комбінаторний аналіз Комбінаторика (Комбінаторний аналіз) - розділ математики, що вивчає дискретні об'єкти, множини (перестановки , розміщення і перелік елементів) і відносини на них (наприклад, часткового порядку). Комбінаторика пов'язана з багатьма іншими областями математики - алгеброю, геометрією, теорією ймовірностей і має широкий спектр застосування в різних галузях знань (наприклад, в генетиці, інформатиці, статистичній фізиці). Термін «комбінаторика» був введений в математичний ужиток Лейбніцем, який в 1666 році опублікував свою працю «Міркування про комбінаторне мистецтво». Іноді під комбінаторикою розуміють більш великий розділ дискретної математики, що включає, зокрема, теорію графів. Приклади комбінаторних конфігурацій і завдань Для формулювання і розв'язання комбінаторних задач використовують різні моделі комбінаторних конфігурацій. Прикладами таких конфігурацій є: Розміщенням з n елементів по k називається упорядкований набір з k різних елементів деякого n -елементного множини. Перестановкою з n елементів (наприклад чисел 1,2, ..., n) називається всякий упорядкований набір з цих елементів. Перестановка також є розміщенням з n елементів по n. Поєднанням з n по k називається набір k елементів, вибраних з даних n елементів. Набори, що відрізняються тільки порядком проходження елементів (але не складом), вважаються однаковими, цим поєднання відрізняються від розміщень. Композицією числа n називається всяке уявлення n у вигляді впорядкованої суми цілих позитивних чисел. Розбиттям числа n називається всяке уявлення n у вигляді невпорядкованою суми цілих позитивних чисел. Приклади задач з комбінаторики: Скількома способами можна розмістити n предметів за m скриньках, щоб виконувалися задані обмеження? Скільки існує функцій F з m -елементного безлічі в n -елементне, що задовольняють заданим обмеженням? Скільки існує різних перестановок з 52 гральних карт? Відповідь: 52! (52 факторіал), тобто, 80658175170943878571660636856403766975289505440883277824000000000000 або приблизно 8,0658 × 1067. При грі в кості кидаються дві кістки, і випали окуляри складаються; скільки існує комбінацій, в яких сума очок на верхніх гранях дорівнює дванадцяти? Рішення: Кожен можливий результат відповідає функції F: {1, 2 } to {1, 2, 3, 4, 5, 6} (аргумент функції - це номер кістки, значення - окуляри на верхній грані). Очевидно, що лише 6 + 6 дає нам потрібний результат 12. Таким чином, існує лише одна функція, яка ставить у відповідність 1 число 6, і 2 число 6. Або, іншими словами, існує всього одна комбінація, при якій сума очок на верхніх гранях дорівнює дванадцяти. Комбінаторні задачі У комбінаториці є декілька задач, які вирішуються послідовно одна за одною. Перша з них спочатку формулює вимоги до класу комбінаторних конфігурацій, які потрібно побудувати. Доводиться, що хоча б одна така конфігурація існує, попри те, що побудувати таку конфігурацію може бути досить непросто. Тому інколи буває достатньо теоретичного доведення її існування. Після розв'язання першої задачі комбінаторного аналізу розв'язується не менш важлива друга — задача переліку комбінаторних об'єктів, які відповідають вихідним правилам їх побудови. Саме на розв'язання цієї задачі спрямовані сьогодні зусилля багатьох учених. Є досить багато задач, які так чи інакше стосуються цієї загальної задачі. Наприклад, до неї належить питання про кількість різних способів, якими можна розмістити групу студентів з 30 чоловік на 30 чи більше місцях, або про кількість способів проведення матчів з футболу між 10 різними командами? Далі на основі отриманих розв'язків конкретних задач з переліку комбінаторних об'єктів розв'язується третя задача комбінаторики — це її побудова. Наприклад, потрібно не лише підрахувати кількість можливих варіантів розподілу 30 студентів на 30 місцях, а й побудувати всі ці розподіли або деякі з них у вигляді їх конфігурацій. Також може виникнути потреба побудувати таблицю матчів між 10 футбольними командами, а не тільки знати їх кількість. Четверта і остання задача комбінаторики — це задача про пошук серед комбінаторних конфігурацій такої, яка б приводила деяку функцію до оптимуму. Це на сьогодні досить нелегка для розв'язання загальна задача. Вона містить задачі комбінаторної оптимізації, наприклад, задачу комівояжера, яка на сьогодні ще не має остаточного розв'язання. Правило суми В основі розв'язання багатьох задач комбінаторики лежать два простих правила — правило суми та правило добутку. Правило суми стверджує, що якщо є можливість вибрати елемент з деякої множини елементів А n способами, а елемент з множини В, яка не має спільних елементів з множиною А, — k способами, то вибрати елемент множини А або елемент множини В можна n+k способами. Це правило зручно продемонструвати з допомогою такої моделі. Якщо маємо дві урни і в одній з них знаходиться n куль, а в іншій k, то кількість способів, якими можна буде вийняти кулю з тієї чи іншої урни, дорівнюватиме n+k. Дійсно, з першої урни кулю можна вийняти n способами, але якщо з першої урни кулю не виймати, то тоді з другої урни її можна вийняти k способами. Тому загальна кількість способів, якими можна вийняти одну кулю з двох урн, буде дорівнювати n+k. У загальному випадку правило суми може бути сформульоване таким чином. Якщо треба виконати якусь дію n1 , n2 ,… або nk способами, то кількість можливих способів реалізації цієї дії буде дорівнювати N = n1 +n2 +… + nk. Особливістю цього правила є те, що воно використовує сполучник або, який протиставляє різні дії одна одній. Приклад 1. На денне чергування в студентському гуртожитку може піти або студент з кімнати 1, де проживають три студенти, або студент з кімнати 2, де проживають чотири студенти. Скількома способами можна вибрати одного студента на денне чергування в гуртожитку? Розв'язання. Загальна кількість способів, якими можна вибрати одного студента або з кімнати 1 або з кімнати 2 на денне чергування, згідно з правилом суми буде 3+4=7. Правило добутку Правило добутку використовується тоді, коли кожний елемент множини А може бути вибраний разом з елементом множини В. Відповідно до кожного способу вибору елемента множини А буде зіставлятися k способів вибору елемента множини В. Тоді загальна кількість способів сумісного вибору елементів множини А з елементами множини В, очевидно, дорівнюватиме n\cdot k. Модель урн можна застосувати і для ілюстрації правила добутку. У цьому випадку розглядаються дві урни, у першій з яких знаходиться n куль, а в другій k. Будемо вважати, що будь-якій кулі першої урни може відповідати будь-яка куля з другої урни. А оскільки в першій урні знаходиться n куль, то й кількість способів вибору куль з першої урни разом з різними кулями з другої урни буде дорівнювати n\cdot k. У загальному вигляді правило Добутку буде мати такий вигляд. Якщо треба виконати якусь дію, що може бути виконана к сумісними діями, перша з яких може бути виконана n1 способами, друга — n2 і т. д. до к — ої дії, яку можна виконати nk способами, то основна дія може бути виконана М способами, де М =n1•n2 •…•nk. У цьому правилі важливу роль відіграє сполучник і, який об'єднує різні дії в одну. Приклад 2. На денне чергування в студентському гуртожитку вибирається два студента — один студент з трьох, що проживають у кімнаті 1, і один студент з чотирьох, які проживають у кімнаті 2. Скільки існує можливих способів формування різних пар з двох студентів для чергування? Розв'язання. Кількість способів чергувань двох студентів з різних кімнат відповідно до правила добутку буде 3*4=12. Розділи комбінаторики Перелічувальна Перелічувальна комбінаторика (або обчислювальна комбінаторика) розглядає завдання про перерахування або підрахунку кількості різних конфігурацій (наприклад, перестановок) утворених елементами кінцевих множин, на які можуть накладатися певні обмеження, такі як: розрізненість або нерозрізненість елементів, можливість повторення однакових елементів і т. п. Кількість конфігурацій, утворених декількома маніпуляціями над безліччю, підраховується згідно з правилами складання і множення. Типовим прикладом завдань даного розділу є підрахунок кількості перестановок. Інший приклад - відома Завдання про листах. Структурна До даного розділу відносяться деякі питання теорії графів, а також теорії матроідов. Екстремальна Прикладом цього розділу може служити наступна задача: яка найбільша розмірність графа, що задовольняє певним властивостям. Теорія Рамсея Теорія Рамсея вивчає наявність регулярних структур у випадкових конфігураціях елементів. Прикладом твердження з теорії Рамсея може служити наступне: в групі з 6 чоловік завжди можна знайти трьох осіб, які або попарно знайомі один з одним, або попарно незнайомі. У термінах структурної комбінаторики це ж твердження формулюється так: в будь-якому графі з 6 вершинами знайдеться або кліка, або незалежне безліч розміру 3. Імовірнісна Цей розділ відповідає на питання виду: яка ймовірність присутності певної властивості у заданої множини. Топологічна Застосовує ідеї та методи комбінаторики в топології, при вивченні дерева прийняття рішень, частково впорядкованих множин, розмальовок графа та ін. Інфінітарна Застосування ідей і методів комбінаторики до нескінченним (у тому числі, незліченну) множинам. Відкриті проблеми Комбінаторика, і зокрема, теорія Рамсея, містить багато відомих відкритих проблем, часом з вельми нескладної формулюванням. Наприклад, невідомо, при якому найменшому N в будь-якій групі з N чоловік знайдуться 5 осіб, або попарно знайомих один з одним, або попарно незнайомих (хоча відомо, що 49 людина достатньо). [1] Історія Джироламо Кардано написав математичне дослідження гри в кості, опубліковане посмертно. Теорією цієї гри займалися також Тарталья і Галілей. В історію зароджувалась теорії ймовірностей увійшла листування запеклого гравця шевальє де Мере з П'єром Ферма і Блез Паскаль, де були порушені кілька тонких комбінаторних питань. Крім азартних ігор, комбінаторні методи використовувалися (і продовжують використовуватися) в криптографії - як для розробки шифрів, так і для їх злому. Блез Паскаль багато займався біноміальними коефіцієнтами і відкрив простий спосіб їх обчислення: «трикутник Паскаля». Хоча цей спосіб був уже відомий на Сході (приблизно з X століття), Паскаль, на відміну від попередників, суворо виклав і довів властивості цього трикутника. Поряд з Лейбніцем, він вважається основоположником сучасної комбінаторики. Сам термін «комбінаторика» придумав Лейбніц, який в 1666 (йому було тоді 20 років) опублікував книгу «Міркування про комбинаторном мистецтві». Правда, термін «комбінаторика» Лейбніц розумів надмірно широко, включаючи в нього всю кінцеву математику і навіть логіку [2]. Учень Лейбніца Якоб Бернуллі, один із засновників теорії ймовірностей, виклав у своїй книзі «Мистецтво припущень» (1 713) безліч відомостей з комбінаторики. У цей же період формується термінологія нової науки. Термін «поєднання» (combination) вперше зустрічається у Паскаля (1653, опублікований в 1665). Термін «перестановка» (permutation) вжив у зазначеній книзі Якоб Бернуллі (хоча епізодично він зустрічався і раніше). Бернуллі використовував і термін «розміщення» (arrangement). Після появи математичного аналізу виявилася тісний зв'язок комбінаторних і низки аналітичних завдань. Абрахам де Муавр і Джеймс Стірлінг знайшли формули для апроксимації факторіала. [3] Остаточно комбінаторика як самостійний розділ математики оформилася в працях Ейлера. Він детально розглянув, наприклад, такі проблеми: задача про хід коня; задача про сім мостах, з якої почалася теорія графів; побудова греко-латинських квадратів; узагальнені перестановки. Крім перестановок і сполучень, Ейлер вивчав розбиття, а також поєднання і розміщення з умовами. Комбінаторика в мовознавстві Комбінаторика (мовознавство) - це властивість одиниць мови і відповідних їм одиниць мовлення вступати в синтагматичні відносини, тобто у відносини сполучуваності. Примітки ↑ Weisstein, Eric W. Числа Рамсея (англ.) На сайті Wolfram MathWorld. ↑ Виленкин Н. Я., 1975, с. 19 ↑ O'Connor, John; Edmund Robertson. Abraham de Moivre. The MacTutor History of Mathematics archive (06 2004). Література Андерсон Джеймс. Дискретна математика і комбінаторика = Discrete Mathematics with Combinatorics. - М.: «Вільямс», 2006. - С. 960. - ISBN 0-13-086998-8. Виленкин Н.Я. Популярна комбінаторика. - М.: Наука, 1975. Ерош І. Л. Дискретна математика. Комбінаторика - СПб .: СПбГУАП, 2001. - 37 c. Липський В. Комбінаторика для програміста. - М.: Світ, 1988. - 213 с. Раізер Г. Дж. Комбінаторна математика. - Пров. з англ. - М., 1966. Райгородский А. М. Лінійно-алгебраїчні і імовірнісні методи в комбінаториці. - Літня школа «Сучасна математика». - Дубна, 2006. Рейнгольд Е., Нівергельт Ю., Део Н. Комбінаторні алгоритми. Теорія і практика. - М.: Світ, 1980. - 476 с. Ріордан Дж. Введення в комбінаторний аналіз. - Пров. з англ. - М., 1963. Р. Стенлі. Перечислительную комбінаторика = Enumerative Combinatorics. - М.: «Мир», 1990. - С. 440. - ISBN 5-03-001348-2. Р. Стенлі. Перечислительную комбінаторика. Дерева, виробляють функції і симметрические функції = Enumerative Combinatorics. Volume 2. - М.: «Мир», 2009. - С. 767. - ISBN 978-5-03-003476-8.

--ASƨɐ 20:19, 29 жовтня 2015 (UTC)

Стаття Теорія алгоритмів

Тарасе, щиро дякую за ваш внесок. Проте, хотів би зазначити, що при написанні статей варто одразу ж додавати посилання на джерела інформації, бо інакше вони забуваються, а статті в результаті виходять не такими добрими, як могли б. Будь ласка, користуйтесь тегом <ref> та відповідними шаблонами ({{cite book}}, {{cite journal}}, {{cite web}}). Дякую!--vityok (обговорення) 12:47, 19 травня 2016 (UTC)