RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ЛИЧНЫЙ КАБИНЕТ
Видеотека
Архив
Популярное видео

Поиск
RSS
Новые поступления





Для просмотра файлов Вам могут потребоваться






XVII летняя школа «Современная математика», посвященная памяти Виталия Арнольда, 2017
27 июля 2017 г. 15:30, г. Дубна, дом отдыха «Ратмино»
 


Счёт вслепую. Занятие 4

М. А. Раскин

Количество просмотров:
Эта страница:6

Аннотация: Пользуясь цифрами 0 и 1, несложно записать натуральное число. Сложение в столбик позволяет прибавить к этому числу единицу. Такой способ записи и изменения числа требует в некоторых ситуациях прочитать и изменить все цифры.
А если число большое и мы хотим читать и писать поменьше цифр, но можем быстро запросить любые цифры числа «вразбивку»? Разумеется, придётся изменить представление числа. С середины 20-го века известны коды Грея; нам всё равно потребуется иногда читать число целиком, зато менять надо будет лишь по одной цифре за раз.
А можно ли прибавить к числу единицу, не читая всего числа? Оказывается, можно. Известен способ, при котором увеличение числа из $n$ двоичных цифр на каждом из $2^n$ шагов оставляет непрочитанной одну цифру. Можно ли лучше? Наверное чуть лучше можно, точно не знаю. Но хотя бы половину цифр прочитать придётся. Причём увеличить запись, тратящую $n+1$ цифру на числа от 1 до $2^n$, можно прочитав лишь около $\log n$ цифр, но вот если использовать все комбинации, то придётся читать не меньше $\dfrac12 n$.
Конструкции — после того, как они были один раз предъявлены — объясняются совсем просто; а для нижней оценки надо пошаманить с перестановками и их чётностью, чем мы и займёмся.
Предварительных знаний не потребуется. Я надеюсь, что всем слушателям удастся понять из рассказанного не меньше, чем они пожелают.

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


Website: https://www.mccme.ru/dubna/2017/courses/raskin.html
Цикл лекций

ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru
 
Обратная связь:
 Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2017