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