Мне трудно полностью ответить на Ваш вопрос, так как я сам хожу на эти лекции, а не читаю их. Описание курса было составлено лектором. Данные сжимаются за счет того, что в них встречаются повторы, а комбинаторика слов изучает повторы и преобразования, которые эти повторы выявляет. Кроме сжатия данных уже были рассказаны примеры связанные с поиском образца в строке на лету, когда строка поступает в реальном времени, эффективное построение индекса для больших данным (такой индекс занимает места столько же, сколько сами данные и поиск в этой структуре выполняется очень быстро).
Про логи был анонсирован пример, который используется в робототехнике, т.е. слово — это последовательность действий робота и с помощью комбинаторики слов решается какая-то задача управления.
Этот курс лекций не ставит цели обучить навыкам программирования, он посвящен математическому аппарату, который используется в комбинаторике слов. А комбинаторика слов в свою очередь имеет множество практических приложений, например для сжатия данных. Основная польза от этого курса — получение глубокого понимания того, как устроены методы работы со строками, какие существуют проблемы, как их решают, и почему именно так.
Лемма Фаркаша, конечно, верна в обе стороны: система неравенств несовместна тогда и только тогда, когда можно сложить неравенства с неотрицательными коэффициентами и получить противоречивое неравенство 0≥1. Я сформулировал неочевидную импликацию (которая утверждает, что доказать таким образом всегда можно), в обратную сторону лемма очевидна: если уж вывели противоречие, то понятно, что система несовместна. Но формально вы правы.
Это хороший вопрос. Я попробую пояснить на примере. Пусть алиби — это распечатка местонахождения телефонного аппарата, которую выдал сотовый оператор. Будем считать, что сотовый оператор выдал эту распечатку в стандартном виде на флешке вместе с электронной подписью корректности этой выписки. Можно написать программу, которая получает на вход ФИО человека и такую распечатку и проверяет, что 1) электронная подпись корректная 2) человек ФИО, действительно, был далеко от места преступления в нужное время. Если проверка проходит, то программа выдает 1, если не проходит по какой-либо причине, то выдает 0. Если программа выдает 1, значит алиби подтверждено. Эту программу судья просит написать независимого программиста и исходные коды этой программы открыты, все могут убедиться, что она делает то, что должна делать. Эта программа задает систему доказательств для множества людей, которые в момент преступления были далеко от места преступления и у них был включен телефон. Нетрудно понять, что такая программа будет работать полиномиальное от длины входа время. А это значит, что множество людей M, невиновность которых можно доказать с помощью этой программы лежит в классе NP. А как я писал в статье, для любого языка из класса NP можно построить интерактивное доказательство с нулевым разглашением.
Могу даже примерно описать, как будет выглядеть это интерактивное доказательство. Во-первых, выбирается конкретный NP-полный язык, для которого удобно строить доказательства с нулевым разглашением. Этот язык 3COL — множество графов, вершины которого можно правильным образом раскрасить в 3 цвета (правильным образом — это когда две вершины, соединенные ребром, покрашены в разные цвета). Доказательством принадлежности этому языку будет сама раскраска. Для этого языка есть доказательство с нулевым разглашением, его я опишу в самом конце. Поскольку 3COL — это NP-полный язык, значит к нему сводится любой другой язык из класса NP, в том числе и язык M. Судья заказывает программисту сведение языка M к языку 3COL, он пишет эту программу и опять же код этой программы любой может проверить. Что делает это сведение? Оно отображает ФИО человека в граф, если человек обладает алиби, то этот граф будет 3-раскрашиваемым, если не обладает, то не будет 3-раскрашиваемым. Также можно написать программу, которая довольно быстро по содержимому флешки выдаст раскраску графа. Эту раскраску обвиняемый не должен никому сообщать, поскольку, возможно, из нее можно извлечь какую-то информацию с флешки.
Теперь как же всем продемонстировать, что граф красится в 3 цвета, не предъявляя раскраску? В зал судебного заседания выносится большой холст, на котором нарисован граф, посчитанный программой. Обвиняемый случайным образом переставляет цвета своей раскраски и пишет в вершине ее цвет вершины, но закрывает вершину тут же сверху фишкой, из под которой не видно, что написано в вершине. После чего предлагает прокурору выбрать любое ребро графа, прокурор выбирает, обвиняемый снимает две фишки под концами этих ребер. Если получились одинаковые цвета, то доказательство ложное, поскольку две вершины, соединенные ребром, должны быть покрашены в один цвет. Теперь допустим, что раскраски не существует, тогда хотя бы одним ребром можно уличить преступника. Если ребер m, то если прокурор будет выбирать ребро случайным образом, то ему повезет с вероятностью 1/m. Значит, надо этот процесс повторить 10m раз. Перед каждым повторением процесса обвиняемый перемешивает случайным образом цвета и меняет пометки вершин. Вероятность того, что все 10m раз преступнику будет везти, не превосходит (1-1/m)10m<e-10.
Да, бывают верные теоремы, которые нельзя доказать. Но я имел в виду множество истинных утверждений, так как иначе пришлось бы отдельно говорить о том, что значит доказуемое в математическом смысле утверждение, а этого делать в этой статье не хотелось.
Про логи был анонсирован пример, который используется в робототехнике, т.е. слово — это последовательность действий робота и с помощью комбинаторики слов решается какая-то задача управления.
Материалы лекций появляются тут: compsciclub.ru/course/wordscombinatorics
Видеозаписи через некоторое время появятся тут: www.lektorium.tv
Могу даже примерно описать, как будет выглядеть это интерактивное доказательство. Во-первых, выбирается конкретный NP-полный язык, для которого удобно строить доказательства с нулевым разглашением. Этот язык 3COL — множество графов, вершины которого можно правильным образом раскрасить в 3 цвета (правильным образом — это когда две вершины, соединенные ребром, покрашены в разные цвета). Доказательством принадлежности этому языку будет сама раскраска. Для этого языка есть доказательство с нулевым разглашением, его я опишу в самом конце. Поскольку 3COL — это NP-полный язык, значит к нему сводится любой другой язык из класса NP, в том числе и язык M. Судья заказывает программисту сведение языка M к языку 3COL, он пишет эту программу и опять же код этой программы любой может проверить. Что делает это сведение? Оно отображает ФИО человека в граф, если человек обладает алиби, то этот граф будет 3-раскрашиваемым, если не обладает, то не будет 3-раскрашиваемым. Также можно написать программу, которая довольно быстро по содержимому флешки выдаст раскраску графа. Эту раскраску обвиняемый не должен никому сообщать, поскольку, возможно, из нее можно извлечь какую-то информацию с флешки.
Теперь как же всем продемонстировать, что граф красится в 3 цвета, не предъявляя раскраску? В зал судебного заседания выносится большой холст, на котором нарисован граф, посчитанный программой. Обвиняемый случайным образом переставляет цвета своей раскраски и пишет в вершине ее цвет вершины, но закрывает вершину тут же сверху фишкой, из под которой не видно, что написано в вершине. После чего предлагает прокурору выбрать любое ребро графа, прокурор выбирает, обвиняемый снимает две фишки под концами этих ребер. Если получились одинаковые цвета, то доказательство ложное, поскольку две вершины, соединенные ребром, должны быть покрашены в один цвет. Теперь допустим, что раскраски не существует, тогда хотя бы одним ребром можно уличить преступника. Если ребер m, то если прокурор будет выбирать ребро случайным образом, то ему повезет с вероятностью 1/m. Значит, надо этот процесс повторить 10m раз. Перед каждым повторением процесса обвиняемый перемешивает случайным образом цвета и меняет пометки вершин. Вероятность того, что все 10m раз преступнику будет везти, не превосходит (1-1/m)10m<e-10.