∀ x, y, z

Вход Регистрация
Главная Инфотека Форум Регистратура Онлайн О сайте Правила Контакты Ещё…
Главная ≫ Инфотека ≫ Математика ≫ Видео ≫ Счёт вслепую // Михаил Раскин

Счёт вслепую

Михаил Раскин

Комментарии: 0
Часть 1

Часть 2

Часть 3

Часть 4

Пользуясь цифрами $0$ и $1$, несложно записать натуральное число. Сложение в столбик позволяет прибавить к этому числу единицу. Такой способ записи и изменения числа требует в некоторых ситуациях прочитать и изменить все цифры.

А если число большое и мы хотим читать и писать поменьше цифр, но можем быстро запросить любые цифры числа «вразбивку»? Разумеется, придётся изменить представление числа. С середины 20-го века известны коды Грея; нам всё равно потребуется иногда читать число целиком, зато менять надо будет лишь по одной цифре за раз.

А можно ли прибавить к числу единицу, не читая всего числа? Оказывается, можно. Известен способ, при котором увеличение числа из $n$ двоичных цифр на каждом из $2^n$ шагов оставляет непрочитанной одну цифру. Можно ли лучше? Наверное чуть лучше можно, точно не знаю. Но хотя бы половину цифр прочитать придётся. Причём увеличить запись, тратящую $n+1$ цифру на числа от $1$ до $2^n$, можно прочитав лишь около $\log n$ цифр, но вот если использовать все комбинации, то придётся читать не меньше $\frac{1}{2}n$.

Конструкции — после того, как они были один раз предъявлены — объясняются совсем просто; а для нижней оценки надо пошаманить с перестановками и их чётностью, чем мы и займёмся.

Предварительных знаний не потребуется. Я надеюсь, что всем слушателям удастся понять из рассказанного не меньше, чем они пожелают.

Примерная программа курса:

  1. Коды Грея (прибавление единицы с изменением только одной цифры).
  2. Запись чисел, бинарные деревья принятия решений и сложность операций.
  3. Бинарные диаграммы принятия решений: ещё один канонический вид для функций с бинарными аргументами
  4. Нижняя оценка класса «совесть надо иметь»: почему нельзя надеяться прочитать меньше логарифмического количества цифр.
  5. Увеличение чисел в экономной записи без чтения целиком: что сказал полный перебор и как это запомнить.
  6. Почему в экономной записи придётся прочитать половину цифр: перестановки, параллельные переносы и чётность.
  7. Увеличение чисел без чтения целиком: медленное сложение в столбик для случая с лишней цифрой.
  8. Прибавление единицы для записей, тратящих $n$ цифр на «почти» $2^n$ значений.

Материалы к лекции: Часть 1 (pdf, 27 KB); Часть 2 (pdf, 21 KB); Часть 3 (pdf, 20 KB); Часть 4 (pdf, 18 KB).

Литература:

  1. Gerth Stølting Brodal, Mark Greve, Vineet Pandey, Srinivasa Rao Satti. Integer representations towards efficient counting in the bit probe model. J. Discrete Algorithms 26: 34-44 (2014).
  2. Mikhail Raskin. A linear lower bound for incrementing a space-optimal integer representation in the bit-probe model. International Conference in Automata, Logic and Programming. (ICALP 2017).

Раскин Михаил Александрович.

Летняя школа «Современная математика», г. Дубна, дом отдыха «Ратмино»
21-27 июля 2017.
Комментарии: 0

Теги

#ВИДЕО #математика #арифметика #Михаил_Раскин #ЛШСМ

