Российские распределенные вычисления на платформе BOINC
Форум участников распределённых вычислений.

Добро пожаловать, Гость! Чтобы использовать все возможности Вход или Регистрация.

Уведомление

Icon
Error

15 Страницы«<1112131415>
Опции
К последнему сообщению К первому непрочитанному
Offline MikeVentris  
#241 Оставлено : 15 апреля 2012 г. 10:14:18(UTC)
MikeVentris


Статус: Старожил

Группы: Member
Зарегистрирован: 18.10.2010(UTC)
Сообщений: 512
Мужчина
Откуда: Санкт-Петербург

Сказал «Спасибо»: 79 раз
Поблагодарили: 48 раз в 34 постах
Автор: evatutin Перейти к цитате
Автор: MikeVentris Перейти к цитате

Множество не может содержать в себе одинаковых элементов. Ваш К.О.


Этого вроде в описании нет. Откуда вы взяли?

Из определения понятия множество smile Если элементы могут повторяться - это уже мультимножество, разве нет?

Автор: Freddykrug Перейти к цитате
Автор: MikeVentris Перейти к цитате

Где ваша толерантность! Может быть именно это кому-то и нравится. BOINC всегда радовал разнообразием, пускай радует и дальше.
А причем тут привыкание к повышению дозы лекарств?
Это, типа, шутка? Если что, я имел в виду социологическое значение слова "толерантность".

Автор: Freddykrug Перейти к цитате

Автор: MikeVentris Перейти к цитате
BOINC всегда радовал разнообразием, пускай радует и дальше.
Разнообразие бывает разное. Конечно, можно тянуть кайф от расшифровки телеграмм в Энигме, но вопрос стоит опять-таки: "Зачем?" Эти телеграммы, скорее всего, даже исторического интереса не представляют. Вот и смысла в этих фазанах я не вижу.

Ключевые слова "смысла в этих фазанах я не вижу". А кто-то видит. Это и есть разнообразие - любой, даже очень далекий от физики, математики, техники и счастливого будущего, может найти в РВ то, что ему нравится. Вас-то никто не заставляет его считать. Не хотите - не надо. Но смеяться над наличием возможности - не стоит.
Offline evatutin  
#242 Оставлено : 15 апреля 2012 г. 13:01:54(UTC)
evatutin


Статус: Старожил

Медали: Первооткрывателю: Результат в проекте SAT@homeРазработчику: За организацию проекта Gerasim@home

Группы: Editors, Member
Зарегистрирован: 08.06.2010(UTC)
Сообщений: 3,622
Откуда: Russia, Kursk

Сказал(а) «Спасибо»: 1015 раз
Поблагодарили: 1788 раз в 874 постах
MikeVentris
Ну это уже игра слов smile. "Set" можно перевести и как набор, а в наборе элементы могут повторяться. Немного правильнее говорить вектор, но в векторе важен порядок следования элементов, а тут он не важен. Мне кажется, что совпадения или отличия элементов не добавляют существенных особенностей к задаче, хотя лучше всего спросить напрямую у разработчиков проекта.

ЗЫ. А еще есть матаппарат r-выборок (см. слайд), в нем все определяется более строго и без игры слов. В приведенном примере перечисляются разные r-выборки из 3 по 2, а в данной задаче надо перебрать неупорядоченные r-выборки без повторений из n по 1, из n по 2, ..., из n по n в итоге, найти для каждой из них сумму и проверить ее совпадение с t. Перебор можно ограничить, как я уже писал выше...
Пользователь evatutin прикрепил следующие файлы:
r.png

kvt.kurskstu team founder
Gerasim@home scientist
My numbers are 5056994653507584 and 1835082219864832081920. Why not? smile
Offline citerra  
#243 Оставлено : 15 апреля 2012 г. 14:08:32(UTC)
citerra


Статус: Старожил

Медали: Первооткрывателю: Нахождение пар ОДЛК в RakeSearch!Донор: За финансовую помощь сайту

