Название работы	Кол-во страниц	Размер
Лекция №1. «Общее понятие об управлении рисками» Понятие риска и...	1	86kb.
Справочник по танцам. 2 Редактирование справочника фигу	1	73.03kb.
Семинару по теме Закон РФ об эцп назовите	1	40.6kb.
В части I «Начальное общее образование. Основное общее образование»...	1	46.42kb.
Кафедра геологии нефти и газа вопросы государственного экзамена для...	1	79.4kb.
Об электронной цифровой подписи	1	170.67kb.
Закон РФ от 10. 01. 2002 №1-фз "об электронной цифровой подписи"	1	187.08kb.
Всемирная организация интеллектуальной собственности	6	2243.63kb.
Алгоритм преобразования выражений с квадратным корнем (радикалом)	1	21.5kb.
Страница 9 методичек: тема	1	156.8kb.
Иоганн генрих песталоцци	1	16.8kb.
Расширение функциональных возможностей инвертора напряжения систем...	1	134.94kb.
Викторина для любознательных: «Занимательная биология»	1	9.92kb.

Вариант от 9 октября 2002.

Темы для студенческих работ

1. 
   Преобразования уровней абстракции программ
   
   1. 
      Теория
      
      1. 
         Предложить общую концепция преобразования уровня абстракции для алгоритмов (например, на основе универсальной модели ASM¹, см. Работы Boerger’а и др. на тему «ASM и Refinement», см. также общее понятие медиаторного преобразования в документе ИББ).
         Концепция должна узаконивать сложившуюся практику оформления преобразований уровней в виде медиаторов и допускать медиаторы общего вида.
         
      2. 
         Формализовать предусловия и результаты тестирование на соответствие модели при использовании преобразования уровня абстракции.
         Что мы тестируем на нижнем уровне, обходя верхний автомат?
         Эта проблема может рассматриваться как в общем случае, так и для разных классов преобразований уровня абстракции по отдельности.
         
   2. 
      Практика
      
      1. 
         Разработка алгоритма синхронизации состояния модельных объектов в многоуровневой тестовой системе.
         Практически важные примеры у нас уже есть.
         
         1. 
            Предложить общий алгоритм синхронизации данных в многоуровневой тестовой системе, построенной из объектов.
            Обратить внимание на
            
            1. 
               Недопустимость проверок модельных данных объекта, пока его состояние не синхронизированно с нижним уровнем, и использования модельных ссылок, ведущих «против» реализационных.
               
            2. 
               Процедуру синхронизации статических данных. Похоже, что состояние класса должно синхронизовываться не позже состояния любого объекта этого класса.
               
            3. 
               Возможность динамического создания медиаторов, и, значит, динамического корректного включения их в систему синхронизации состояний.
               
      2. 
         Предложить механизм реализации в виде правил трансляции J@va  Java.
         
   3. 
      Правила обращения с кластерами уточнения
      
      1. 
         Предложить алгоритм синхронизации данных в многоуровневой тестовой системе, построенной из объектов, с учетом отдельно проводимых синхронизаций в кластерах модельных объектов.
         
      2. 
         Предложить структуру тестового набора, учитывающую наличие спецификаций с уточнением, требующим модификации объектов-параметров.
         
      3. 
         Создать пример такого тестового набора.
         
      4. 
         Предложить механизм реализации в виде правил трансляции J@va  Java.
         
2. 
   Тестирование объектов с закрытым состоянием и функциональных систем
   
   1. 
      Теория
      
      1. 
         Предложить метод тестирования компонентов со скрытым состоянием на основе какого-либо способа обхода автоматной модели.
         
      2. 
         Определить теоретические количественные ограничения на число вызовов целевых операций и общее число операций, необходимое для тестирования по такому методу.
         
   2. 
      Практика
      
      1. 
         Предложить механизм тестирования компонента, имеющего методы с параметрами-объектами (входными и выходными), состояние которых, влияющее на поведение данного компонента, никак нельзя определить, кроме как по самому поведению.
         
      2. 
         Предложить механизм тестирования компонента, имеющего методы с функциональными параметрами (указатели на функции, делегаты, спец. интерфейсы и пр.) (входными и выходными), и накладывающего ограничения аксиоматического вида на эти параметры.
         
