Основные научные результаты

Анализ производительности и планирование мощности узлов Internet

В 2001 г. эти исследования проводились в рамках фундаментальной НИР по заданию Министерства образования РФ "Исследование закономерностей поведения трафика соединений и разработка методов планирования мощности узлов Internet" (научный руководитель проф. В.Н. Васильев, ответственный исполнитель доц. Ю.А. Богоявленский, исполнители доц. О.Ю. Богоявленская, Д.Ж. Корзун).

При этом исследования были сконцентрированы на задаче разработки простых, эффективно решаемых и легко интерпретируемых моделей нагрузки внешнего канала узла. В качестве основного аппарата для такого моделирования выбраны линейные системы диофантовых уравнений с неотрицательными решениями (системы НЛДУ).

Целью работы в 2001 г. являлась разработка моделей для характеризации нагрузки внешнего канала (ВК) регионального телекоммуникационного узла (РТУ) на уровне потоков, структура которых определяется базисом Гильберта некоторой системы НЛДУ, разработка и обоснование алгоритмов их решения, использующих методы грамматического разбора для решения соответствующих систем НЛДУ, и аппробация полученных результатов, что в целом имеет существенное значение для теории анализа вычислительных сетей, теории формальных языков и теории НЛДУ.

В 2001 г. были получены следующие результаты:

Выполнен системный анализ существующих методов характеризации нагрузки современных устройств передачи сетевого трафика.
Предложено понятие равновесия грамматики, на основании чего разработан метод построения АНЛДУ по произвольной КС-грамматике и двум цепочкам над ее алфавитом. Выделены основные классы систем АНЛДУ (стандарные, канонические, ε-АНЛДУ, однородные и др.). Доказано, что любая система АНЛДУ может быть приведена к каноническому виду. Для произвольной системы НЛДУ доказано существование, в общем случае не единственным образом, КС-грамматики и цепочек, порождающих эту систему. Получена теорема об общем решении произвольной системы АНЛДУ, которая сводит задачу ее решения к построению некоторых выводов в грамматике (обобщенный вывод).
Показано, что задача решения произвольной канонической системы АНЛДУ может быть сведена к решению системы ε-АНЛДУ и решению некоторых систем Фробениуса. Разработаны псевдополиномиальные алгоритмы для нахождения минимальных решений системы ε-АНЛДУ и однородной системы АНЛДУ, что полностью решает задачу нахождения базиса Гильберта системы ε-АНЛДУ. Соответствующий алгоритм имеет временную вычислительную сложность равную в наихудшем случае O(M²m²n(M+n)) = O(M³m⁴) и использует память как O(Mmn) = O(Mm²), где n - число уравнений, m - число неизвестных, M - число элементов в базисе Гильберта системы, n<=m. Предлагаются полиномиальные алгоритмы для нахождения некоторого решения системы ε-АНЛДУ и однородной системы АНЛДУ.
Выполнена реализация предложенных алгоритмов решения систем ε-АНЛДУ и однородных АНЛДУ. Проведена их экспериментальная оценка и тестирование, в результате чего получено, что a) временная вычислительная сложность в большинстве случаев может быть оценена как величина Θ(Mm²) б) предложенный алгоритм работает значительно эффективнее по времени, нежели некоторые из существующих общих алгоритмов решения произвольных систем НЛДУ (метод целочисленного линейного программирования и универсальный алгоритм Filgueiras и Tomas).
Предложен новый инвариант неоднородного сетевого трафика - линейные пропорции между объемами различных типов данных. Исследуются теоретические свойства этого инварианта и обосновывается его использование для характеризации нагрузки ВК и описания ее структуры. Даны различные содержательные интерпретации предложенного инварианта, что позволяет трактовать линейные пропорции как некие источники нагрузки ВК (композиционная структура нагрузки). На основе инварианта разработана структурная дискретная линейная модель нагрузки ВК, позволяющая идентифицировать устойчивые компоненты нагрузки и оценивать степень их активности. Предложен ряд алгоритмов для решения этой модели, сводящихся к а) аппроксимации обнаруженных линейных пропорций в трафике с помощью однородной системы АНЛДУ; б) нахождению базиса Гильберта этой системы с помощью предложенных алгоритмов грамматического разбора, при этом базисные элементы определяют компоненты нагрузки (структуру); в) вычисление активности обнаруженных компонент (динамическая часть нагрузки). На базе этой модели предлагается ряд важных показателей производительности ВК.
Реализованы алгоритмы решения предложенной структурной дискретной линейной модели нагрузки ВК, использующих систему TCPconan для получения данных. Выполнена экспериментальная оценка этой модели на данных внешнего трафика Федерального Петрозаводского узла RUNNet за период с 4 декабря 2000 г. по 29 апреля 2001 г. Было получено, что такие важные на практике и теоретически предполагаемые свойства модели, как а) устойчивость структуры нагрузки во времени, б) масштабируемость структуры, в) удовлетворительный уровень точности описания реальной нагрузки, г) компактность и д) эффективность решения, согласуются с результатами экспериментов.