Группы: Editors, Member, Russia Team Group, Moderators
Зарегистрирован: 02.10.2007(UTC)
Сообщений: 2,265

Сказал(а) «Спасибо»: 486 раз
Поблагодарили: 341 раз в 248 постах
Автор: MikeVentris Перейти к цитате
Из определения понятия множество smile Если элементы могут повторяться - это уже мультимножество, разве нет?

Видимо есть строгое определение понятия "множество", где четко различаются множество и мультимножество. А есть, наверно, "размытое" понятие "множество".
Так в задаче о рюкзаке нет ограничения на уникальность предметов. Или м.б в таком случае тоже надо строго говорить мультимножество.
В SubsetSum@Home имеет смысл говорить о разных числах.
Offline evatutin  
#244 Оставлено : 15 апреля 2012 г. 14:37:48(UTC)
evatutin


Статус: Старожил

Медали: Первооткрывателю: Результат в проекте SAT@homeРазработчику: За организацию проекта Gerasim@home

Группы: Editors, Member
Зарегистрирован: 08.06.2010(UTC)
Сообщений: 3,622
Откуда: Russia, Kursk

Сказал(а) «Спасибо»: 1015 раз
Поблагодарили: 1788 раз в 874 постах
citerra
Цитата:
Видимо есть строгое определение понятия "множество", где четко различаются множество и мультимножество


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

Цитата:
А есть, наверно, "размытое" понятие "множество"

В нечеткой логике есть нечеткие множества, только к поставленной задаче это не относится smile

All
В общем если в олимпиаду вы играть не хотите, вот решение. Входные данные я не проверяю на уникальности, поэтому хотите — вводите множество, не хотите — вводите мультимножество smile

kvt.kurskstu team founder
Gerasim@home scientist
My numbers are 5056994653507584 and 1835082219864832081920. Why not? smile
Offline Шмяка  
#245 Оставлено : 15 апреля 2012 г. 14:55:12(UTC)
Шмяка


Статус: Старожил

Медали: Роза: Девчатам от доброго сердца

Группы: Member, Crystal Dream Group
Зарегистрирован: 08.02.2012(UTC)
Сообщений: 1,862
Женщина
Российская Федерация
Откуда: Везде, куда ни занесет

Сказала «Спасибо»: 841 раз
Поблагодарили: 438 раз в 238 постах
а все таки тут мысль дельная была насчет если сумма указана нечетная а все элементы четные и если это сразу проверять то от некоторой немалой доли переборов можно избавиться.

(+) а линейки глобомба они где то от этой задачи недалеко вроде? по смыслу если?
◕‿‿◕ Мяяяяяу!!! ◕‿‿◕ godville.net/gods/Шмяка ◕‿‿◕ MIUKA.mybrute.com ◕‿‿◕

UserPostedImage

Offline evatutin  
#246 Оставлено : 15 апреля 2012 г. 15:13:11(UTC)
evatutin


Статус: Старожил

Медали: Первооткрывателю: Результат в проекте SAT@homeРазработчику: За организацию проекта Gerasim@home

Группы: Editors, Member
Зарегистрирован: 08.06.2010(UTC)
Сообщений: 3,622
Откуда: Russia, Kursk

Сказал(а) «Спасибо»: 1015 раз
Поблагодарили: 1788 раз в 874 постах
Шмяка
Переборные комбинаторные задачи все недалеко друг от друга. И внешне они очень похожи и перебором решаются, только вот при детальном анализе оказывается, что некоторые из них имеют быстрые полиномиальные алгоритмы решения — это класс P, а другие — не имеют и решаются только перебором — класс NP. А есть задачи, для которых до сих пор неизвестно, P они или NP. Еще есть открытый вопрос о равенстве классов P и NP... smile