3. 
   Повторное использование ранее определённых покрытий
   
   1. 
      Предложить правила создания спецификаций и схему тестового набора, в которой можно было бы повторно использовать покрытия, определённые в базовой или абстрактной спецификации, в наследнике или уточняющей спецификации, соответственно.
      Нужно уметь использовать покрытия из уточняемых/наследуемых спецификаций и расширять их, надо уметь динамически отслеживать такое расширенное покрытие в ходе теста и, предпочтительно, фильтровать тестовые данные по нему.
      Схема тестового набора предпочтительна компонентная, т.е., только один компонент соответствует одному определённому покрытию. При использовании этого покрытия в других местах должен использоваться этот компонент.
      
   2. 
      Предложить правила создания медиаторов и схему тестового набора, в которой можно было бы использовать покрытия, определённые в медиаторах для тестирования по ним.
      Хорошо бы при этом уметь в медиаторах расширть определённые в спецификациях покрытия.
      Схема тестового набора предпочтительна компонентная, т.е., только один компонент соответствует одному определённому покрытию, при использовании его в других местах должен использоваться этот компонент.
      
4. 
   Библиотеки абстрактных спецификаций и тестов для них
   
   1. 
      Ввод/вывод
      
      1. 
         Разработать методику тестирования библиотечных компонентов ввода/вывода.
         
      2. 
         Разработать стандартный пакет спецификаций и тестов.
         
   2. 
      Образцы проектирования (patterns) и анализа.
      
      1. 
         Разработать возможные образцы тестирования систем, сконструированных при помощи общеизвестных образцов проектирования.
         
   3. 
      Библиотеки итераторов
      
5. 
   Реализовать на основе технологии ATP инструмент и библиотечку для сбора покрытия кода по нескольким метрикам.
   
6. 
   Статический анализ кода
   
   1. 
      Сделать обзор известных видов дефектов, обнаруживаемых при статическом анализе кода.
      В обзор надо включить способы обнаружения и, возможно, анализ области их применимости.
      
   2. 
      Определить виды дефектов, легко обнаруживаемых при использовании технологии ATP.
      
   3. 
      Определить направления расширения технологии ATP для возможности обнаружения новых видов дефектов при статическом анализе.
      
7. 
   Генерация кода по неявным спецификациям
   
   1. 
      Предложить схему такой генерации, учитывающую разные возможности
      
      1. 
         Явные части спецификаций использовать, насколько это возможно
         
      2. 
         Выделять такие спецификации, которые легко разрешаются относительно результатов (несколько эвристических приёмов)
         
      3. 
         Использовать механизмы декомпозиции, генерации и обратной композиции, если возможно
         
      4. 
         Использовать библиотеку готовых компонент с известными спецификациями
         
8. 
   Генерация документации по спецификациям
   
   1. 
      Предложить схему генерации документации из спецификаций на J@va, которая использовала бы формальный код для построения документации на естественном языке.
      Основная задача — выявить как можно более слабые ограничения, следуя которым можно получить легко переводимые в документацию спецификации.
      
9. 
   Генерация сценариев по аксиомам и алгебраическим спецификациям
   
   1. 
      Предложить схему такой генерации с возможностью для пользователя указывать нужный способ упрощения автомата (уменьшение числа состояний)
      Основная проблема — как использовать факторавтомат совместно с алгебраическими спецификациями. Скорее всего, требующееся преобразование не будет факторизацией.
      
   2. 
      Предложить схему такой генерации, основанную на выделении модели состояния на основе аксиом
      
   3. 
      Как минимизировать (в соответствии с некоторым покрытием) добавляемые в автомат (дополнительно к аксиомам и цепочкам в алгебраических спецификациях) переходы, с тем чтобы полученный автомат был обходим.
      
