Заседания 2009/2010 учебного года

27 мая 2010
(четверг 17-20 каб. А.Н. Терехова)

проф. Краснопёрова Марина Абрамовна
О некоторых аспектах кибернетического моделирования ритмики текста

Ритмика текста является уникальным явлением, в котором находят формальное отражение результаты функционирования внутренних процессов и механизмов, действующих на стыке мышления и языка. Наиболее четко это проявляется в стихотворном тексте. Строго выраженная организация ритмообразующих конструкций позволяет изучать их объективными методами, Изучение данного явления вызывает интерес не только филологов, но и специалистов в области точных наук, прежде всего, математиков. К ним относятся поэт и математик А. Белый, математик и филолог Б. В. Томашевский, выдающийся русский математик  А. Н. Колмогоров и другие ученые.

Автор доклада, специалист по математической лингвистике, начинала свои занятия в области ритмики в Московском  университете под руководством А. Н. Колмогорова. Ею создана теория реконструктивного моделирования стихосложения на данном уровне текста. В докладе дается общая характеристика теории и ее центральной модели (порождения и восприятия ритмической структуры  стиха – МПВ).  Рассматриваются наиболее важные аспекты испытания МПВ, анализируются некоторые задачи, связанные с компьтеризацией этой модели.

20 мая 2010
(четверг 17-20 каб. А.Н. Терехова)

проф. Гейн Александр Георгиевич (Екатеринбург)
Реформа обучения компьютерным дисциплинам студентов математического и компьютерного направлений: концепция и результаты

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

13 мая 2010
(четверг 17-20 каб. А.Н. Терехова)

Смирнов Арсений Юрьевич
Алгоритмы преобразования деревьев с помеченными листьями

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

Пусть есть два дерева T и T' с одинаковым числом листьев, помеченных с использованием одного и того же набора меток. В частности, это означает, что между листьями T и T' установлено взаимно однозначное соответствие. В T разрешается последовательно стягивать какие-то пары внутренних вершин. Требуется получить дерево, изоморфное T' (с учетом того, что биекция между листьями задана изначально), или показать, что искомого преобразования не существует.

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

6 мая 2010
(четверг 17-20 каб. А.Н. Терехова)

Зеленчук Илья Валерьевич, Малец Андрей Александрович, Хозов Андрей Валерьевич (Екатеринбург)
Управление предоставлением ресурсов МВС: от принципов к реализации

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

Опыт применения системы управления пропуском пакетных задач в Межведомственном суперкомпьютерном центре (г. Москва) и вычислительном центре ИММ УрО РАН (г. Екатеринбург) показывает продуктивность найденных решений, а также вскрывает потенциальные возможности развития. Представляется, что продуктивным может стать обобщение понятия «ресурс», что должно быть подтверждено или отвергнуто практикой реализации новой системы управления предоставлением ресурсов МВС с предварительным названием RTBScheduler.

29 апреля 2010
(четверг 17-20 каб. А.Н. Терехова)

Кириленко Яков Александрович
О развитии прикладного синтаксического анализа, применяемых инструментах и алгоритмах

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

22 апреля 2010
(четверг 17-20 каб. А.Н. Терехова)

Вяткина Кира Вадимовна
О взвешенных диаграммах Вороного для прямых на плоскости

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

В докладе будут обсуждаться взвешенные диаграммы Вороного для прямых на плоскости. Мы рассмотрим случаи аддитивных и мультипликативных весов, а также их обобщение, при котором вес прямой l задается ассоциированной с ней линейной функцией f, а расстояние от произвольной точки q до l определяется значением f для аргумента, равного евклидову расстоянию от q до l. Предлагаемый подход к изучению диаграмм

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

Доклад будет основан на результатах, изложенных в работах:
G. Barequet, K. Vyatkina, "On Voronoi Diagrams for Lines in the Plane",
in Proc. ICCSA 2009, Yongin, Korea, June 29 - July 2, 2009, IEEE-CS, 2009, 159-168
K. Vyatkina, "On Constructing the Voronoi Diagram for Lines in the Plane under a
Linear-Function Distance", in Proc. ICCSA 2010, Fukuoka, Japan, March 23-26, 2010,
IEEE-CS, 2010, 192-200.

15 апреля 2010
(четверг 17-20 каб. А.Н. Терехова)

Гуревич Лев Станиславович
Методы оптимизации в обработке видео изображений

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

8 апреля 2010
(четверг 17-20 каб. А.Н. Терехова)

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

