Научно-исследовательская работа студентов: Материалы юбилейной 60-й научной студенческой конференции. Петрозаводск: Изд-во ПетрГУ, 2008. 325 с. Isbn 978-5-8021-0880-2
| Вид материала | Научно-исследовательская работа |
СодержаниеСекция «Прикладная математика» Экономизация квазиполиномов Секция «Информационные системы и технологии» Теоретические основы работы |
- Работа студентов материалы 58-й научной студенческой конференции, 3780.58kb.
- Программа 58-й научной студенческой конференции петрозаводск Издательство Петргу 2006, 841.28kb.
- Введение седьмая Межвузовская научная конференция продолжает обсуждение проблем межкультурного, 1199.81kb.
- Сборник статей ежегодной международной студенческой научно-практической конференции, 1058.05kb.
- «свое» и «чужое» в культуре народов европейского севера, 1556.91kb.
- В. М. Пивоев (отв ред.), А. М. Пашков, М. В. Пулькин, 3114.99kb.
- О хозяйства материалы студенческой научной конференции (18 февраля 3 марта 2008г.), 5864.74kb.
- Программа 61-й научной студенческой конференции (20-24 апреля) Петрозаводск, 854.03kb.
- Краткий курс высшей математики : учеб пособие для вузов / Б. П. Демидович, В. А. Кудрявцев., 1363.18kb.
- Актуальные социально-экономические и правовые аспекты устойчивого развития региона., 2089.17kb.
Секция «Прикладная математика»
АНАЛИЗ ЭФФЕКТИВНОСТИ
РАЗЛИЧНЫХ АЛГОРИТМОВ
НАХОЖДЕНИЯ МАКСИМАЛЬНОГО ПОТОКА
Караваев А.
Научный руководитель — канд. физ.-мат. наук Перепечко С. Н.
Теоретическая оценка сложности алгоритма часто не соответствует реальному поведению алгоритма на практике. Оценка сложности, выраженная символом «O-большое», не объясняет, как алгоритм поведет себя на конкретно взятом примере. Алгоритмы с «плохой» теоретической оценкой обычно на практике работают гораздо быстрее алгоритмов, теоретическая оценка которых намного лучше. Часто это обусловлено тем, что хорошая теоретическая оценка достигается применением нетривиальных структур данных, что сильно усложняет реализацию,
в то время как тривиальная реализация «медленных» алгоритмов делает их применение гораздо более выгодным для решения реально существующих задач. Проблема в том, что один алгоритм поиска максимального потока показывает очень хорошее время работы на одних сетях, тогда как другие алгоритмы на тех же сетях работают медленно. Взяв тесты другого вида, можно отыскать другой алгоритм, который будет работать на них быстрее остальных алгоритмов.
Таким образом, если можно было бы, используя некоторый набор характеристик сети, сказать, какой алгоритм для этой сети подходит лучше всего, то можно было бы создать так называемый «менеджер», который умеет анализировать сеть и определять, какой алгоритм для этой сети использовать, чтобы быстро получить решение. Такой менеджер должен быть обучен на некотором наборе сетей. На основе той информации, которая получается во время обучения, менеджер должен для каждой сети, подаваемой на вход, подбирать лучший для нее алгоритм. Цель работы в создании такого менеджера и выборе некоторого набора параметров для классификации сетей.
На начальном этапе был построен менеджер, содержащий 5 алгоритмов. Для обучения было выбрано 12 000 различных тестов. Тестирование менеджера на этих же тестах показало прирост производительности на 10,9 %. На эту величину менеджер справился с тестами быстрее, чем самый быстрый из отдельно взятых алгоритмов. При тестировании менеджера на 7 000 незнакомых тестах эксперимент потерпел неудачу: менеджер работал на 67 % хуже, чем самый быстрый для этих тестов алгоритм, но лучше, чем все остальные. Неудача объясняется тем, что менеджер не смог классифицировать 97 % незнакомых сетей, поскольку обучение было недостаточно содержательным. Успех тестирования менеджера на знакомых тестах показал, что такая идея способна давать улучшение производительности, надо лишь отыскать хороший способ обучения.
^ ЭКОНОМИЗАЦИЯ КВАЗИПОЛИНОМОВ
Воропаев А.
Научный руководитель — канд. физ.-мат. наук Перепечко С. Н.
Решения некоторых задач перечислительной комбинаторики являются квазиполиномами и предстают в громоздком виде. В этих случаях экономизация результата (его приведение к более компактному виду) может способствовать уменьшению вычислительных затрат и классификации семейства задач. Обзор работ и опыт использования специализированных компьютерных программ свидетельствуют о возможности экономизации квазиполиномов в частных случаях и вместе с тем о недостатке результатов в этой области. Вариантом экономизации квазиполинома является его представление в виде линейной комбинации заданных «компактных» квазиполиномов с наименьшим числом слагаемых.
Основой для этого может послужить выбор некоторой общей формы для представления исходного и «компактных» квазиполиномов. Удобный инструмент для задания «компактных» квазиполиномов и построения общей формы — функция целой части (floor). Полученные соотношения позволяют «вручную» экономизировать решения некоторых частных задач. Проблемой является построение автоматического инструмента экономизации квазиполиномов, например в виде менеджера. Другая проблема состоит в построении общей формы для квазиполиномов, которые имеют компоненты с различными периодами, без привлечения общего периода.
^
Секция «Информационные системы и технологии»
ПРИМЕНЕНИЕ ИНФОРМАЦИОННЫХ
ПРОТИВОБОРСТВ В ГРАЖДАНСКИХ СФЕРАХ
ДЕЯТЕЛЬНОСТИ
Виноградова А.
Научный руководитель — канд. тех. наук, доц. Поляков В. В.
В последние годы стремительно растет потребность в квалифицированных специалистах в области информационных систем. Российские студенты, обучающиеся специальностям данного направления, в основном получают знания технической направленности, тогда как, согласно международному стандарту, существенный акцент должен делаться на изучение аспектов, связанных с проблемами информационного наполнения сетевых ресурсов, включая возможности ведения информационных войн.
Проявления информационных войн можно найти повсеместно: предвыборная борьба, конкурентная борьба предприятий. Они актуальны даже для нашего университета, поскольку с течением времени становится все труднее привлекать перспективных и способных абитуриентов, приходится вести конкурентную борьбу с другими вузами. Несомненно, что знание методов информационной войны поможет
в решении этой проблемы.
Стремительное развитие теории информационных противоборств было спровоцировано появлением Интернета. Информационные воздействия в глобальной сети могут проводиться эффективно и разнообразно: на программно-аппаратном уровне в виде кибер-войн, на уровне человека в виде информационно-психологических воздействий.
В настоящее время во многих странах созданы специальные группы по изучению методов ведения информационных войн во всех проявлениях. Недавно и в Вооруженных силах РФ была создана специальная группа по изучению и применению методов информационной войны. При этом особое внимание российские специалисты уделяют вопросам защиты от информационно-психологических воздействий.
Для эффективного ведения информационной войны следует непрерывно отслеживать действия конкурента и наполнение его информационных ресурсов, в частности наполнение и качество Интернет-сайтов. Так, например, университету следует афишировать свои достижения и события, для чего целесообразно выделить ответственного за это на каждом факультете. Студентов следует обучать методам информационно-психологической защиты личности и методам анализа окружающей информации, для чего необходимо включить изучение проблем и методов обеспечения информационной безопасности, в том числе проблемы информационных войн, в программу подготовки студентов различных факультетов, адаптируя материал применительно к требованиям конкретной специальности.
^ ТЕОРЕТИЧЕСКИЕ ОСНОВЫ РАБОТЫ
ПОИСКОВЫХ СИСТЕМ
Гравова Е.
Научный руководитель — канд. тех. наук Жуков А. В.
Ни для кого не секрет, что в настоящие дни Интернет заменяет людям очень многое: телевизор, книги, газеты, словари, даже друзей. В случае возникновения каких-либо вопросов, касающихся описания исторической эпохи или определения термина, люди все чаще обращаются к своему сетевому помощнику — информационному поисковику. Разработка поисковых систем очень перспективна, поскольку основы их работы затрагивают также и столь актуальную область поиска плагиата.
Поисковая система (ПС) — это программное обеспечение, предоставляющее доступ к коллекции слабоструктурированной (это главное отличие поисковой системы от СУБД).
Основная задача поисковой системы — минимизировать время, затрачиваемое пользователем на поиск релевантной запросу информации.
Модели поиска делятся на три основных класса:
1. Теоретико-множественные модели.
2. Вероятностные модели.
3. Алгебраические модели (векторные).
Теоретико-множественные модели используют в качестве каркаса теорию множеств. Классический пример — булева модель. В рамках этой модели документы и запросы представляются в виде множеств термов. Применяются в библиографических системах. Основной недостаток — каждый документ является однозначно релевантным или нерелевантным запросу.
Вероятностные модели: в качестве оценки релевантности документа запросу пользователя используется вероятность того, что пользователь признает документ истинно релевантным. Модель очень хорошо формализована. Главный недостаток — требуются первоначальные предположения о начальных значениях вероятностей. Применяются для глобального поиска.
В рамках алгебраических (векторных) моделей документы и запросы описываются в виде векторов в многомерном пространстве. Каркасом для таких моделей выступают алгебраические методы. Применяются для поиска в Веб. Основной недостаток — не учитываются синонимы и значения слов в разных контекстах.
Особняком стоят структурные методы, они пока не имеют широкого распространения, но достаточно перспективны.
В рамках каждого из классов было предложено множество альтернативных моделей, специфика Веб обусловила не только необходимость модификации классических методов поиска, но и появление новых задач.