Вставка
- Опубліковано 25 сер 2024
- Каждому известно, что при попадании компьютера в непонятное состояние надо нажать кнопку “Reset”, после чего через некоторое время он перейдет в начальное. При этом на компьютере выполняется фиксированная последовательность команд: в каком бы состоянии он ни пребывал, после её выполнения он переходит в одно и то же.
Если же вместо компьютера у нас есть произвольный конечный автомат, всё становится сложнее. Черни давным давно выдвинул гипотезу, что если общее число состояний автомата равно n, то количество команд в такой последовательности будет не больше чем n-1 в квадрате, и привел серию автоматов, для которых эта оценка достигается. Чуть больше десяти лет назад Михаил Волков прочел серию лекций www.lektorium...., где предположил, что квадратичная оценка сверху для количества команд в такой последовательности будет скоро доказана. Увы, до сих пор это не так. Надеемся, что после обращения внимания в этом видео на сей досадный факт, он перестанет иметь место, тем более у видео есть конкретные адресаты из слушателей канала.
Ролик записан в Центре современной культуры "Смена": / smenakazan
🎯 Поддержать популяризацию математики на Патреоне: / savvateev
Наши ресурсы: alexei_... / aleksey_savvateev / savvatan savvateev.live... savvateev.xyz t.me/savvateev...
![Лента Мёбиуса - кому вообще нужна топология? [3Blue1Brown]](http://i.ytimg.com/vi/QJC27E9bvqU/mqdefault.jpg)
Можете говорить что хотите, но я при слове "Черни" вспоминаю этюды для ф-но
а вот это красиво
Черни Гермер, как вспомню - так дрогну)))
Вьетнамские флэшбэки)
ага, как и при "дыхание Чейна-Стокса" я вспоминаю уравнения Навье-Стокса :-))
А я слыша Черни, вспоминаю, что больше люблю Ганнона
Дядьки, вы супер крутые
Увлечённые люди - это люди любящие своё дело!
Райгородский все понял! А меня кокнуло
да ладно, проблема-то понятна, а вот как решать???
1:04, "Любой может ее понять"
0:42, Савватан: "Я ничего не понял"
Савватеев видимо за несколько секунд до знает что никого не поймёт
я просто должен был врубиться по мылу, что сложно. Вот и позвал Эдика сюда!
Как же тяжело смотреть из-за звука (
Доказательство гипотезы Черни
Очевидно, граф задачи задает конечное множество отображений некоего конечного множества на себя. Какие-то из этих отображений - биекции. Но очевидно, раз существует композиция этих отображений переводящая все фишки в один кружок, среди этих отображений есть сюрьекция.
Очевидно отбрасывая биекции мы лишь увеличиваем количество функций в такой композиции.
Оставим одну биекцию. Аналогичным образом поступим с сюрьекциями. Без ограничения общности можем считать оставшуюся биекцию перестановкой по кругу на один шаг. Очевидно наихудшей сюрьекцией в смысле оптимизации длины композиции является отображение которое которое все элементы оставляет на месте и только пару переводит в один элемент. Таким образом мы попадаем в ситуацию которая была описана в видео, и для которой доказано что наилучшее решение есть и оно имеет длину (n-1)^2.
Вот и все собственно. )))))))
От Эдика Лернера ответ: Спасибо за коммент. Увы, в этом "доказательстве" есть несколько дыр >1) Без ограничения общности можем считать оставшуюся биекцию перестановкой по кругу на один шаг. Произвольная биекция есть не один цикл (перестановка по кругу) а МНОГО циклов (много перестановок по кругу). >2) Очевидно наихудшей сюрьекцией в смысле оптимизации длины композиции является отображение которое которое все элементы оставляет на месте и только пару переводит в один элемент. Это совсем не очевидно, а если утверждается единственность наихудшего автомата, то даже и неверно. Посмотрите вот здесь www.math.uni.wroc.pl/~kisiel/auto/volkov-surv.pdf на граф Кэри на стр 22 и на некоторые графы на предыдущей странице. Они совсем не такие, но так же требуют для синхронизации (n-1)^2 команд. Вообще, основная проблема в 1). Случай, когда есть биекция, переставляющая всё по кругу исследован, и в этом случае гипотеза Черни доказана, см. ua-cam.com/video/xAXz3Ku0YU0/v-deo.html , на с сайте compiter science club можно скачать слайды к этой лекции. Но это частный случай.
Ух ты, теория конечных автоматов! С одной стороны, понятно, что эту решётку подмножеств можно сильно проредить, и это даже сделано до куба, но при этом с 64о года не получается дойти до конца!
Да! Вперёд!!! :-)))
Алексей, Вас очень интересно слушать, но микрофоны - ужас, ничего не слышно, как так? неужели нет возможности брать с собой хороший звук?
брать-то есть возможность, а вот ставить его некому.
Алексей - вот вам вопрос на засыпку.
Такая вот бытовая ситуация
Для простоты не берём в расчет неготовность ждать и риски, что товар не дойдет. Грубо говоря - если для каждого из друзей есть выгода хотя бы в один евроцент - с финансовой точки зрения по отношению к покупке товара "на месте" - то он уже считает, что это выгодно. Но хочется какого-то "справедливого" распределения.
Самая простая и напрашивающаяся схема - распределить затраты на доставку пропорционально затратам на покупку. Т.е. один платит 10 евро (у которого покупка 100евро), другой - 7 и третий 3.
Но тут возникает некий подвох.
Во-первых, первому платить 110 евро совсем невыгодно, ибо "на месте" он бы потратил 105 евро
Во-вторых, по идее, наиболее выгодно участвовать в этой сделке третьему другу (30евро), ведь иначе ему придется переплатить 33% (+10 евро), если он решит покупать на месте
Также достаточно заинтересован второй друг (70евро), ведь он хочет сэкономить (а в случае если он не будет участвовать в сделке, он по-любому потратит 90евро), и с его точки зрения любая плата со стороны его друзей будет выгодной, даже если они скинутся по одному центу
Так как же правильно распределить оплату доставки в этом случае? Из каких принципов следует исходить?)
Вот навскидку пару рассуждений.
Начнем с того, что первый друг должен заплатить не больше 5 евро
Третий друг - не больше 10
Таким образом, как минимум 5 оставшихся евро третий друг по-любому должен оплатить.
Остаётся 15 евро. Ввиду неопределённости можно, конечно, разделить эти 15 евро поровну - типа 5 евро платит первый и третий, а второй - 10. Но в этом случае выгода первого никакая, а выгода второго, всё-таки, 5 евро, а выгода третьего - 10.
Можно как-то попытаться вычислять тупо по количеству выгоды. Типа сделать так, чтобы каждый "выиграл" одинаково. Тут будет такое распределение - первый ничего не платит за доставку. Второй платит 5 евро, третий - 15. Таким образом, каждый сэкономит 5 евро. Но опять же, как-то получается, что первый получает эту "выгоду", совершенно ничего за неё не платя - грубо говоря, за чужой счет.
Тут возникает идея о соразмерности вложений в сумму доставки с выгодой для каждого друга.
если назвать сумму, которую оплатит первый - за а, второй - за b и третий - за c - получим такую систему уравнений
a+b+c = 20
(5-a)/a = (20-b)/b = (10-c)/c
Решение этой системы уравнений будет решением или нет?
ну и собственно это будет
a= 20/7
b= 20*4/7
c=20*2/7
т.е. их распределение вкладов соответствует пропорциям их выгод от сделки без учета суммы доставки. грубо говоря 3евро (экономит 2евро), 11евро (экономит 9евро), 6евро(экономит 4евро).
Но тут опять вопрос - не возникает ли ощущение несправедливости. Типа исходя из изначальных условий для того, кто заплатит 70 евро - в целом чуть легче заплатить +20 евро, чем тому, кто платит 30евро +10. И почему тогда второй должен вдвое больше внести вклад в сделку (11 и 6 евро это я округлил, но по математике - получается ровно вдвое), чем третий. не должен ли учитываться ещё и какой-нибудь процентный показатель "готовности" платить "вплюс"... короче, я немного запутан) Ваше мнение?)
Класс! Только звук не очень
ага, но не беда. главное - содержание!
@@user-rb8ux1no6j с таким звуком до содержания можно не дойти)
Красно зелёные👍👍👍👍😃
!!!!!!
Очень интересная проблема!
ага!!!
Для нас гуманитариев просто понять,а в чем суть проблемы?)))) уже достижение!!!
гуманитарий - человек высоких материй и смыслов!! Это роднит гуманитариев с математиками! (Это я недавно придумал)
задачка про развилки дорог
на поверхности бутылки Клейна
Почему надо друг друга перебивать всё время? Почему нельзя дать партнёру спокойно высказать мысль до конца? Зачем все эти дёрганья и прерывания? Зачем Савватеев всё время говорит «тааак»? Почему нельзя молча дослушать предложение, нельзя дать договорить мысль? Почему такая рваная речь? :/
нам так нравится - вот честный ответ!
По моему, это нормальная реакция, если хочешь чему-то обучиться, а не просто вежливо послушать.
@@user-rb8ux1no6j Ответ честный. А как вы думаете, зачем в статьях абстракты пишут? Ладно, вы всё равно ответите не по существу. Поэтому говорю кратко: сначала сформулируйте результат без "эээээ", "аааа!", без перебивания друг друга, беканья и меканья. Спокойно, на хорошем русском языке, объяните, чему посвящено видео. Это займёт две минуты. А потом, после, перебивайте друг друга, многозначительно молчите, сверкайте глазами, упивайтесь собственной значимостью, произнося "аааа!", бекайте и мекайте сколько влезет. Но сначала: спокойная, понятная, обстоятельная формулировка предмета: о чём видео. Вот такие мысли у меня при попытке просмотра вашего видео. Но на зрителя вам класть, как я понял. Тоже позиция, конечно. Типа: клали мы на всех, нам так интересно. Ну ок. Клали на всех. Молодцы.
Это мой вам честный ответ.
@@dmarsentev Спасибо за критику. Абстракт на хорошем русском языке мы старались написать (точнее, писал я с некоторой редактурой тех, кто в теме, а Лёша убрал ошибки в русском). Он с самого начала размещен под видео (см. выше).
@@user-mf3lo5mx7h Спасибо! Этот абстракт с самого начала был? Если абстракт был с самого начала, то тогда моя вина, что я его не заметил, приношу извинения за резкость, критику снимаю. При наличии краткого содержания перед основным материалом ваше святое неотъемлемое право делать видео сколь угодно неудобопрослушиваемым. Нет вопросов.
Алексей Владимирович, вопрос совершенно из другой области, но достаточно волнующий. Пожалуйста, выразите ваше мнение насчёт российской вакцины от короновируса. Просто, встал вопрос стоит ли вакцинироваться и безопасна ли она?
Сейчас не так-то просто узнать, насколько вакцины действительно безопасны. Хотя, существенных данных о проблемах, вроде бы, нет, но Вам лучше самому поискать о конкретной вакцине, которой Вы хотите прививаться. Скажем, эпивак, вероятно, безопаснее, но и менее эффективен. Ещё, надо учитывать вероятность заражения, сама по себе болезнь тяжёлая, всяко поопаснее вакцины.
Есть ещё такой момент, этический: то что спутник выращивается на эмбриональной клеточной линии. Я христианин и для меня это стало причиной выбора другой вакцины, т.к. совесть говорила, что нельзя получать пользу из убийства, даже косвенно.
ХЗ :-)) Вроде, многие друзья вакцинировались, никто не жалуется! У меня просто есть антитела, я переболевший - поэтому могу пока решения не принимать :-)))
@@yurifromspb спасибо, учту
@@user-rb8ux1no6j хорошо, спасибо)))
будет решена в 2023-2027 годах
Что там с тем либеркактотам?
А вам зачем?
Существует только два вида команд?
В общем случае - фиксированное количество и считают, что гипотеза Черни верна и для такого обобщения. Но если доказать квадратичную оценку для случая всего двух видов команд, то отсюда будет легко следовать квадратичная оценка для любого фиксированного числа команд, поэтому достаточно построитьквадратичную оценку только для любых графов с двумя видами стрелочек.
щас, минутку братаны, я другану своему покажу эту вашу гипотезу (опытный ферматист между прочим!) - он е быренько докажет! а куда за абелевкой потом приходить подскажите только?
В Кащенко
пианисты не поняли название видео
блин, и я не понял, уже всё забыл (я на аккордеоне играл, правда)
Черни это который разрабатывал архитектуру PS4 и PS5?))
SSD!
Кубик Рубика напомнило)
почему?
@@user-rb8ux1no6j потому, что после применения к кубику цепи из N операций Райт/Лефт, будет достигнут однозначный результат
Только фамилия у него Черны, а не Черни
@kornet white другъ, какой сейчас год?
Ну и кликбейтные же вы превьюхи делаете!
Ничего не понял, но очень интересно.
P.s. хочу стать физиком ядерщиком ПАМАГИТЕ с обучением.
учись
зачем?
@@TurboGamasek228 бизнесом?
@@Sergey-Primak чтоб сходить в свой пту и наплевать на однокашников
@@moodnight8538 чачачача
Не Черни, а Чёрного
Саши Чёрного?
Блин, вот если бы политиканы вот такими задачами занимались, были бы такие же светлые люди. А так занимаются.... материться не хочется. Как же человечество просветлённое далеко от зла, и кажется, зло - во многом -оттого, что ущербные люди пытаются самоутвердиться всякой.... а умные люди вот, интересными вещами занимаются и не меряются тем единственным, что есть у политиканов.
да, если я буду в думе, буду и там читать лекции по математике !!!
2+2=5. теорема пуанкаре - перельмана 🤥.🌎🙃
Так, стоп, это же фамилия композитора 😑
Гипотеза черни звучит, как собирательный образ левых идеологий.
Пхахаххах
Черни это злой этюдодел, ученик Бетховена. А не вот это вот....
Почему злой? Надо много помучиться, и начнет нравиться :)
Савватан рулит!!!
крутим баранку :-)))!! Спасибо!!