Например, если есть страна с городами и дорогами, в которой необходимо найти кратчайший путь между заданной парой городов — это задача класса P, решается алгоритмом Дейкстры. А если надо обойти все города кратчайшим образом и вернуться в исходный — это уже NP и быстро не решается. Хотя внешне они очень схожи smile

ЗЫ. Однажды мне довелось быть на лекции Стефана Бойда, где он показывал аналогичные примеры в теории управления: внешне задачи схожи, но решаются за существенно различное время

kvt.kurskstu team founder
Gerasim@home scientist
My numbers are 5056994653507584 and 1835082219864832081920. Why not? smile
Offline Шмяка  
#247 Оставлено : 15 апреля 2012 г. 15:22:07(UTC)
Шмяка


Статус: Старожил

Медали: Роза: Девчатам от доброго сердца

Группы: Member, Crystal Dream Group
Зарегистрирован: 08.02.2012(UTC)
Сообщений: 1,862
Женщина
Российская Федерация
Откуда: Везде, куда ни занесет

Сказала «Спасибо»: 841 раз
Поблагодарили: 438 раз в 238 постах
ну я не в том смысле что перебираемо-неперебираемо а в том что тут набор чисел которые суммы образуют а там тоже набор делений которые в сумме тоже образовывали. вот про такое сходство я подумала и подумалось не подойдет ли одно для решения другого.
◕‿‿◕ Мяяяяяу!!! ◕‿‿◕ godville.net/gods/Шмяка ◕‿‿◕ MIUKA.mybrute.com ◕‿‿◕

UserPostedImage

Offline MikeVentris  
#248 Оставлено : 15 апреля 2012 г. 15:27:09(UTC)
MikeVentris


Статус: Старожил

Группы: Member
Зарегистрирован: 18.10.2010(UTC)
Сообщений: 512
Мужчина
Откуда: Санкт-Петербург

Сказал «Спасибо»: 79 раз
Поблагодарили: 48 раз в 34 постах
Автор: Шмяка Перейти к цитате
а все таки тут мысль дельная была насчет если сумма указана нечетная а все элементы четные и если это сразу проверять то от некоторой немалой доли переборов можно избавиться.

Чисто технически, проверка двух чисел на честность - две операции (причем чаще всего её реализуют с помощью целочисленного деления, что не слишком оптимально), в то время как сложение - всего одна и самая простейшая.
Offline Шмяка  
#249 Оставлено : 15 апреля 2012 г. 15:30:04(UTC)
Шмяка


Статус: Старожил

Медали: Роза: Девчатам от доброго сердца

Группы: Member, Crystal Dream Group
Зарегистрирован: 08.02.2012(UTC)
Сообщений: 1,862
Женщина
Российская Федерация
Откуда: Везде, куда ни занесет

Сказала «Спасибо»: 841 раз
Поблагодарили: 438 раз в 238 постах
Автор: MikeVentris Перейти к цитате
Автор: Шмяка Перейти к цитате
а все таки тут мысль дельная была насчет если сумма указана нечетная а все элементы четные и если это сразу проверять то от некоторой немалой доли переборов можно избавиться.

Чисто технически, проверка двух чисел на честность - две операции (причем чаще всего её реализуют с помощью целочисленного деления, что не слишком оптимально), в то время как сложение - всего одна и самая простейшая.

а перебор это целая прорва операций что СЛИШКОМ НЕ оптимально
◕‿‿◕ Мяяяяяу!!! ◕‿‿◕ godville.net/gods/Шмяка ◕‿‿◕ MIUKA.mybrute.com ◕‿‿◕

UserPostedImage

Offline evatutin  
#250 Оставлено : 15 апреля 2012 г. 15:32:20(UTC)
evatutin


Статус: Старожил

Медали: Первооткрывателю: Результат в проекте SAT@homeРазработчику: За организацию проекта Gerasim@home

Группы: Editors, Member
Зарегистрирован: 08.06.2010(UTC)
Сообщений: 3,622
Откуда: Russia, Kursk

