При передаче и хранении информация портится (шум в телефонной трубке, ошибки жесткого диска и так далее). Чтобы восстановить исходное сообщение в систему передачи следует ввести избыточность, иными словами, передавать вместо него более длинное закодированное сообщение. Так возникает понятие корректирующего кода (кода, исправляющего ошибки). Математически это приводит к задаче упаковки шаров в конечномерном векторном пространстве над конечным полем. Эта задача, в свою очередь, оказывается в значительной части эквивалентна проблеме расположения точек в проективном пространстве “в наиболее общем положении”. Здесь уже недалеко и до алгебраической геометрии. Конструкцию кодов по алгебраической кривой нетрудно рассказать, когда эта кривая — прямая.

Теория информации — математическая дисциплина, в которой одновременно применяются методы многих разделов математики: теории вероятностей, теории алгоритмов, комбинаторики. Она занимается, в числе прочих, вопросами — как лучше всего сжать файл? Сколько информации может содержать данное сообщение? Как возможно точно передать сообщение, несмотря на помехи в канале связи? Как защитить сообщение от несанкционированного доступа? Ключевые идеи о том как решать перечисленные задачи были изложены в статье К. Шеннона «Математическая теория информации», где впервые было введено понятие энтропии (количества информации) и намечены контуры будущей теории. Мы займёмся введением в теорию сжатия дискретных данных (в отличие от непрерывных; там — своя специфика). Рассмотрим несколько алгоритмов, которые применяются в универсальных архиваторах (zip, rar). А также сделаем первые шаги (определим понятия и докажем начальные теоремы) на пути, ведущем к теоретическому обоснованию эффективности этих алгоритмов.

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

Ященко Иван Валериевич, кандидат физико-математических наук. Летняя школа «Современная математика», г. Дубна, 2003 г.

Автоморфизм n-мерного аффинного пространства — это отображение (x_1,…,x_n) → (f_1,…,f_n), где f_i — многочлены от переменных x_1,…,x_n, для которого существует обратное отображение, также заданное многочленами. Мы начнем с полного описания автоморфизмов прямой, проблему якобиана. Определим ручные и дикие автоморфизмы, докажем, что все автоморфизмы плоскости являются ручными, и немного поговорим о доказательстве теоремы Шестакова и Умирбаева (2004) о том, что автоморфизм Нагаты трехмерного пространства (1972) является диким. Также мы обсудим свойство бесконечной транзитивности действия группы автоморфизмов и его связь с локально нильпотентными дифференцированиями. Будет сформулирован ряд известных открытых проблем аффинной алгебраической геометрии: проблема сокращения, проблема выпрямления, проблема линеаризации для торов и ее связь с градуировками.

В алгоритмической теории информации колмогоровская сложность объекта (такого, как текст) есть мера вычислительных ресурсов, необходимых для точного определения этого объекта. Колмогоровская сложность также известна как описательная сложность, сложность Колмогорова — Хайтина, стохастическая сложность, алгоритмическая энтропия или алгоритмическая сложность.

Классическая теорема Бойяи–Гервина (1830-е годы) утверждает, что любые два многоугольника равной площади равносоставлены друг с другом: первый многоугольник можно разрезать на конечное число многоугольных частей и затем сложить из этих частей второй многоугольник. Ещё Гаусс задавал вопрос, верно ли аналогичное утверждение для многогранников. А именно, его интересовало, можно ли доказать стандартную формулу для объёма пирамиды (одна треть произведения длины высоты на площадь основания) без использования предельного перехода, то есть разбив пирамиду на конечное число кусков, из которых можно сложить прямоугольный параллелепипед.

Произведение элементов пишут в виде слова, изображаемого отрезком. А что значит умножить элементы по кругу? Какой смысл имеет мозаика, составленная из таких кругов? Понимание такого рода вещей приводит к решению ряда открытых вопросов. Например, допустим мы хотим задать конечным числом соотношений полугруппу в которой степень любого элемента равна нулю. Конечным числом запрещенных подслов на прямой нельзя добиться того, чтобы были сколь угодно длинные слова без запрещенных подслов и в то же время не было таких периодических слов. В то же время на плоскости существуют конечные системы запретов допускающие только апериодические замощения. Но как умножать с разных сторон? Эти и другие вопросы предполагается обсудить.

Энтропия — мера неопределённости, мера хаоса. В естественных науках это мера беспорядка системы, состоящей из многих элементов; в теории информации — мера неопределённости какого-либо опыта, процесса или испытания, которые могут иметь разные исходы (а значит, мера количества информации); в математике — мера сложности объекта или процесса. Понятие энтропии было впервые введено в 1865 году Р. Клаузиусом в термодинамике, К. Шенноном в теории информации в 1949 г., в теории стохастичпеских процессов Колмогоровым, Гельфандом и Яглом в 1956 г., в функциональном анализе и теории динамических систем Колмогоровым в 1956–1958 гг. Между мирами полной детерминированности, изучаемой классическим анализом и миром хаоса, изучаемым теорией вероятностей, ныне перекидывается мост, который связан с понятием энтропии.

RSA (аббревиатура от фамилий Rivest, Shamir и Adleman) — криптографический алгоритм с открытым ключом, основывающийся на вычислительной сложности задачи факторизации больших целых чисел. Алгоритм используется в большом числе криптографических приложений, включая PGP, S/MIME, TLS/SSL, IPSEC/IKE и других.