Харитоновские чтения 2010, информатика

Саров. 26 февраля 2010. Внимательно слушали презентации и задавали вопросы авторам представленных работ по информатике: главный программист Вадим Башуров, главный программист Николай Дегтяренко, начальник отдела Александр Кибкало и я безработный.

На конференции был продемонстрирован хороший уровень докладов и решаемых школьниками проблем. По сравнению с предыдущей конференцией представлено больше задач, решенных с помощью С++, и больше кода, разработанного для многоядерных процессоров. Участники конференции были активны и задавали много вопросов. Особенно активным оказался Артем Стукан из Нижнего Новгорода.

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

Гудулин Александр. Саров. Параллельная реализация алгоритма Дейкстры.

Александр представил решение задачи, суть которой заключается в нахождении кратчайшего пути от одного узла графа до другого с использованием известного алгоритма Дейкстры. Структура описания узла включает его условные координаты, вес, и признак того, что узел пройден. Матрица смежности представлена числами 0 и 1. Распараллеливание выполнено с помощью OpenMP. Ускорение, полученное за счет распараллеливания на 2-х ядерной машине едва заметно. Этого можно было ожидать, так как операции, выполняемые при обходе узлов, просты - сравнить и сложить, и сравнимы с затратами на организацию многопоточности. Тем не менее, этот факт важно было обнаружить во время реального исполнения кода чтобы учитывать его в будущем как ограничение эффективного распараллеливания. Отвечая на вопросы, Александр отметил, что коллизий при обработке потоками данных одного и того же узла не должно возникать, так как данные объявлены с помощью прагм OpenMP приватными; а в случае одинокого веса узлов выбирается ближайший в оперативной памяти, видимо, в массиве данных.

Зотова Ульяна. Нижний Новгород. Применение показателя Херста для прогнозирования поведения временных рядов.

льяна рассказала о том, как можно охарактеризовать и прогнозировать протекание различных процессов: от биения сердца до изменения солнечных пятен и котировок акций, с помощью нормированного размаха изменяемых данных - показателя Херста. Применимость метода к таким различным задачам объясняется тем, что метод анализирует внешние проявления процессов и не использует знание особенностей исследуемой системы. Реализация метода проверялась на модельных сигналах: недетерминированных - псевдослучайных данных, и детерминированных - синусоидальном сигнале. Рассчитанные значения нормированных отклонений логарифмируются и аппроксимируются прямой с помощью метода наименьших квадратов. Наклон прямой и есть искомый показатель. Интересной оказалась история создания метода. Херст прожил на берегах Нила 40 лет, наблюдая за колебаниями уровня полноводной реки и пытаясь предсказать требуемый сброс воды на нильской плотине. 

Ульяна уверенно отвечала на вопросы, в частности, о возможности прогнозировать температуру в Нижнем Новгороде, зная ее изменения за 200 лет. Данные для обработки могут не только генерироваться в программе, но и читаться из файла. Следовательно, можно анализировать и уровни температур и цены на нефть. Мы выяснили, что Ульяна предпочитает линейную аппроксимацию из-за лучшей точности, хотя сам метод подразумевает именно линейную. На вопрос Вадима, заработала ли она на бирже, было сказано, что нет, потому что не было такой задачи. Действительно, в этом возрасте нужно накапливать знания, чтобы позднее стать сильным и высокооплачиваемым экспертом. Ульяна была одна из немногих, кто использовал англоязычную литературу для решения задачи, в том числе и такую "горячую", как arXiv публикации.

Исаченко Александр. Нижний Новгород. Создание программ, развивающих логические и аналитические способности.

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

Далее он представил программу, решающую задачу 8-ми ферзей. Однако, понимая, что ему, как разработчику, удалось развить свои способности, мы остались без ответа на вопрос, как же развиваются логические и аналитические способности игроков, и чем отличается представленная программа от множества программ игры в шахматы, работающих на смартфонах и ноутбуках. Вадим даже в шутку потребовал, чтобы ему показали обученного и высокоразвитого с помощью этой программы школьника-игрока. Видимо, на следующую презентацию работы автор придет не один.

Кортюков Александр. Саров. Вопрос о создании эллиптического лазера.

Александр в своей работе попытался ответить на вопрос, можно ли внутри эллиптической поверхности получить параллельные лучи в случаях, если источник излучения расположен не в фокусе эллипса. Для идеального случая, когда луч испускается из точки фокуса, ответ есть. Ответ положительный и обосновывается так называемым биллиардным свойством эллипса. Для математического моделирования оптики эллиптического лазера Александр написал специальную программу, которая рассчитывает поведение лучей (координаты и углы) для двух рассматриваемых случаев - источник находится на оси левее и правее от фокуса. Результаты работы программы показывают, что при таких условиях (а они близки к реальным условиям) создание лазера "не имеет смысла". 