Сказал(а) «Спасибо»: 1015 раз
Поблагодарили: 1788 раз в 874 постах
Автор: MikeVentris Перейти к цитате
Чисто технически, проверка двух чисел на честность - две операции (причем чаще всего её реализуют с помощью целочисленного деления, что не слишком оптимально), в то время как сложение - всего одна и самая простейшая.


Не понял, почему две, но для проверки на четность можно обойтись без деления: x & 00...01 (=1 для нечетного, =0 для четного), а логика так же быстра в современных процессорах, как и арифметика smile.

Шмяка написал:
а перебор это целая прорва операций что СЛИШКОМ НЕ оптимально


Ваше предложение с проверкой имеет смысл только тогда, когда решения нет. Когда оно есть, проверка от перебора не спасет

kvt.kurskstu team founder
Gerasim@home scientist
My numbers are 5056994653507584 and 1835082219864832081920. Why not? smile
Offline Шмяка  
#251 Оставлено : 15 апреля 2012 г. 15:42:46(UTC)
Шмяка


Статус: Старожил

Медали: Роза: Девчатам от доброго сердца

Группы: Member, Crystal Dream Group
Зарегистрирован: 08.02.2012(UTC)
Сообщений: 1,862
Женщина
Российская Федерация
Откуда: Везде, куда ни занесет

Сказала «Спасибо»: 841 раз
Поблагодарили: 438 раз в 238 постах
вот когда оно может и есть тогда и перебирать а так можно не рыться там где заведомо ничего не зарыто. не поедет же никто в антарктиду с лопатой "вдруг там картофель созрел".
◕‿‿◕ Мяяяяяу!!! ◕‿‿◕ godville.net/gods/Шмяка ◕‿‿◕ MIUKA.mybrute.com ◕‿‿◕

UserPostedImage

Offline MikeVentris  
#252 Оставлено : 15 апреля 2012 г. 15:48:39(UTC)
MikeVentris


Статус: Старожил

Группы: Member
Зарегистрирован: 18.10.2010(UTC)
Сообщений: 512
Мужчина
Откуда: Санкт-Петербург

Сказал «Спасибо»: 79 раз
Поблагодарили: 48 раз в 34 постах
Автор: evatutin Перейти к цитате
Автор: MikeVentris Перейти к цитате
Чисто технически, проверка двух чисел на честность - две операции (причем чаще всего её реализуют с помощью целочисленного деления, что не слишком оптимально), в то время как сложение - всего одна и самая простейшая.


Не понял, почему две, но для проверки на четность можно обойтись без деления: x & 00...01 (=1 для нечетного, =0 для четного), а логика так же быстра в современных процессорах, как и арифметика smile.

Да, действительно, не две. Достаточно будет проверить на четность все числа множества. Сначала показалось, что идея в том, что бы перед сложение проверять, может ли вообще сумма получиться четной.

Про логику - это да, но о ней постоянно забывают. Проще написать x%2. Современные программисты раскормлены законом Мура и часто забывают про оптимизацию даже при написании софта, в котором быстродействие - важнейший элемент.
Offline evatutin  
#253 Оставлено : 15 апреля 2012 г. 16:02:49(UTC)
evatutin


Статус: Старожил

Медали: Первооткрывателю: Результат в проекте SAT@homeРазработчику: За организацию проекта Gerasim@home

Группы: Editors, Member
Зарегистрирован: 08.06.2010(UTC)
Сообщений: 3,622
Откуда: Russia, Kursk

Сказал(а) «Спасибо»: 1015 раз
Поблагодарили: 1788 раз в 874 постах
Автор: MikeVentris Перейти к цитате
Про логику - это да, но о ней постоянно забывают. Проще написать x%2. Современные программисты раскормлены законом Мура и часто забывают про оптимизацию даже при написании софта, в котором быстродействие - важнейший элемент


