Гурвич Владимир Александрович :
другие произведения.
Околонауки
Самиздат:
[
Регистрация
] [
Найти
] [
Рейтинги
] [
Обсуждения
] [
Новинки
] [
Обзоры
] [
Помощь
|
Техвопросы
]
Ссылки:
Школа кожевенного мастерства: сумки, ремни своими руками
Оставить комментарий
© Copyright
Гурвич Владимир Александрович
Размещен: 10/10/2017, изменен: 19/08/2023. 101k.
Статистика.
Эссе
:
Мемуары
Скачать
FB2
Ваша оценка:
не читать
очень плохо
плохо
посредственно
терпимо
не читал
нормально
хорошая книга
отличная книга
великолепно
шедевр
В 1995-м я читал лекцию на летней школе по теории игр в Университете Стоуни Брук на Лонг Айленде.
[Каменный ручей на Длинном острове...
"В Оксфорде, то бишь в Бычьем Броду, "практикуется" словесная пря, называемая диспут", -
как писал в "Новом Мире" Сергей Наровчатов, в рассказе "Диспут".
Цитирую не точно, потому как найти в интернете этот рассказ, равно как и ещё два,
"Абсолют" и "Ведьма", совершенно невозможно. А между тем, это - вершина его творчества,
не сравнить со стишками. Да и сам ли он эти три рассказа написал?..]
Впрочем это всё это с моей историей никак не связано.
А рассказывал я доказательство гипотезы Клода Бержа и Пьера Душе о ядрах в совершенных графах.
"Любая ориентация совершенного графа, не имеющая циклов, в которых присутствуют все хорды, имеет ядро".
Это для тех, кто в теме. Редкий случай, когда гипотеза из теории графов доказана средствами теории игр;
обычно бывает наоборот. Так что собралось довольно много народа.
Эта гипотеза, Бержа-Душе, - довольно сильное обобщение знаменитой теоремы
Гейла-Шепли 1962-го года об устойчивых паросочетаниях (the stable marriage theorem).
Ллойд Шепли успел за неё получить Нобелевскую премию по экономике, а Дэвид Гейл не дожил - умер в 2008-м.
Теорема Гейла-Шепли получается из гипотезы Бержа-Душе, если заменить
совершенные графы на рёберные графы двудольных.
Они совершенны, как следует из теоремы Кёнига, доказанной ещё в 1920-х. Но этот случай совсем прост.
Совершенных графов намного больше и гипотеза считалась довольно смелой. Мы её доказали с Эндре Борошем в 1994-м.
Но вернёмся к лекции. Среди прочего мне нужны были "сбалансированные и расщепляемые покрытия".
Сбалансированное покрытие кратности k - это семейство множеств, накрывающее каждый элемент ровно k раз.
С помощью этого понятия доказаны несколько теорем существования ядра (core) в кооперативных играх.
[Ядро ориентированного графа (kernel) - это совсем другое, но по-русски и то, и это - всё ядро.]
Этим занимались в 1960-х Ольга Бондарева (1962), Ллойд Шепли (1964, 67), Херб Скарф (1967),
Бецалел Пелег (1967), а позже Владимир Данилов и Александр Сотсков (1988).
При k=1 сбалансированное покрытие - это просто разбиение.
Семейство множеств называется расщепляемым, если любое его сбалансированное подсемейство содержит разбиение
(или, что то же, разлагается в сумму разбиений).
Всё это применяется в теории кооперативных игр. Например, К-ядро
(то есть множество дележей, не отвергаемых ни одной коалицией из данного семейства К)
непусто тогда и только тогда, когда семейство К расщепляемо.
Эта теорема переносится и на случай, когда исходы не конвертируются в деньги.
При этом семейство К, расширенное всеми синглетонами (то есть, отдельными игроками) должно быть расщепляемым.
Эти две теоремы мы доказали с Александром Васиным в 1976-м и 77-м.
Расщепляемые покрытия полезны и в комбинаторике и в теории графов. Например, Ласло Ловас доказал
слабую гипотезу Бержа: "граф, дополнительный к совершенному, тоже совершенный".
По сути дела он доказал, что, взяв для каждой вершины совершенного графа все максимальные клики,
её содержащие, и добавив синглетоны (все максимальные клики по отдельности) получим расщепляемое семейство.
Короче, я привожу поясняющий пример: " Семейство всех коалиций на множестве трёх игроков {1,2,3} не является расщепляемым.
В самом деле, подсемейство {1,2}, {2,3}, {3,1} - сбалансированное покрытие, но никаких разбиений не содержит."
Тут вдруг поднимает руку какой-то дядька лет шестидесяти с лишком и возражает:
"Натурально, Вы ошибаетесь! Оно натурально разлагается в сумму разбиений: {1,2},{3}; {2,3},{1} и {3,1},{2}. "
"Но этого не достаточно", - популярно объясняю я, - "надо чтобы и любое подпокрытие разлагалось,
а вот глядите: {1,2}, {2,3}, {3,1} нипочём не разлагается.
А он опять гнёт своё: "{1,2},{3}; {2,3},{1}; {3,1},{2} ..."
"Эдак мы всё лекцию с Вами проспорим", - резонно говорю я, - "Давайте уж потом разберёмся".
А потом мне сразу же и сообщили, что это не просто дядька, а Ллойд Ставел Шепли собственной персоной,
и что свои-то собственные теоремы он, уж наверно, знает получше меня.
"Как знать..." - отвечаю.
Тут он подходит и всё начинается по-новой: "Так ведь {1,2},{3}; {2,3},{1}; {3,1},{2}!"
"А как насчёт {1,2}, {2,3}, {3,1} ?!" И пошло-поехало, на потеху публике.
Тут он вдруг разозлился и говорит: "Вы, юноша (мне как раз исполнилось 43) повторяетесь!"
"Что же я могу поделать: {1,2}, {2,3}, {3,1} - единственный контрпример к Вашему
(чересчур оптимистичному) утверждению (в случае, когда базовое множество содержит всего три элемента).
На том и разошлись. Большинство, конечно, решило, что он прав:
знаменитый человек, да ещё и статьи про сбалансированные покрытия писал.
Правда, дело было давно : в 1964-м и 67-м, но всё же.
&n bsp; А я так сразу понял: что-то с ним не так. Что-что, а уж свои-то теоремы математики обычно помнят.
А года через 3-4 уже все поняли, что "старик спятил". Лекции в UCLA бросил читать,
потом стал куда-то пропадать из своего дома в Санта Монике.
Но Нобелевскую лекцию прочитал; правда читал не час, как положено, а всего минут десять.
Он и Джон Нэш "двигались навстречу друг другу". Нэшу становилось всё лучше, а Шепли всё хуже.
Но в 95-м, кроме меня, никто ничего ещё не замечал.
VG; 10 октября 2017
-------------------
Торг с богами.
Из статьи про Нэша в Мат. Просвещении 20, 2016
Кого Боги хотят погубить, того они лишают разума." Верно ли обратное?
Джон Форбс Нэш младший - единственный в мире обладатель и Нобелевской и Абелевской премий.
Получив последнюю, он с супругой Алисией возвращался из Норвегии домой в Нью Джерси 23 мая 2015-го.
Они взяли такси в аэропорту Ньюарк и ... оба погибли в автокатострофе.
Впрочем, было бы удивильно, если бы человек с такой биограей спокойно умер в своей постели.
Дело в том, что Боги и в самом деле лишили его разума, в прямом смысле слова.
Не менее тридцати пяти лет Джон Нэш страдал параноидальной шизофренией в крайне тяжёлой форме.
Удалось ли его этим погубить? Во всяком случае, он боролся на равных:
победил неизлечимую болезнь, получил две высшие награды: за вклад в экономику и в математику.
Возможно, чаша терпения Богов переполнилась, они отказались от изощрённых методов наказания
и прибегли к вульгарным, но более надёжным. Капитулировали?
...
Он выглядел лучше, но сожалел об изменениях в своём состоянии и называл этот период ремиссии
насильственным возвратом к здравому смыслу.
Он говорил, что ряд великих математических идей явились к нему из Космоса
вместе с галлюцинациями, а рациональное мышление ослабляет связьс Космосом,
что это форма конформизма, в то время как безумие - тоже возможный выход.
(Об этом писал и Пушкин, но тут - бесценное свидетельство человека, знающего предмет не понаслышке; VG.)
---------------------------------
Осенью 1995-го работал я в Технионе и решил проверить гипотезу Пьера Душе
об ориентированных графах, не имеющих ядра.
Теорема Ричардсона (1953) утверждает, что любой такой граф содержит нечётный ориентированный цикл.
Иными словами, все минимальные ориентированные графы, не имеющие ядра, - это как раз
нечётные ориентированные циклы и есть.
Душе шёл дальше. Он предполагал, что не только минимальные, но и локально минимальные тоже.
Иными словами, если ориентированный граф ядра не имеет, а при удалении из него любого ребра
ядро появляется, то граф этот не что иное как нечётный ориентированный цикл.
Он, конечно, обладает всеми указанными свойствами; так что обратное утверждение очевидно.
Но в гипотезе Душе я сомневался.
И у меня были все шансы получить контрпример, если только таковой существует.
Ведь у меня в классе было тридцать аспирантов. Должен же среди них быть хоть один сильный программист.
Вызвалась дама по имени Евгения. Она сразу мне объяснила, что сама она, может, и не очень подходит
для такого дела, но как раз недавно вышла замуж и очень удачно: её супруг большой профессионал
в программировании и как раз специализируется в постановке комбинаторных экспериментов.
Вообще-то, задача была связана с моим курсом, хотя и не слишко сильно, но всё-таки.
В курсе разбиралось недавнее доказательство гипотезы Бержа-Душе, а тут просто гипотеза Душе, причём Душе -
тот же самый, Пьер. Кстати, то обстоятельство, что его учитель Клод Берж под второй гипотезой "подписываться"
не стал, сильно укрепляло мои надежды. Так вот Евгения (или её муж, что меня тоже устраивало) программу написал,
но та работала медленнее, чем хотелось бы. Я запускал её в конце рабочего дня и она всю ночь считала. При этом я
накрывал клавиатуру листом бумаги с написанной на нём (листе) просьбой к ней (клавиатуре) ни в коем случае не прикасаться.
Дело в том, что программа не спасала вычислений, и если кто-то тыкал пальцем в клавиатуру, всё тут же и пропадало.
Однажды в ночь со среды на четверг кто-то так и поступил. Результаты пропали. Ну, я огорчился и
в четверг вечером запустил программу по-новой. А поскольку пятница и суббота в Израиле выходные, запустил счёт
до сорока пяти вершин, вместо прежних сорока. В результате контрпример с сорока тремя вершинами и был получен.
Я человек не очень суеверный, но и уверенно отрицать вмешательство высших сил не стал.
Поэтому я и решил поставить Евгении 100, а всем остальным не более, чем 99. Из этого, правда, ничего не вышло, но это уже другая история.
Полученный пример - циркулянт (1,7,8)_43. Нарисуйте на окружности 43 точки и соедините каждую к со следующей, k+1, а ещё с k+7 и с k+8.
Сам этот циркулянт ядра не имеет. Можно доказать, что циркулянт (1,7,8)_n имеет ядро, если и только если n кратно или 3-м или 29-и.
Но при удалении любого ребра ядро появляется. Это легко проверить. Почему легко? Хотя всего рёбер немало, 3х43 = 129,
а проверить надо - всего 3: длины 1, длины 7 и длины 8. Каждая такая проверка заменяет 43.
Тут-то как раз и проявляется главное достоинство циркулянтов - симметрия.
Вообще, я бы сравнил циркулянты с буром. С помощью компьютера "можно забуриться очень глубоко", до 70 или даже 80 вершин.
и обнаружить при этом широкие "пласты" графов: совершенные циркулянты или циркулянты без нечётных дыр и анти-дыр и пр.
Более того, можно охарактеризовать их на простом языке арифметики.
Например, циркулянт (k_1, ..., k_t)_n связен, если и только если НОД (n, k_1, ..., k_t) = 1;
двудолен, если и только если n чётно, ас все k_1, ..., k_t - нечётны.
Если же отказаться от симметрии, то глубже 20-и вершин не забуришься, даже и с компьютером.
Кстати можно ли построить пример, аналогичный (1,7,8)_43, если разрешить всего две, а не три длины;
то есть, t=2 вместо t=3. Ответа я не знаю, хотя могу доказать, что это невозможно при n < 1,000,000.
VG; 11 октября 2016
--------------------
http://rutcor.rutgers.edu/pub/rrr/reports2012/20_2012.pdf
http://rutcor.rutgers.edu/~gurvich/MIPTstory.pdf
http://rutcor.rutgers.edu/~gurvich/resistance.pdf
--------------------
В Израиле над каждым университетом надзирает раввин. Наука наукой, но и о душе думать надо.
Так вот технионский раввин оказался не в меру ретивым и запретил использовать понятие
пустого множества, ну и символ, заодно. "Б_г - всйюду!" - объяснил он.
Математики заметно приуныли. Что же теперь все учебники переписывать?!
Я предложил довольно изящное решение, но, кажется, они им не воспользовались.
Надо просто добавить в список ошибок и опечаток фразу: "Символом перечёркнутый ноль теперь обознается
не множество, в котором нет ни одного элемента, как ошибочно считалось в предыдущих изданиях,
но множество, не содержащее ничего, кроме Б_га.
-
А вот Иосиф Бродский, кажется, с раввином согласен:
"В деревне Бог живёт не по углам,
Как думают насмешники, а всюду",
но только отчасти: в деревне - всюду,
а в городе и в других местах - нет.
-
Получается, что раввин Техниона полагает, что Б_г есть, а пустого множества нет.
Но ведь, кроме этого "Есть-Нет", есть ещё три варианта: Есть-Есть, Нет-Есть и Нет-Нет.
Учитывая, что народу чёртова уйма, наверняка у каждого есть множество адептов [не пустое].
Как они называются?
Впрочем, наверно, много и таких, кто ни в какие множества не верит: ни в пустые, ни в прочие.
VG; 1 октября 2014
------------------
Неделю назад я узнал, что имеется оказывается чёртова уйма индексов, отражающих научную активность учёного.
Как-то они там по-разному вычисляются по количеству публикаций и ссылок на них.
То есть, я и раньше слыхал о них, но как-то не придавал значения. А зря. Дело серьёзное. Узнал я случайно.
На моей новой работе к первому сентября обнаружили что у меня ничего такого нет. А у всех коллег есть.
Да и вообще оказалось, что у всех знакомых учёных индексы эти полном ажуре, только я один оплошал.
Ну я хотя бы полез в интернет и посмотрел, что за индексы такие. Самым симпатичным оказался Google Scholar.
Сиди себе сложа руки, а Гугл, используя свои навыки пылесоса, отыщет все твои книги, статьи и даже препринты.
Причём больше, чем у тебя есть. Если кто-то неправильно написал название твоей работы, ну например, вставил недостающий
(с его точки зрения) артикль - и вот тебе лишняя публикация. А самый мерзкий - Research Gate.
Мне они вставили с десяток публикаций, а остальные и не подумали, хотя прекрасно осведомлены.
Набираешь пару слов в названии и они её тут же находят, но требуют подтверждения авторства.
Короче, у них я оказался снова в 76 году. Но зато туда можно "вручную" публикации вводить. Думаю, они всё же проверят.
Выходит, теперь индексы эти для учёной карьеры вещь необходимая. И тут я многое понял. Например, почему в
Дискретную Прикладную Математику (я там редактирую секцию Теории Игр) лет пять назад число представленых работ
возросло вдруг втрое и среди них оказалось 90% "мусора", а раньше было всего 50%.
Похожая вещь случилась в СССР в конце 80х. Лучшие журналы стали переводить на западе, а авторам переводить деньги за эти переводы.
Короче, "не перевелись ещё..." Правда, была такая организация "Всесоюзное Агентство по Авторским Правам (ВААП).
Так она 90% гонорара забирала себе. (Что охраняешь, то и имеешь", - кал сказал Жванецкий. Когда ещё Райкин за него говорил.)
Но всё равно и 10% - деньги немалые. Они же в долларах. Ну правда, были запрещены, но
можно было плучить в чеках, эдак по два рубля за чек. Ну и вот сразу началась вакханалия (или ваапханалия).
Раньше статью в приличном журнале напечатать было не так уж и сложно, был бы результат.
А тут очередь увеличилась, а качество упало примерно втрое.
Правильно Щедрин сказал:
"Удивительная в то время во всем простота царствовала. Нынче молодому человеку и пожить-то в свое удовольствие нельзя,
ежели, по крайности, хоть до тройного правила арифметику не прошел. Говорят тебе:
"Какие ты можешь, скотина, удовольствия или огорченья испытывать, коль скоро ты даже именованных чисел не знаешь!"
А прежде с корнета ничего такого не спрашивали. Был бы верный слуга отечеству
да по части женского пола чтобы все в исправности состояло - вот и только."
VG; 2 сентября 2016
-------------------
А вот и следствия.
В РФ все эти индеклсы стали существенно влиять на зарплату, и
теперь я каждую неделю получаю такие послания:
----
Ксения Алексеевна
3:49 AM (5 hours ago) 12 апреля 2017 to me
Здравствуйте, Владимир Александрович!
Биржа публикаци
Scopus
Thomson Reuters
Clarivate Analytics
Web of Science
ВАК
Публикуем!!!
Биржа публикаций даст Вам возможность найти:
- Журнал для публикации.
- Исполнителя.
- Заказчика.
- Соавтора.
- И многое другое.
Цены от 50 дол.
Средняя цена за публикацию - 370 дол.
Средняя цена журнала - 300 дол.
Сообщите нам:
1. Какая помощь Вам нужна?
2. На какую цену Вы рассчитываете?
Мы разместим ваше объявление.
Вы начнете получать отклики мгновенно.