Аннотация:
Данная заметка представляет собой переработанный конспект лекции (с задачами, решения многих из которых были разобраны на лекции), прочитанной в школе №57 г. Москвы школьникам 11д класса в 2006 году и повторенной школьникам 11в класса в 2008 году. Она основана на находящейся в стадии написания книге по колмогоровской сложности В. А. Успенского, Н. К. Верещагина, А. Шеня [2], которую тем не менее можно рекомендовать для дальнейшего чтения по этой теме, см. файлы по ссылке.