В приведенном примере абсолютное большинство современных оптимизирующих компиляторов сделают именно логику (AND), а не деление (DIV или IDIV) — в данном случае программисту можно расслабиться smile. В общем же случае за оптимизацией следить надо. В одной из задач, которой я сейчас плотно занимаюсь, я убил почти месяц на анализ хотспотов и реализацию двух подсистем (кэширование и система уведомления о событиях), зато теперь качество решения оценивается за 1,2 с, а до оптимизации было 1,3 мин smile

kvt.kurskstu team founder
Gerasim@home scientist
My numbers are 5056994653507584 and 1835082219864832081920. Why not? smile
Offline Шмяка  
#254 Оставлено : 15 апреля 2012 г. 16:05:13(UTC)
Шмяка


Статус: Старожил

Медали: Роза: Девчатам от доброго сердца

Группы: Member, Crystal Dream Group
Зарегистрирован: 08.02.2012(UTC)
Сообщений: 1,862
Женщина
Российская Федерация
Откуда: Везде, куда ни занесет

Сказала «Спасибо»: 841 раз
Поблагодарили: 438 раз в 238 постах
ну вот с этим выяснилось. а с глобомбами?
◕‿‿◕ Мяяяяяу!!! ◕‿‿◕ godville.net/gods/Шмяка ◕‿‿◕ MIUKA.mybrute.com ◕‿‿◕

UserPostedImage

Offline citerra  
#255 Оставлено : 15 апреля 2012 г. 16:07:46(UTC)
citerra


Статус: Старожил

Медали: Первооткрывателю: Нахождение пар ОДЛК в RakeSearch!Донор: За финансовую помощь сайту

Группы: Editors, Member, Russia Team Group, Moderators
Зарегистрирован: 02.10.2007(UTC)
Сообщений: 2,265

Сказал(а) «Спасибо»: 486 раз
Поблагодарили: 341 раз в 248 постах
Если n > floor(m/2)+1 и числа разные, то всегда найдется нечетное число.
thanks 1 пользователь поблагодарил citerra за этот пост.
evatutin оставлено 15.04.2012(UTC)
Offline evatutin  
#256 Оставлено : 15 апреля 2012 г. 16:37:47(UTC)
evatutin


Статус: Старожил

Медали: Первооткрывателю: Результат в проекте SAT@homeРазработчику: За организацию проекта Gerasim@home

Группы: Editors, Member
Зарегистрирован: 08.06.2010(UTC)
Сообщений: 3,622
Откуда: Russia, Kursk

Сказал(а) «Спасибо»: 1015 раз
Поблагодарили: 1788 раз в 874 постах
citerra
Нетривиальное и вроде верное замечание! В таком случае и построение подобных множеств потребует некоторых хитростей

kvt.kurskstu team founder
Gerasim@home scientist
My numbers are 5056994653507584 and 1835082219864832081920. Why not? smile
Offline Шмяка  
#257 Оставлено : 15 апреля 2012 г. 17:14:38(UTC)
Шмяка


Статус: Старожил

Медали: Роза: Девчатам от доброго сердца

Группы: Member, Crystal Dream Group
Зарегистрирован: 08.02.2012(UTC)
Сообщений: 1,862
Женщина
Российская Федерация
Откуда: Везде, куда ни занесет

Сказала «Спасибо»: 841 раз
Поблагодарили: 438 раз в 238 постах
ну вот опять я попадаю... знания куда как меньше чем соображалки... floor(x) -- это что от х ? (а то у меня за плечами только одна математика. школьная. и то...)
◕‿‿◕ Мяяяяяу!!! ◕‿‿◕ godville.net/gods/Шмяка ◕‿‿◕ MIUKA.mybrute.com ◕‿‿◕

UserPostedImage

Offline Freddykrug  
#258 Оставлено : 15 апреля 2012 г. 17:32:36(UTC)
Freddykrug


Статус: Старожил

Группы: Member, Модератор Astronomy.Ru Forum
Зарегистрирован: 30.05.2010(UTC)
Сообщений: 2,874
Мужчина
Российская Федерация
Откуда: г. Томск

