Алгоритмические проблемы теоретической информатики.
Алгоритмические проблемы теоретической информатики.
Различные методы анализа случайных графов, построение новых математических моделей безмасштабных графов (подчиняющихся так называемому степенному закону) является актуальным направлением исследований, в связи с анализом сетей в интернете (в частности, социальных таких как Фейсбук, Твиттер и многих других). При этом их свойства и параметры таких сетей могут изменятся. Для предсказания таких изменений и служит изучение общих свойств математических моделей таких сетей, которые можно рассматривать как случайные графы. Однако классическая теория Эрдеша-Реньи неадекватно описывает графы, возникающие в приложениях, в связи с чем стала развиваться теория безмасштабных случайных графов, в которых степени вершин распределены по так называемому степенному закону. Был предложен целый ряд моделей для порождения таких графов и несколько генераторов. Специфика задачи в том, что целью является порождение указанных графов с числом вершин порядка миллиарда. Чтобы достичь этого требуется разработка быстрых алгоритмов и использование параллельных вычислений.
Обфускацией программы называется всякое ее преобразование, которое сохраняет вычисляемую программой функцию (эквивалентное преобразование), но при этом придает программе такую форму, что извлечение из текста программа (программного кода) ключевой информации об алгоритмах и структурах данных, реализованных в этой программе, становится трудоемкой задачей. В отличие от традиционных видов шифрования обфускация не предполагает построения эффективных алгоритмов расшифрования, т.е. восстановления исходного текста программы, но зато требует сохранения смысла зашифрованного сообщения – функции, вычисляемой обфускируемой программой. Поэтому задача обфускации программ может быть также отнесена к области криптографии и криптоанализа. Именно двойственность этой задачи и объясняет тот факт, что ее исследование вот уже более 15 лет проводится по двум направлениям – со стороны системного программирования и со стороны криптографии, – которые очень мало взаимодействуют друг с другом.
При изучении математической проблемы обфускации программ начинать нужно с определения стойкости обфускации, которые существенно зависят от тех приложений, в которых используется обфускация.
Исполнитель
Перейти к списку всех проектов 