Санкт-Петербург 2004 Технология автоматизации тестирования алгоритмов решения неотрицательных линейных диофантовых уравнений Кулаков К.А. kulakov@cs.karelia.ru. - презентация

1 Санкт-Петербург 2004 Технология автоматизации тестирования алгоритмов решения неотрицательных линейных диофантовых уравнений Кулаков К.А. магистрант 1 года обучения, кафедра Информатики и математического обеспечения, Петрозаводский государственный университет Научный руководитель: Д.Ж. Корзун, к.ф. м.н., старший преподаватель

2 Санкт-Петербург 2004 Введение НЛДУ система неотрицательных линейных диофантовых уравнений АНЛДУ ассоциированная с КС-грамматиками система НЛДУ Л-ра: Корзун Д. Ж. Синтаксические алгоритмы решения неотрицательных линейных диофантовых уравнений и их приложение к моделированию структуры нагрузки канала Интернет. Дисс. на соиск. канд. физ.-мат. наук. Петрозаводск. ПетрГУ, с. Защита в СПбГУ. Первый оппонент – профессор И. Л. Братчиков

3 Санкт-Петербург 2004 Введение Общий вид системы: Система АНЛДУ

4 Санкт-Петербург 2004 Пример системы АНЛДУ Система АНЛДУ: Базис Гильберта :

5 Санкт-Петербург 2004 Область применения Разработка технологии автоматизации тестирования алгоритмов решения неотрицательных линейных диофантовых уравнений

6 Санкт-Петербург 2004 Поставленные задачи 1) Разработка алгоритмов генерации систем АНЛДУ и соответствующих им базисов Гильберта. 2) Разработка программного обеспечения для выполнения комплексного тестирования и сравнительного анализа. 3) Выполнение тестирования и сравнительного анализа алгоритмов решения систем НЛДУ. 4) Обработка статистической информации для получения результатов сравнительного анализа.

7 Санкт-Петербург 2004 Концепция проекта Теоретическое обоснование алгоритмов генерации систем АНЛДУ: генерация = система АНЛДУ + базис Гильберта Разработка алгоритмов генерации систем АНЛДУ и соответствующих базисов Гильберта

8 Санкт-Петербург 2004 Концепция проекта Разработка программного средства, автоматизирующего процесс генерации и тестирования Оценка потребляемых ресурсов программными реализациями алгоритмов решений

9 Санкт-Петербург 2004 Теорема о приведении систем АНЛДУ к более простому виду Теорема: Пусть задана произвольная система АНЛДУ: Задача нахождения базиса Гильберта сводится к задаче нахождения базиса Гильберта либо уравнения вида либо системы вида

10 Санкт-Петербург 2004 Алгоритмы генерации Алгоритм генерации на основе преобразования Жордано (МЖ) является самым простым из алгоритмов. Он выделяет в матрице коэффициентов системы АНЛДУ единичную подматрицу. Алгоритм генерации на основе преобразования Гаусса (МГ) является аналогом преобразования Гаусса однородной системы уравнений.

11 Санкт-Петербург 2004 Алгоритмы генерации Расширенный метод Гаусса является расширенным аналогом преобразования Гаусса. Любая система АНЛДУ, сгенерированная с помощью МГ входит в класс генерации данного алгоритма. Алгоритм генерации полного класса систем АНЛДУ позволяет создать произвольную систему АНЛДУ.

12 Санкт-Петербург 2004 Алгоритмы генерации

13 Санкт-Петербург 2004 Особенности реализации проекта Разработка алгоритмов генерации систем АНЛДУ Модульная структура ПО Переносимость Независимость от формата исследуемого алгоритма решения систем АНЛДУ (исполняемые файлы)

14 Санкт-Петербург 2004 Особенности реализации проекта Сбор и обработка статистической информации о ходе процесса решения Обработка критических ситуаций Эти задачи решены методами системного программирования

15 Санкт-Петербург 2004 Схема работы ПО

16 Санкт-Петербург 2004 Полученные теоретические результаты Теорема о приведении произвольной системы АНЛДУ к более простому виду Разработка и теоретическое обоснование алгоритмов генерации тестовых примеров

17 Санкт-Петербург 2004 Полученные практические результаты Программная реализация алгоритмов генерации Программное обеспечение для выполнения тестирования Экспериментальный и сравнительный анализ алгоритмов решения Два реализованных алгоритма генерации систем АНЛДУ и ПО расчета затрачиваемых ресурсов используются в программной системе Web-SynDic

18 Санкт-Петербург 2004 Алгоритмы решения систем АНЛДУ Синтаксический алгоритм решения систем АНЛДУ, предложенный Д.Ж. Корзуном. Л-ра: Корзун Д. Ж. Синтаксические алгоритмы решения неотрицательных линейных диофантовых уравнений и их приложение к моделированию структуры нагрузки канала Интернет. Дисс. на соиск. канд. физ.-мат. наук. Петрозаводск, ПетрГУ, с. Алгоритм нахождения базиса Гильберта систем НЛДУ, предложенный португальскими математиками M. Filgueiras, A.-P. Tomas. Л-ра: M. Filgueiras, A.-P. Tomas. Package Slopes.

19 Санкт-Петербург 2004 Генерация систем АНЛДУ

20 Санкт-Петербург 2004 Генерация и решение систем АНЛДУ

21 Санкт-Петербург 2004 Решение систем АНЛДУ

22 Санкт-Петербург 2004 Экспериментальная часть anlde slopessys Распределение времени решения по числу векторов базиса Гильберта Тестирование: более 1.5 миллиона тестовых систем Сравнительный анализ решателей: 9500 тестовых систем

23 Санкт-Петербург 2004 Перечень используемых для реализации продуктов Microsoft Портирование программного обеспечения под ОС семейства Windows Программная система портирована под ОС Windows 2000 NT Professional с помощью ПО Cygwin за 30 человеко-часов Система может быть легко портирована под технологию Microsoft.NET так как реализована на C++.

24 Санкт-Петербург 2004 Заключение Теоретически обоснованы, разработаны и реализованы алгоритмы генерации систем АНЛДУ Разработано и реализовано ПО для выполнения тестирования Выполнено тестирование и экспериментальный анализ Разработана и реализована обработка статистической информации Результаты подробно представлены в бакалаврской работе и в проектной документации. Программная система может быть продемонстрирована.