2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Минимальное количество методов.
Сообщение01.02.2018, 23:52 


03/02/16
91
Здравствуйте, помогите разобраться.

Михаил 20 раз решал задачи классификации. В каждой задаче он использовал ансамбль из пяти различных классификаторов, причем никакую пару классификаторов он не применял более одного раза. Каково минимально возможное число известных Михаилу классификаторов?

Мне кажется надо решать через графы. Пусть каждая вершина в графе - это классификатор. Ребро показывает, использовались ли 2 вершины в паре для решения задачи. Каждая решенная задача представляет собой полный подграф из 5 вершин. Значит, нужно подорать граф, состоящмй из 20 подграфов с минимальным количеством вершин. Дальше не знаю.

 Профиль  
                  
 
 Re: Минимальное количество методов.
Сообщение02.02.2018, 01:59 
Заслуженный участник


18/01/15
3073
Да нет, не через графы. Прямо-то решение писать нельзя. Попробуем то же, с уменьшенными параметрами.
Дано, что $X$ --- некоторое множество, $L_1,\ldots,L_6$ --- шесть его подмножеств, причем в каждом 3 элемента. Известно, что любая пара элементов $x,y\in X$ лежит или ровно в одном из подмножеств $L_1,\ldots,L_6$, или вообще ни в одном. Спрашивается, сколько при этом может быть элементов в $X$ (наименьшее возможное число)? Прикиньте так, чисто комбинаторно, поперебирайте различные варианты.

 Профиль  
                  
 
 Re: Минимальное количество методов.
Сообщение05.02.2018, 23:31 


03/02/16
91
Простите за глупость, но можно еще подсказок?
Я пытался работать с тем, что 2 элемента задают одну тройку, или посчитатть количесвто всех возможных троек и вычеркнуть все те, где пары повотряются.... Вобщем ни к чему я не пришел

 Профиль  
                  
 
 Re: Минимальное количество методов.
Сообщение06.02.2018, 00:43 
Заслуженный участник


18/01/15
3073
Жаль. Ну давайте еще проще. Пусть у нас есть всего три тройки, и мы знаем, что каждая пара лежит не более чем в одной тройке. Что тогда можно сказать о том, сколько элементов может быть в $X$?

-- 05.02.2018, 23:53 --

И еще попробуйте доказать такой общий факт. Пусть у нас во множестве $Y$ есть $a$ подмножеств, в каждом из них по $b$ точек, и известно, что каждая точка лежит не более чем в $c$ подмножествах. Тогда $|Y|\geq ab/c$.

 Профиль  
                  
 
 Re: Минимальное количество методов.
Сообщение15.02.2018, 12:39 


03/02/16
91
Простите за долгое отсутствие

vpb в сообщении #1290461 писал(а):
Жаль. Ну давайте еще проще. Пусть у нас есть всего три тройки, и мы знаем, что каждая пара лежит не более чем в одной тройке. Что тогда можно сказать о том, сколько элементов может быть в $X$?


Минимальное количество элементов $X$ - 6. Кажется

vpb в сообщении #1290461 писал(а):
И еще попробуйте доказать такой общий факт. Пусть у нас во множестве $Y$ есть $a$ подмножеств, в каждом из них по $b$ точек, и известно, что каждая точка лежит не более чем в $c$ подмножествах. Тогда $|Y|\geq ab/c$.


Я не уверен, как доказатать это строго, но если пердроложить что каждая точка принадлежит $c$ подмножествам, тогда количество точек равно $ab/c$, и это и есть минимально возможное количество точек

 Профиль  
                  
 
 Re: Минимальное количество методов.
Сообщение15.02.2018, 14:40 
Заслуженный участник


18/01/15
3073
an2ancan
рад что Вы продвигаетесь в решении.
an2ancan в сообщении #1292637 писал(а):
Минимальное количество элементов $X$ - 6. Кажется
Да. А как это доказывается?
an2ancan в сообщении #1292637 писал(а):
Я не уверен, как доказатать это строго, но если пердроложить что каждая точка принадлежит $c$ подмножествам, тогда количество точек равно $ab/c$, и это и есть минимально возможное количество точек
Не знаете, как доказать строго, попробуйте своими словами.

 Профиль  
                  
 
 Re: Минимальное количество методов.
Сообщение15.02.2018, 16:24 


03/02/16
91
vpb в сообщении #1292648 писал(а):
an2ancan в сообщении #1292637

писал(а):
Минимальное количество элементов $X$ - 6. Кажется Да. А как это доказывается?


Ну по формуле включений-исключений:

$\left\lvert X \right\rvert = 3 \cdot 3 - \sum\limits_{i\ne j} (a_i \cap a_j)$

Масксимальное количество пересечений из 3 элементов:

$C_3^2  = 3$

Выходит, что $\left\lvert X \right\rvert = 6$

vpb в сообщении #1292648 писал(а):
Не знаете, как доказать строго, попробуйте своими словами.


vpb в сообщении #1292648 писал(а):
если пердроложить что каждая точка принадлежит $c$ подмножествам, тогда количество точек равно $ab/c$, и это и есть минимально возможное количество точек

 Профиль  
                  
 
 Re: Минимальное количество методов.
Сообщение15.02.2018, 18:22 
Заслуженный участник


18/01/15
3073
an2ancan в сообщении #1292669 писал(а):
Ну по формуле включений-исключений
Да, в данном случае можно так. Однако, формула включений исключений, вообще говоря, дает не равенство, а неравенство (каламбур получился...). В полном виде она выглядит как
$ |\cup_i X_i|=\sum_i|X_i|-\sum_{i<j}|X_i\cap X_j|+\sum_{i<j<k}|X_i\cap X_j\cap X_k|-\ldots $,
что в нашем случае приводит к неравенству
$|X|\geq |L_1\cup L_2\cup L_3|=\sum_i|L_i|-\sum_{i<j}|L_i\cap L_j|+|L_1\cap L_2\cap L_3|$,
откуда $|X|\geq 6$. Однако это рассуждение не доказывает, что конфигурация, для которой $|X|=6$, действительно существует (так что может быть в принципе, что минимальное возможное значение для $|X|$ --- это $7$, $8$, или что-то еще больше). Можете Вы предъявить такую конфигурацию в явном виде?

По второму вопросу Вы, собственно, ничего не написали, просто еще раз повторили то же утверждение (к тому же с опечатками, чего желательно избегать). Пока, пожалуй, оставим этот вопрос.

Скажите еще, а Вы какие-нибудь книжки по дискретной математике, комбинаторике и т.д. когда-нибудь читали? Если да, то какие?

 Профиль  
                  
 
 Re: Минимальное количество методов.
Сообщение15.02.2018, 23:09 


03/02/16
91
Ну коогда я читал Виленкина "Комбинаторика". )
vpb в сообщении #1292693 писал(а):
Можете Вы предъявить такую конфигурацию в явном виде?


Боюсь, что нет ( .

 Профиль  
                  
 
 Re: Минимальное количество методов.
Сообщение16.02.2018, 01:50 
Заслуженный участник


18/01/15
3073
Вопрос очень простой (настолько простой, что, как говорится, дальше некуда). Возможно, Вы просто не понимаете, в чем задача? Переформулирую ее другими словами. Рассмотрим множество $X=\{1,2,3,4,5,6\}$. Требуется указать какой-нибудь пример трех подмножеств $L_1, L_2,L_3\subseteq X$ таких, что $|L_1|=|L_2|=|L_3|=3$ и каждое из пересечений $|L_1\cap L_2|$, $|L_1\cap L_3|$, $|L_2\cap L_3|$ содержит не более одной точки.

В Виленкине того, что нужно, увы, нет. Я, возможно, еще кое-что из литературы поищу, что имеет отношение к задаче.

 Профиль  
                  
 
 Re: Минимальное количество методов.
Сообщение16.02.2018, 07:56 


03/02/16
91
Да,простите, я не понял вопроса. Пример такой конфигурации:

$123$
$145$
$356$

 Профиль  
                  
 
 Re: Минимальное количество методов.
Сообщение16.02.2018, 15:25 
Заслуженный участник


18/01/15
3073
Да, правильно. Попробуйте решить аналогичную задачу (т.е., каково минимальное $|X|$) для случая 4-х троек, тоже посредством рассмотрения разных конфигураций (при этом формула включений-исключений, возможно, не понадобится. Она тут, вообще говоря, ни при чем).

 Профиль  
                  
 
 Re: Минимальное количество методов.
Сообщение16.02.2018, 15:42 


03/02/16
91
Тоже 6

$123$
$145$
$356$
$246$

 Профиль  
                  
 
 Re: Минимальное количество методов.
Сообщение16.02.2018, 17:29 
Заслуженный участник


18/01/15
3073
Да, правильно. Теперь рассмотрите случай 5 троек.

 Профиль  
                  
 
 Re: Минимальное количество методов.
Сообщение17.02.2018, 11:18 


03/02/16
91
7 элементов:

$123$
$456$
$147$
$257$
$367$

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 23 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: YandexBot [bot]


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group