Полученные результаты могут быть использованы для характеризации нагрузки различных систем передачи данных сетевого трафика, для анализа и прогнозирования их производительности, для анализа и решения некоторых систем НЛДУ, при разработке и реализации программного обеспечения обработки данных сетевого трафика на уровне потоков.

Результаты работы докладывались на научных семинарах рабочей группы по анализу производительности вычислительных сетей (Network Performance Analysis Group) кафедры информатики Хельсинкского университета, Хельсинки (Финляндия), на научном семинаре отдела телекоммуникаций Центра технических исследований Финляндии (VTT), Хельсинки (Финляндия), на Шестой Санкт-Петербургской Ассамблее молодых ученых и специалистов, Второй политехнический симпозиум - Молодые ученые промышленности Северо-Западного региона, Конференция "Компьютерные технологии, коммуникации, численные методы и математическое моделирование".

На последней конференции докладчик Д.Ж. Корзун был награжден грамотой за лучший доклад.

Учебно-научный центр дистанционного образования - УНЦ ДО ПетрГУ, Кольского филиала ПетрГУ и КолНЦ РАН

В 2001 году продолжалась работа по поддержке и развитию единой информационно-технологической инфраструктуры для совместной учебной и научной деятельности преподавательского состава ПетрГУ, Кольского филиала ПетрГУ и научных сотрудников Кольского НЦ РАН, созданной в рамках данного проекта в 1997 - 2000 годах (научный руководитель доц. Н.С. Рузанова, отвественный исполнитель доц. Г.С. Сиговцев, исполнители М.А. Чарута, П.Е. Гладышев, М.В. Дьяконов).

Основными задачами проекта являются:

поддержка и развитие новых форм обучения и сопровождения учебного процесса для повышения качества фундаментального образования и повышение квалификации на базе современных технологий в КНЦ РАН, ПетрГУ и КФ ПетрГУ
разработка инструментальных средств и учебных информационных ресурсов для дистанционного обучения
развитие единой информационной сети и информационного наполнения сайтов УНЦ ДО
предоставление дистанционных образовательных и информационных услуг преподавательскому составу и студентам ПетрГУ, КФ ПетрГУ, сотрудникам КНЦ РАН

Разработка учебных дистанционных курсов

В УНЦ ДО ПетрГУ созданы прототипы трех новых курсов.

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

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

Курс "Экономический управленческий анализ" включает набор лекций по теоретическому материалу курса, разбитому на семь глав. После прохождения каждой главы студент выполняет тест, результаты тестирования сохраняются для последующей обработки и просмотра преподавателем. Кроме того, пять глав имеют наборы контрольных задач, результаты решения которых отсылаются преподавателю по электронной почте или сохраняются в файле. Имеется набор модулей в виде CGI-скриптов на языке Perl для авторизации доступа, создания новых тестов, просмотра результатов тестирования по группе студентов и по отдельному студенту.

Программная система для автоматизации подготовки информационно емких образовательных ресурсов

Реализована система для автоматизации подготовки сложных образовательных Интернет-ресурсов большого объема. Название системы - "E-book". Программное обеспечение реализовано на языке VBA (Visual Basic for Applications) с привлечением программ, написанными на других Visual-языках. Для написания части системы, которая отвечает за генерацию web-страниц, курса выбран язык VBA для Word. Это обусловлено тем, что этот язык позволяет работать над существующими документами Microsoft Word, а также то, что Microsoft Word'97 содержит встроенный конвертер из Microsoft Word в HTML.

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

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

Система реализована в виде интегрированного пакета. В состав пакета входят: программа инсталляции (install.doc - реализована также на VBA для Microsoft Word'97), шаблон (e-book.dot - содержит в себе все необходимые для работы с системой программы), набор базовых шаблонов html-документов, некоторые элементы дизайна для базовых шаблонов.

После инсталляции в Microsoft Word появляется дополнительная панель инструментов "E-book", в которой находятся кнопки для запуска соответствующих подпрограмм. Система позволяет полностью автоматизировать процесс "разумной конвертации" исходных текстов учебной литературы, подготовленной в текстовом процессоре Microsoft Word, а также позволяет облегчить процесс создания html-страниц с тестовыми заданиями для самопроверки знаний обучаемого.

Основное отличие модуля генерации веб-страниц от встроенного в Microsoft Word'97 заключается в том, что, из линейного word-документа создается структурированный набор страниц, с соответствующими переходами между ними, в отличие от существующего встроенного, который конвертирует word-документы по принципу "один к одному".

Оптимизация бизнес-плана сельскохозяйственного предприятия

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

Моделирование для базового предприятия с последующим анализом результатов показало, что упущенная прибыль предприятия в 2000 г. составила более 35%, а его потенциал по прибыли имеет значение более чем на 80% выше достигнутой.

Разработка дистанционного курса "Программирование на языке Турбо Паскаль"

Разработан дистанционный курс, который предаставлен в Web пространстве по адресу: http://www.karelia.ru/psu/Chairs/IMO/pascal

Курс содержит развернутое изложение основных тем по углубленному курсу программирования, включая работу со структурами данных и объектными средствами. Предусмотрены также средства самоконтороля студентов для проверки степени усвоения материала.