10. 
    Автоматическое построение факторавтоматов
    
    1. 
       Предложить схему автоматического построения факторизованного автомата на основе спецификаций и критерия покрытия.
       Основная задача здесь — выделить модель состояния из спецификаций и предикатов, определяющих покрытие. Надо определить ограничения, позволяющие делать это автоматически.
       
11. 
    Тестирование различного рода автоматов.
    
    1. 
       Слабо детерминированные автоматы.
       
       1. 
          Указать точную оценку сложности алгоритмов ИБ.
          
       2. 
          Указать точную оценку сложности алгоритма ВК.
          
       3. 
          Есть ли более быстрые избыточные алгоритмы обхода слабо детерминированных автоматов.
          
       4. 
          Есть ли неизбыточный алгоритм обхода слабо детерминированных автоматов, работающий в среднем быстрее, чем известные нам.
          
       5. 
          Построить неизбыточный алгоритм обхода слабо детерминированных автоматов со взвешенными переходами, строящий путь минимального веса.
          
    2. 
       Слабо/сильно недетерминированные автоматы.
       
       1. 
          Является ли класс свободно обходимых автоматов радикалом среди неизбыточных алгоритмических подклассов всех графов.
          Доказано для детерминированных и слабо детерминированных.
          
       2. 
          Каково устройство свободно обходимых слабо/сильно недетерминированных автоматов.
          По сути, нужно какое-либо их характеристическое свойство, требующее для своей проверки гораздо меньше времени, чем проверка существования обхода-Δ-продолжения любого Σ-обхода.
          
       3. 
          Построить оптимизированный неизбыточный алгоритм обхода свободно обходимых слабо/сильно недетерминированных автоматов.
          
       4. 
          Построить неизбыточный алгоритм обхода свободно обходимых слабо/сильно недетерминированных автоматов минимальной сложности в худшем случае.
          
       5. 
          Построить неизбыточный алгоритм обхода свободно обходимых слабо/сильно недетерминированных автоматов минимальной сложности в среднем случае.
          
       6. 
          Построить неизбыточный алгоритм обхода свободно обходимых взвешенных слабо/сильно недетерминированных автоматов, строящий Σ-маршрут минимального веса.
          
    3. 
       Автоматы с отложенными реакциями.
       
       1. 
          Пополнение спецификационных конструкций такими, которые облегчают спецификацию компонентов с отложенными реакциями.
          Пример системы с отложенными реакциями и её спецификаций.
          
       2. 
          Формализация метода стационарного тестирования.
          Определение и точные ограничения на автомат, допускающий стационарное тестирование.
          Построение адекватно устроенной тестовой системы.
          Демонстрация-пример работающей тестовой системы для стационарного тестирования.
          
       3. 
          Формализация серийного тестирования.
          Определение и точные ограничения на автомат, допускающий серийное тестирование. Можно ли с помощью серийного тестирования добиться более тонкого покрытия, чем при помощи стационарного.
          Понимание стационарного тестирования как преобразования уровней абстракции.
          Построение адекватно устроенной тестововй системы.
          Построение алгоритма работы механизма серийного тестирования.
          Демонстрация-пример работающей тестовой системы для стационарного тестирования.
          
       4. 
          Формализация общего нестационарного тестирования.
          Здесь все те же вопросы, с одним дополнением: можно ли вообще что-то оттестировать таким общим способом.
          
    4. 
       Покрытие путей в автоматах.
       
       1. 
          Общая постановка задачи покрытия множества путей в атомате.
          Формальная модель. Что тестируется в этом случае. Понимание такого тестирования как преобразования уровня абстракции.
          Каким образом можно в описывать покрытие, определяемое множеством путей — предложения по расширению языка.
          Архитектура тестовой системы подходящей для достижекния общего покрытия, определяемого множеством путей.
          Алгоритмы тестирования, достигающие заданного таким образом покрытия.
          Демонстрация-пример тестирования множества путей.
          
       2. 
          Построить неизбыточный алгоритм, проходящий все простые du-пути в атомате (переходы которого помечены символами d_x и u_x для некоторого набора переменных X={x_i}).
          То же, для минимальной сложности.
          То же, для взвешенных переходов — строить обход минимального веса.
          
    5. 
       Композиция и декомпозиция автоматов.
       
       1. 
          Под этим заголовком собраны все задачи, относящиеся к специфицированию и тестированию автомата как композиции автоматов — построение спецификаций и тестов для композиции автоматов по известным спецификациям и тестам для её элементов.
          Связи между элементами могут рассматриваться как статические и динамические.
          Построение подходящей тестовой системы.
          
       2. 
          Всевозможные задачи следующего рода: вдруг тестируемый автомат можно так декомпозировать, что тестировать его как композицию будет проще (пример: тестирование двухуровневого детерминированного сильно связного автомата).
          
