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

Счёт вслепую

М. А. Раскин планирует провести 3-4 занятия.

Доступны 4 видеозаписи курса.

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

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

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

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

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

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

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

E-mail оргкомитета:

dubna@mccme.ru