Процесс принятия решений сводится к задаче выбора наилучшей альтернативы из множества доступных по одному или нескольким критериям. Если альтернативы сравниваются по одному критерию, то можно представить решаемую задачу как задачу поиска минимума (максимума) некоторой функции. Если рассматривается несколько критериев, то нужно не только оценивать альтернативы относительно критериев, но и сравнивать критерии между собой.

Часто альтернативы и критерии нужно сравнивать по признакам, которые тяжело или невозможно представить в численном виде (например, привлекательность, важность, уровень подготовки). В таких случаях прибегают к методу попарных сравнений альтернатив и критериев между собой. Один из наиболее известных методов такого рода - метод анализа иерархий (analytic hierarchy process).

1 апреля 2010
(четверг 17-20 каб. А.Н. Терехова)

Булычев Дмитрий Юрьевич
Softening hardware development with HaSCoL

Развитие реконфигурируемых аппаратных платформ (прежде всего FPGA) достигло того уровня, при котором с их помощью оказалось возможным решать задачи, которые раньше не относились к области разработки аппаратного обеспечения (АО). В настоящее время известны примеры применения специализированных аппаратных плаформ для решения NP-трудных задач (SAT, TSP), для задач биоинформатики, обработки слабоструктурированных данных и т.д. В этом контексте традиционные инструмены разработки АО уже оказываются недостаточными по ряду причин.

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

В докладе будет рассмотрен высокоуровневый язык описания оборудования HaSCoL (Hardware-Software Codesign Language), его семантика, особенности применения и преимущества по сравнению как с традиционными языками описания АО, так и другими перспективными средствами.

25 марта 2010
(четверг 17-20 каб. А.Н. Терехова)

Полозов Виктор Сергеевич
Архитектуры клиентских платформ веб-приложений

Клиентское веб-приложение — это приложение, доступное через интернет, и обладающее функциональностью традиционных настольных приложений, не поддерживаемой браузером непосредственно. На сегодняшний день существует несколько платформ для создания таких приложений, например Java applets, Flash, Silverlight, JavaFX и другие.

В докладе будет рассмотрена история развития, мифология и технологические особенности платформ для создания клиентских веб-приложений. Особое внимание будет уделено языко-ориентированному подходу к разработке платформы на примере технологии Silverlight.

11 марта 2010
(четверг 17-20 каб. А.Н. Терехова)

Суворов Владимир Александрович
Гуманоидный интерфейс и его использование для интеграции приложений

Для предоставления внешнего интерфейса на этапе разработки возможно использовать множество стандартных технологий: SOAP, REST, RPC, DCOM, CORBA, WCF. В докладе рассматриваются существующие технологии и проблемы их использования. Предлагается к рассмотрению альтернативная технология взаимодействия с приложением - на основе программной имитации действий пользователя. Данная технология успешно применяется для задач тестирования приложений, но практически не используется для решения задачи интеграции. Выделяются вопросы распознавания элементов управления и данных в десктопных и веб-приложениях. Приводятся существующие примеры использования (RoboForm, AutoMouseClicker, AutoIt системы тестирования).

В качестве работающего прототипа с открытым кодом, предлагается создать промежуточный слой: приложение - WCF сервис, который с одной стороны будет включать в себя протокол взаимодействия со сторонней программой (визуальный/Http/DLL), а с другой стороны предоставлять WCF сервис, на основе которого может быть построена гибкая структура взаимодействия приложений. Это позволит, с одной стороны использовать готовую и применяемую технологию, а с другой стороны существенно расширит ее возможности для интеграции любых приложений в визуальном режиме.

3 марта 2010
(среда 17-20 каб. А.Н. Терехова)

Васильева Наталья Сергеевна
Построение и комбинирование признаков в задаче поиска изображений по содержанию

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

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

25 февраля 2010
(четверг 17-20 каб. А.Н. Терехова)

Луцив Дмитрий Вадимович
Сопроцедуры в событийно-ориентированных архитектурах

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

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

18 февраля 2010
(четверг 17-20 каб. А.Н. Терехова)

Сабашный Вадим Евгеньевич
Методы аналитического сравнения бизнес-решений

Материалы к докладу:
Thomas H. Davenport, Jeanne G. Harris
Competing on Analytics: The New Science of Winning
2007 Harvard Business School Publishing Corporation
http://www.tomdavenport.com/books.html#coa

11 февраля 2010
(четверг 17-20 каб. А.Н. Терехова)

проф. Граничин Олег Николаевич
Рандомизация измерений и l_1-оптимизация

Материалы к докладу:
http://www.math.spbu.ru/user/gran/soi5/Granichin5.pdf