12. 
    Теоретические основания нашего подхода к тестированию.
    
    1. 
       Абстрактная постановка задачи partition testing.
       Есть 2 алгоритма, представленных в любой известной универсальной форме (лучше, наверно ASM).
       Доказать, что существует такое конечное разбиение области определения (элемент области определения — «вход») первого, что, если результаты обоих алгоритмов на некотором входе из некоторого элемента этого разбиения совпадают (определить ...), то и на всех входах из этого элемента они совпадают, и наоборот, если на некотором входе их результаты различны, то и на любом входе из того же элемента этого разбиения они будут отличаться.
       
    2. 
       Определить разумные классы алгоритмов, для которых задача определения такого разбиения может быть решена автоматически.
       Ясно, что она в общем случае неразрешима, так как её разрешимость влечёт разрешимость задачи эквивалентности алгоритмов, что, в свою очередь, влечёт разрешимость задачи об остановке.
       
13. 
    Нагрузочное тестирование и тестирование быстродействия
    
    1. 
       Теория
       
       1. 
          Формализация задачи нагрузочного тестирования.
          
       2. 
          Формализация задачи тестирования быстродействия.
          
       3. 
          Методы нагрузочного тестирования.
          
    2. 
       Практика
       
       1. 
          Разработка методов, позволяющих определить вид зависимости показателей быстродействия нераспределенной системы от различных параметров.
          
       2. 
          Те же методы для распределенных систем.
          
14. 
    Тестирование систем различного вида
    
    1. 
       Тестирование GUI
       
       1. 
          Методика тестирования элементов графического интерфейса на основе модели.
          
       2. 
          Графический генератор спецификаций, аналогичный средствам конструирования GUI.
          
    2. 
       Тестирование компиляторов
       
       1. 
          Методика построения моделей для тестирования трансформаций (в частности, оптимизаторов).
          
    3. 
       Тестирование протоколов
       
       1. 
          Методика построения моделей по одному из общепринятых форматов описания протоколов.
          
       2. 
          Методы обнаружения ошибок в спецификациях протоколов.
          
    4. 
       Тестирование бизнес-приложений (клиенты+сервер приложений (правила бизнес-логики)+СУБД)
       
       1. 
          Определение наиболее подверженных ошибкам мест при разработке бизнес-приложений
          
       2. 
          Методика построения эффективных моделей для тестирования бизнес-приложений.
          

Список сокращений

ASM	Abstract State Machine	http://research.microsoft.com/fse/ and/or kuliamin@ispras.ru
ATP	Attributed Tree Processing	demakov@ispras.ru
ВК	Виктор Кулямин	kuliamin@ispras.ru
ИБ, ИББ	Игорь Борисович и/или Игорь Бурдонов, Игорь Борисович Бурдонов	igor@ispras.ru