Похожее

  • Случайно существующие объекты (вероятностные доказательства существования)
    Михаил Раскин
    Иногда мы хотим доказать, что какой-нибудь объект существует. Разумеется, можно медленно и методично объект построить. Но это что-то делать надо, а хочется получить кое-что задаром. Поэтому мы просто возьмём случайный объект и заметим, что он подходит с ненулевой вероятностью. Это позволяет избежать занудной конструкции. Заодно можно спрятать в доказательстве незаметную ошибку. Для понимания курса нужно будет знать определение независимых событий. Понимать, что это такое, не обязательно, всё равно в ходе курса такое понимание (или только его иллюзию?) можно будет утратить.
  • Игрушечные примеры игр
    Михаил Раскин
    Теория игр — наука, изучающая принятие решений, особенно принятие решений в условиях зависимости достигаемого результата от действий других участников процесса. При этом «счастье для всех, даром и пусть никто не уйдёт обиженным» как правило невозможно по правилам — хотя ещё обиднее, когда оно возможно, но заведомо не случится. Изучаются же в каком-то смысле «достижимые» и «устойчивые» ситуации — так называемые равновесия. В интересующих нас играх часто можно выписать все сценарии развития событий, но после этого всё равно ещё остаются вопросы. С этой точки зрения шахматы одновременно слишком сложны — много позиций — и слишком просты — полный перебор сразу определил бы оптимальную стратегию для каждой позиций. Так как курс не построен вокруг одного понятия или утверждения, по пожеланиям слушателей возможны значительные изменения программы.
  • Множество условностей и условность множеств
    Михаил Раскин
    Все мы знаем, что математика доказывает импликации. Другими словами, мы доказываем не то, что какое-то утверждение верно, а то, что оно следует из принятых нами аксиом. Но при этом часто недооценивается, насколько сильно можно поменять набор аксиом. Одно из базовых понятий математики, на которых видна степень условности выбора конкретного набора аксиом – понятие множества. Сначала оно казалось совершенно очевидным. К сожалению, этот подход привёл к противоречиям. После этого стали развиваться разные способы работать со множествами не приходя к парадоксам. Понятие множества используется во многих разделах математики, из-за чего работать со множествами обычно учат постепенно, по кусочкам добавляя факты как естественные и самоочевидные основы, пока не получится теория, носящая имя ZFC. Из-за этого часто оказывается заметён под ковёр тот факт, что ZFC лишь один из возможных вариантов и что замена оснований теории множеств совсем не обязана рушить другие разделы математики. Курс будет посвящён рассказу о том, что может быть проблемой при пользовании какой-то аксиоматикой и сколь разнообразны варианты. Предварительные требования будут изменены в соответствии со знаниями и интересами аудитории; я надеюсь, что обозначения →, ∀, ∨, ∈, ∈, ∪, … всё же всем знакомы и привычны настолько, что ошибочно кажутся понятными.
  • «Мы не можем ждать милостей от природы», или применение метода вынуждения в построении моделей теории множеств
    Михаил Раскин
    В теории множеств есть несколько известных вопросов о том, следует ли из некоторых аксиом другая аксиома (или гипотеза; аксиома — это просто гипотеза, которой пользуется подавляющее большинство). Как и в других областях математики, недоказуемость можно продемонстрировать с помощью модели, в которой верны предположения, но не верна гипотеза. Для построения одного из самых известных таких примеров, модели теории множеств, в которой есть промежуточная мощность между мощностями натурального ряда и вещественной прямой, Коэн разработал метод вынуждения.
  • «Кто я? Где я?», или предположения о вероятностных выборках
    Михаил Раскин
    При решении вероятностной задачи мы обычно начинаем с каких-то предположений о распределениях вероятностей. Зачастую естественно один раз зафиксировать эти предположения и дальше задавать разные вопросы. В этом курсе предлагается отвечать на один и тот же вопрос, немного меняя предположения. Нужно заранее хорошо представлять себе, что такое условная вероятность, математическое ожидание, дисперсия. В конце курса понадобится поверхностное представление об аксиоматике теории вероятностей в общем случае. Ещё нужно нужно не бояться разбираться в ситуации, где каждый возможный ответ противоречит здравому смыслу.
  • «К гадалке не ходи…»
    Михаил Раскин
    Вероника сидит в комнате. На улице дождь. Вероника ставит ТеХ и смотрит фехтование. Ей многое интересно. Когда закончится дождь? Не повисла ли установка ТеХа? Будет ли следующая атака по корпусу или по маске? Конечно, чтобы узнать ответ наверняка, Веронике придётся подождать. Двое физиков порождают случайный шум. Один ищет радиочастоту, где сигнал не портит помехи, его соседка водит счётчиком Гейгера. Есть много ситуаций, когда знание, происходящего не позволяет нам предсказывать дальнейшее. Я постараюсь объяснить, откуда (и как по-разному) они берутся.
  • Непрерывные дроби
    Максим Казарян
    Непрерывная дробь — это выражение вида a0+(1/(a1+1/(a2+(1/(a3+… ))))), (конечное или бесконечное), где ai — натуральные числа. Выражения такого вида выглядят довольно забавными, но важность их заключается вовсе не в этом, а в том, что теория непрерывных дробей — это теория наилучших приближений иррациональных чисел рациональными. Например приближениие π≈22/7 точнее, чем более привычное 3,14=314/100, несмотря на то, что у первого знаменатель гораздо меньше второго. Каким образом это происходит, будет объяснено на занятиях.
  • Знак гауссовой суммы
    Владимир Успенский
    Эту формулу нашел Гаусс, он использовал ee в одном из своих доказательств квадратичного закона взаимности. Лишь через несколько лет он сумел доказать, что сумма S_m всегда положительна, так что S_m рано квадратному корню из m. Гаусс записал в дневнике, что его озарение было подобно “вспышке молнии”. Позднее многие известные математики предложили свои доказательства. Одно из самых элегантных принадлежит Дирихле, оно использует ряды Фурье. Предполагается знакомство с понятием сравнения по модулю. Полезно (но необязательно) иметь представление о малой теореме Ферма и о квадратичных вычетах по простому модулю. Знакомства с рядами Фурье не предполагается, необходимые сведения будут сообщены.
  • Способы проверки простоты числа
    Keith Conrad
    Когда Гаусс написал в 1801 г., что «Проблема различения простых и составных чисел и разложения последних на простые сомножители, как известно, является одной из самых важных и полезных в арифметике» он не знал, что 200 лет спустя эта проблема будет иметь огромное значение для криптографии: ее приложениями каждый день пользуются миллионы людей. Мы обсудим, как проверить простоту целых чисел детерминированными и вероятностными алгоритмами. От слушателей потребуется знакомство с арифметикой вычетов, включая малую теорему Ферма.
  • А нужен ли выбор? (альтернатива аксиоме выбора в теории множеств)
    Михаил Раскин
    Современная математика в качестве своего основания использует теорию множеств. Традиционно при анализе теоретико-множественных тонкостей используется аксиоматика Цермело-Френкеля с аксиомой выбора, обозначаемая ZFC. На аксиому выбора опираются доказательства наличия базиса в любом векторном пространстве и существования неизмеримого множества в математическом анализе. К сожалению, теория множеств обязана работать и со множествами, которые не описываются достаточно подробно и конкретно, чтобы мы могли себе их представить. В курсе будет рассмотрен один пример, к чему это приводит. Оказывается, ценой ослабления аксиомы выбора можно получить теорию множеств, в которой любая ограниченная функция на отрезке интегрируема по Лебегу. То, что используется аксиома выбора, в каком-то смысле, произошло исторически. Курс основан на статье Р.М. Соловэя о построении теории множеств, в которой все множества вещественных чисел измеримы.
Далее >>>
Главная ≫ Инфотека ≫ Математика ≫ Видео ≫ Счёт вслепую // Михаил Раскин