Александру было предложено рассмотреть и третий случай, в котором источник располагается в фокусе, для того, чтобы подтвердить наличие того самого биллиардного свойства и правильность реализации алгоритма. Одним из вопросов к Александру был вопрос о возможности срезать сосульки с помощью лазера. Ответ был категоричен - надо давать устройство грамотным людям, а не дворникам (хоть и ленинградским), которые способны и дом порезать на части.

Матвеева Светлана. Саров. Применение генетического алгоритма в криптографической системе RSA

Светлана решила найти эффективный способ взлома зашифрованных данных, который позволял бы разложение больших чисел на 2 простых множителя быстрее существующих методов, в том числе и метода простого перебора. Оригинальная идея заключается в том, чтобы использовать генетический алгоритм для поиска неизвестных сомножителей. Мы выяснили, что процесс мутации в реализованном алгоритме заключается в выборе таких простых чисел, произведение которых наиболее близко к исходному разлагаемому числу. Остальные отбрасываются. Сам я не поверил, что такая стратегия работает, как задумано. Имею в виду "близость" (абсолютная разность) полученного произведения к исходному в качестве критерия отбора. Скорее всего, такой поиск выходит на обычный перебор сомножителей. 

Программа по прежнему в разработке, сделаны оценки производительности. Результаты не очень показательны, так как даны только для 8-ми значных чисел, не больше. 

Светлана полна энтузиазма и уверенности, что метод работает, и что он покажет свое преимущество в реальном деле. Пожелаем ей успеха.

Савиных Александр. Нижний Новгород. Лаборатория создания роботов

Сразу заметим, речь идет о роботах программных. Александр рассказал о разработанной им программе, которая играючи обучает программированию. Роботы способны двигаться по лабиринтам и лопать яблоки. Лопать, судя по происходящему, - не в смысле поедать. Яблоки лопаются как шарики от прикосновения к ним робота. Александр продемонстрировал работу программы, объяснил, какие компоненты в нее входят, обосновал выбор некоторых из них, описал особенности реализации. В частности, ключевые свойства и компоненты программы таковы: ученик использует PascalScript для программирования поведения роботов; для рисования лабиринтов, роботов и яблок используется OpenGL; игра сопровождается музыкой или звуками, записанными в файлах MP3; программа работает в Linux и Windows; коды ученика сохраняются в файлах; коды программы для обеспечения гибкости в разработке и эксплуатации разделены и представлены в исполняемом файле и динамической библиотеке; написана и встроена в программу справочная система; создан инсталляционный модуль; сделаны оценки занимаемой памяти и приведены объемы кодов; и даже загрузка процессора оценена. 

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

Сластин Илья. Саров. Метод триангуляции для распознавания образов фигур

Идея метода у Ильи родилась благодаря работе Пабло Пикассо "Портрет Вильгельма Уде".

Аналогично технике великого художника мы можем воспроизвести любое изображение с помощью треугольников, и даже метод для этого уже создан - триангуляция. Что-то подобное этому подумалось Илье. В представленной работе автор предлагает дальнейшее развитие идеи - если любое изображение можно описать набором треугольников, значит можно сравнивать одно изображение с другим, а следовательно можно распознавать изображение, виденное раньше и сохраненное. 

Полезным применением метода по мнению автора может быть распознавание дорожных знаков. 

Осталось невыясненным, как выполняется сравнение распознавания, как строится контур, внутрь которого "бросаются" точки триангуляции со случайными координатами, и как чувствительно сравнение к повороту, яркости и размеру распознаваемого образа. 

Соврасов Владислав. Саров. Создание функций неточного поиска в больших массивах данных

Владислав представил вторую (возможно третью, так как распознавательная часть упущена) часть работы, знакомой нам из предыдущего выступления Ильи. Назовем ее "распознаванием дорожных знаков", потому что решение этой проблемы упоминается в двух последовательных выступлениях, и Илья ссылался на презентацию Владислава. 

Владислав говорил способности ребенка распознать круг, в отличие от компьютера, который только учиться этому, о выбранном языке программирования, выбран С++, и многопоточности в программе, реализована с помощью библиотеки pthreads. 

Однако, структура данных, как хранятся данные, как выполняется сравнение при распознавании, почему поиск "неточный" и насколько он неточный, почему при распознавании формы объекта имеют значение размеры объекта, все это осталось невыясненными. Так примерно и обещано в названии работы - "неточный поиск в большом массиве данных", есть место неопределенности и в материале доклада. 

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

Стукан Артем. Нижний Новгород. Создание насыщенных интернет-приложений и концепция перемещения ПО в сеть