Сказал «Спасибо»: 740 раз
Поблагодарили: 494 раз в 313 постах
Автор: evatutin Перейти к цитате
Например, если есть страна с городами и дорогами, в которой необходимо найти кратчайший путь между заданной парой городов — это задача класса P, решается алгоритмом Дейкстры. А если надо обойти все города кратчайшим образом и вернуться в исходный — это уже NP и быстро не решается. Хотя внешне они очень схожи smile
Если не ошибаюсь, эти задачи решаются в "теории графов" и логистике?
Кстати, в теории графов есть т.н. задача коммивояжера, и вот что написано в Википедии:
Цитата:
Общая постановка задачи, впрочем как и большинство её частных случаев, относится к классу NP-полных задач. Задача коммивояжёра относится к числу трансвычислительных: уже при относительно небольшом числе городов (66 и более) она не может быть решена методом перебора вариантов никакими теоретически мыслимыми компьютерами за время, меньшее нескольких миллиардов лет.

3 Gb Radeon 7950, i-5 2400, 16 Gb ОЗУ Astronomy.Ru Forum

Offline Freddykrug  
#259 Оставлено : 15 апреля 2012 г. 17:38:42(UTC)
Freddykrug


Статус: Старожил

Группы: Member, Модератор Astronomy.Ru Forum
Зарегистрирован: 30.05.2010(UTC)
Сообщений: 2,874
Мужчина
Российская Федерация
Откуда: г. Томск

Сказал «Спасибо»: 740 раз
Поблагодарили: 494 раз в 313 постах
Автор: MikeVentris Перейти к цитате
Автор: Freddykrug Перейти к цитате
А причем тут привыкание к повышению дозы лекарств?
Это, типа, шутка? Если что, я имел в виду социологическое значение слова "толерантность".


У меня к социологическому значению слова "толерантность" очень не толерантное отношение smile предпочитаю старое слово "терпимость". Тем не менее считаю нетерпимым положение, когда тыкая толерантностью, затыкают оппоненту рот, что довольно часто наблюдается в политических дискуссиях. MikeVentris - ничего личного!!! buba Я высказал своё мнение о РВ в фазанах. Но навязывать его не собираюсь.
3 Gb Radeon 7950, i-5 2400, 16 Gb ОЗУ Astronomy.Ru Forum

Offline citerra  
#260 Оставлено : 15 апреля 2012 г. 18:07:59(UTC)
citerra


Статус: Старожил

Медали: Первооткрывателю: Нахождение пар ОДЛК в RakeSearch!Донор: За финансовую помощь сайту

Группы: Editors, Member, Russia Team Group, Moderators
Зарегистрирован: 02.10.2007(UTC)
Сообщений: 2,265

Сказал(а) «Спасибо»: 486 раз
Поблагодарили: 341 раз в 248 постах
Автор: Шмяка Перейти к цитате
ну вот опять я попадаю... знания куда как меньше чем соображалки... floor(x) -- это что от х ? (а то у меня за плечами только одна математика. школьная. и то...)

В данном случае целая часть числа.
Функция floor возвращает значение с плавающей точкой, представляющее наибольшее целое, которое меньше или равно x.
floor(2.3)=2.0
floor(-2.3)=-3.0
Пользователи, просматривающие эту тему
Guest
15 Страницы«<1112131415>
Быстрый переход  
Вы не можете создавать новые темы в этом форуме.
Вы не можете отвечать в этом форуме.
Вы не можете удалять Ваши сообщения в этом форуме.
Вы не можете редактировать Ваши сообщения в этом форуме.
Вы не можете создавать опросы в этом форуме.
Вы не можете голосовать в этом форуме.

Boinc.ru theme. Boinc.ru
Форум YAF 2.1.1 | YAF © 2003-2018, Yet Another Forum.NET
Страница сгенерирована за 0.247 секунды.