Артем не первый раз представляет на Харитоновских чтениях свое видение мировых тенденций в разработке веб-приложений. Он не только знакомится с современными технологиями по публикациям, но и пробует программировать в каждой из них, чтобы, основываясь на собственных впечатлениях и выводах, рассказать о них на конференции. Вот и на этот раз Артем отметил появление новых интернет-приложений, например, Painter, работающий в браузере, и рассмотрел существующие программные средства, помогающие создавать "богатые" медиа-содержанием интернет приложения. Таких клиентских средств сегодня, на его взгляд, четыре: MS Silverlight, Adobe AIR, ajax и javafx; и останутся, то есть выживут из них только Silverlight и AIR.

Остальные не смогут развиться и удовлетворить стремительно возрастающие требования разработчиков и пользователей. На предполагаемую смерть ajax Вадим пошутил, что Аякс уже умер 2000 лет назад. Затем мы обсудили возможности мобильных устройств, недостатки однозадачности многих из них, нашли "правду, как обычно посредине" между чисто веб-приложениями и традиционными десктоп-приложениями. Сам я разделяю оптимизм Эрика Шмидта относительно роли "облачных" вычислений в будущем, когда такие вычислительные задачи, как распознование речи и незаметная для беседующих по телефону трансляция с одного языка на другой, будут выполняться на серверах, доступных вашим мобильным устройствам. Тогда фавориты этого доклада, я имею в виду Silverlight и AIR, конечно, тоже должны будут умереть. Кстати, этот текст я пишу в Гугловском доке, чистом веб-приложении, работающем в Гугловском Хроме

Федоренко Яков. Саров. Компьютерный комплекс для исследование диаграмм направленности радиолюбительских антенн диапазона ДМВ

Яков представил сложный компьютерный комплекс, мы назвали его АРМ радиолюбителя, позволяющий любителям и профессионалам, работающим  на радиостанции Дома Творчества, исследовать диаграммы направленности многоэлементных ДМВ антенн. Комплекс состоит из множества компонентов: антенна, ПК, интерфейс к повортному устройству, устройство горизонтального поворота антенны, ДМВ передатчик и приемник; а также программное обеспечение управления антенной, моделирования свойств антенны, регистрации реальных диаграмм направленности и вывода их в графическом виде на экран. И все это работает вместе.

Интересно, что не смотря на хорошую точность моделирования параметров антенны с помощью программы mmana, реально измеренные параметры могут отличаться из-за особенностей рельефа и местоположения самой антенны. Следовательно, возьмись Яков помогать другим радиолюбительским коллективам диагностировать и настраивать антенны, придется везти весь комплекс на место ее установки. Это означает, что следующей темой развития комплекса может стать его мобильность. Любите радио.

Юкова Юлия. Саров. Разработка программного кода, обеспечивающего шифрование изображения методом WT стеганографии

Юлия предложила оригинальный способ сокрытия информации - тайнописи в изображениях. В отличие от криптографии, в стеганографии (при беглом первом чтении я ошибочно прочитал - стенография) скрывается и сам факт наличия информации. Шифруемая информация, например, передаваемое сообщение, записывается в младшие биты значений яркости точек изображения. Изменение этих битов, как правило, визуально заметить трудно, или невозможно. Исключением могут быть синтезированные изображения с постоянным значением яркости всей картинки или ее фрагментов. 

Для оценки пригодности изображения для шифрования Юлия использует специальный метод: выполняется вейвлетное преобразование, анализируется полученный высокочастотный компонент разложения, и определяется сколько разрядов занимает шум в изображении. Столько разрядов и можно использовать для шифрования данных.

Метод показал устойчивость к атакам, то есть к попыткам вскрыть информацию. Оценена производительность шифрования - время шифрования линейно зависит от числа точек в изображении, и сделан вывод о высоком быстродействии метода.

Юлия легко ответила на все вопросы, в частности, быстро оценила размер изображения по заданной длине сообщения, разрешила мое непонимание того, о чем мы говорим - шифровании или компрессии (шифрование сообщения, вейвлет преобразование не используется для сжатия изображения), и разъяснила, почему используется именно вейвлет преобразование (возможность легко оценить высокочастотную составляющую, которую предстоит разрушить, вписывая зашифрованное сообщение).

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

К сожалению, не все заявленные работы были представлены, например, методы самооценки профессиональной ориентации по Биркману и решение задач на трение с помощью Matlab. Знакомясь в интернете с базовыми понятиями последней темы наткнулся на "принцип наименьшего принуждения" Гаусса. Хорошо сказано, и, оказывается, гораздо раньше, чем мы услышали от президента.

В качестве замечания к проведению конференции: Как заметил Александр Кибкало, было бы полезно записывать презентации на диск и распространять их. Во многих случаях опубликованных тезисов не достаточно для понимания сути работ и их результатов; полезно, также, иметь в сборнике докладов электронные адреса участников.