У вас вопросы?
У нас ответы:) SamZan.net

Тема- Поиск подстроки с помощью конечных автоматов Руководители- ст

Работа добавлена на сайт samzan.net: 2015-07-10

Поможем написать учебную работу

Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.

Предоплата всего

от 25%

Подписываем

договор

Выберите тип работы:

Скидка 25% при заказе до 28.4.2025

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ, МОЛОДЕЖИ И СПОРТА УКРАИНЫ

ГВУЗ “Донецкий национальный технический университет”

КП – 6.050103-13-114140.001 ПЗ   Кафедра программного обеспечения                                   интеллектуальных систем

Курсовой проект

по дисциплине: «Алгоритмы и структуры данных»

Тема: «Поиск подстроки с помощью конечных автоматов»

Руководители:

      __________ ст.пр. Ольшевский А.И.

    (дата, подпись)

      __________ ст.пр. Бычкова Е.В.

    (дата, подпись)

Разработал:

     ______ ст.гр. ПОС-12а Ольмезов К.И.

                   (дата, подпись)

Донецк – 2013

__________________________                                                                                                                                                                    

 ДОНЕЦКИЙ НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ                  

(назва вищого навчального закладу)

Кафедра Программного обеспечения интеллектуальных систем _______________________

Дисциплина Алгоритмы и структуры данных__________________________

Специальность Программная инженерия___________________________________

Курс ________2_________ Группа _____ПОС-12а_______ семестр _________1__________

З А Д А Н И Е

на курсовой проект (роботу) студента

  _______________ ___   _Ольмезова Константина Ивановича            _________

1. Тема проекта (работы) Поиск подстроки с помощью конечных автоматов___________                                                                         

____________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

2. Срок сдачи студентом законченного проекта (роботы)  12 декабря 2013 ода_______ ___

_______________________________________________________________________  _____

3. Выходные данные к проекту (роботы) Словарь предметной области., теория по_______

данному методу, программный код, реализующий метод поиска подстроки с помощью   _    конечного автомата_______________________   _______________________________ ____ _____________________________________________________________________________

_____________________________________________________________________________

_____________________________________________________________________________

4. Содержание расчетно-пояснительной записки (перечень вопросов, которые подлежат разработки) Описание метода и алгоритма, выполняющего этот метод, листинг_________ программы   _                                              _____  ________________ _____________     ____

______________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

5. Перечень графического материала (с точным указанием обязательных чертежей) Экранные формы__  ___________________________________________________________

_____________________________________________________________________________
_____________________________________________________________________________

_____________________________________________________________________________

_____________________________________________________________________________

6. Дата выдачи задания _____________________09.09.13_____________________________

РЕФЕРАТ

Пояснительная записка: 37 с., 7 рис., 2 источника, 4 прил.

        Объектом разработки является программа поиска подстроки в строке

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

ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ, ОО АНАЛИЗ, ОО ПРОЕКТИРОВАНИЕ, ОО ПРОГРАММИРОВАНИЕ, ДИАГРАММЫ, BOOCH, UML

КП – 6.050103-13-114140.001 ПЗ

Фамилия

Подпись

Дата

Разработал

Ольмезов К.И.

Поиск подстроки с помощью конечного автомата

Литера

Лист

Листов

Рук. проекта

А.И. Ольшевский

8

3

32

Е.В. Бычкова

ДонНТУ,

каф. ПОИС

Группа ПОС-12а

Н. контроль

А.И. Ольшевский

Е.В. Бычкова

Зав. каф.

А.И. Шевченко

СОДЕРЖАНИЕ

      Введение ..............................................................................................................6

      1. Постановка задачи ………….…………………………...…….…..................7

      1.1. Описание предметной области …………………………….....…......…….7

      1.2. Цели и задачи курсового проекта ...............................................................7
      1.3. Выбор средств................................................................................................7

      2. Выбор метода решения....................................................................................8

      2.1. Теоретические данные..................................................................................8

      2.2. Описание входных и выходных данных.....................................................8

      2.3. Обоснование выбора структур данных.......................................................8

      3. Метод решения…....………………………....……………………………….9

      3.1. Описание метода поиска подстроки с помощью конечного автомата.....9

      3.2. Алгоритм составления автомата по заданной подстроке..........................9

      3.3. Нахождение z-функции строки..................................................................11

      4. Исследование эффективности метода..........................................................13

      4.1. Описание исследования..............................................................................13

      4.2. Содержание тестов......................................................................................13

      4.3. Таблица сравнения быстродействия..........................................................14

      4.4. Анализ полученных результатов...............................................................14

      ВЫВОДЫ ...........................................................................................................16
      СПИСК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ……....…………..….…….17

      Приложение А – Техническое задание…………………....…….……...…….18

      Приложение В – Руководство пользователя…………….....…………….......22

      Приложение С – Экранные формы……………………….…....…...….…......23

      Приложение D – Листинг программы……………….…………....….…..…..26

Разработал

Фамилия

Подпись

Дата

КП – 6.050103-13-114140.001 ПЗ

Лист

Ст. гр. ПИ-12в

Ольмезов К.И.

4

ПЕРЕЧЕНЬ ОБОЗНАЧЕНИЙ, СИМВОЛОВ, ЕДИНИЦ,

СОКРАЩЕНИЙ И ТЕРМИНОВ

ПП    –   Программный продукт

ПО    –   Программное обеспечение

КА    –   Конечный автомат

Разработал

Фамилия

Подпись

Дата

КП – 6.050103-13-114140.001 ПЗ

Лист

Ст. гр. ПОС-12а

К.И. Ольмезов

5


ВВЕДЕНИЕ

Поиск информации – одно из основных использований компьютера. Одна из простейших задач поиска информации – поиск точно заданной подстроки в строке. Тем не менее, эта задача чрезвычайно важна – она применяется в текстовых редакторах, СУБД, поисковых машинах.

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

Объектом курсового проекта является поиск подстроки с помощью конечного автомата – этот метод полезен если требуется находить вхождение одной заранее заданной подстроки в достаточно большое множество строк.    

В  процессе разработки предстоит решить следующие задачи:

  •  Описать метод поиска подстроки с помощью конечного автомата
  •  Составить алгоритм и рассчитать его сложность
  •  Запрограммировать составленный алгоритм
  •  Спроектировать экранные формы
  •  Выполнить анализ метода поиска подстроки с помощью конечных автоматов


1 ПОСТАНОВКА ЗАДАЧИ

1.1.Описание предметной области

Строка – это массив символов, хранящийся в памяти компьютера. Алфавит строки – множество используемых символов – определяется произвольно в зависимости от задачи.

Пусть даны две строки и . Тогда строка является подстрокой в позиции если (нумерацию строк считаем с нуля,  -  длина строки S).

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

1.2. Цели и задачи курсового проекта

Задачи курсового проекта:

1. Составить алгоритм на основе метода поиска подстроки с помощью конечного автомата

2. Составить программу, реализующую алгоритм

Цели курсового проекта:

1. Реализовать программный продукт для поиска подстроки с помощью конечного автомата

1.3. Выбор средств

В качестве языка программирования будет использоваться C++, а в качестве среды разработки – C++ Builder 6. Этот выбор обусловлен тем, что C++ Builder 6 – интегрированная визуальная среда разработки и позволяет удобно разрабатывать оконные приложения.


2 ВЫБОР МЕТОДА РЕШЕНИЯ

2.1. Теоретические данные

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

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

2.2. Описание входных и выходных данных

Входные данные:

подстрока, строка

Выходные данные:

позиция вхождение подстроки в строку (нумерация символов с единицы, если подстрока не входит в строку – возвращается 0)

2.3. Обоснование структур данных

Будем представлять автомат в памяти компьютера как массив состояний автомата, каждое из которых определяется множеством переходов из него. Для удобства программирования при создании массива будем использовать контейнер стандартной библиотеки шаблонов vector.

Так как в большинстве случаев количество переходов из каждого состояния автомата невелико (1-2), нет смысла использовать для хранения переходов массив из 256 (по количеству символов) элементов в каждом состоянии.

Для хранении переходов будем использовать контейнер map<char,int>, ключами которого будут входные символы, а значение каждого элемента – номер состояния, в которое будет осуществлён переход по этому символу. Если при поступлении очередного символа значение для него в текущем состоянии не определено, то происходит переход в нулевое состояние.


3. МЕТОД РЕШЕНИЯ

3.1. Описание метод поиска подстроки с помощью конечного автомата

Конечным автоматом называется структура, определяемая упорядоченной пятёркой: , где

  •   — входной алфавит (конечное множество входных символов), из которого формируются входные цепочки, допускаемые конечным автоматом;
  •   — множество состояний;
  •   — начальное состояние ;
  •   — множество заключительных состояний ;
  •   — функция переходов, всюду определённое отображение , такое, что , т.е. значение функции переходов на упорядоченной паре (состояние, входной символ или пустая цепочка) есть множество всех состояний, в которые из данного состояния возможен переход по данному входному символу или пустой цепочке (λ). Для детерминированных автоматов . Соответственно, . При реализации рассматриваемого алгоритма применяются только детерминированные автоматы.

Cчитается, что конечный автомат распознаёт некоторый язык (в данном случае состоящий из одного слова) если при работе на словах этого языка переходит в конечное состояние, а при работе на других словах – нет.

Для каждой строки можно построить КА, распознающий её. После этого при прогоне по этому автомату любой строки можно проверить, содержит ли она заданную подстроку (узнав, было ли достигнуто конечное состояние).

Достигнув конечного состояния автомата, можно с уверенностью сказать, что на текущем символе оканчивается первое вхождение искомой подстроки в строку.

3.2. Алгоритм создания автомата по заданной подстроке

Для создания автомата будем использовать z-функцию строки (её нахождение будет описано далее).

Z-функция строки S – такой массив Z длины N, что Z(i) – длина наибольшего префикса строки S, с которым совпадает её подстрока, начинающаяся с i-того символа. Формально:
Z(0) всегда неопределённо (мы пример Z(0)=0).

Найдя Z-функцию построим автомат в несколько шагов:

  1.  Добавим переходы непосредственно по сиволам. То есть из каждого состояния  будет переход в  по символу
  2.  Добавим учёт многократного повторения префиксов – для этого используем вычисленную Z-функцию. Добавим переходы . При этом перезаписывать переходы не будем. То есть будем устанавливать переход из определённого состояния по определённому символу только если переход из этого символа по этому состоянию ещё не был установлен.

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

Как видно, такой КА, при известной Z-функции строится за линейное время.

Пример

Рассмотрим подстроку S=”ababceabaxd”. Построим для неё распознающий её автомат.

Составим автомат из переходов при прямом проходе по строке.

Рисунок 3.1.1 – первый шаг постройки автомата


Добавим рёбра для учёта повторения префиксов.

Рисунок 3.1.2 – добавление учёта префиксов в автомат

3.3. Алгоритм вычисления z-функции строки

Z-функцию строки можно вычислить за линейное время (пропорциональное длине строки).

Чтобы получить эффективный алгоритм, будем вычислять значения  по очереди — от  до , и при этом постараемся при вычислении очередного значения  максимально использовать уже вычисленные значения. Для корректной работы алгоритма назначим z[0]=0.

Назовём для краткости подстроку, совпадающую с префиксом строки , отрезком совпадения. Например, значение искомой Z-функции  — это длиннейший отрезок совпадения, начинающийся в позиции  (и заканчиваться он будет в позиции ).

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

Тогда если текущий индекс, для которого мы хотим посчитать очередное значение Z-функции, — это , мы имеем один из двух вариантов:

  •   — т.е. текущая позиция лежит за пределами того, что мы уже успели обработать. Тогда будем искать  тривиальным алгоритмом, т.е. просто пробуя значения , , и т.д. Заметим, что в итоге, если окажется , то мы будем обязаны обновить координаты самого правого отрезка  — т.к.  гарантированно окажется больше .
  •   — т.е. текущая позиция лежит внутри отрезка совпадения . Тогда мы можем использовать уже подсчитанные предыдущие значения Z-функции, чтобы проинициализировать значение  не нулём, а каким-то возможно бо'льшим числом.

Для этого заметим, что подстроки  и  совпадают. Это означает, что в качестве начального приближения для  можно взять соответствующее ему значение из отрезка , а именно, значение .

Однако значение  могло оказаться слишком большим: таким, что при применении его к позиции  оно "вылезет" за пределы границы . Этого допустить нельзя, т.к. про символы правее  мы ничего не знаем, и они могут отличаться от требуемых.

Приведём пример такой ситуации, на примере строки aaaabaa

Когда мы дойдём до последней позиции (), текущим самым правым отрезком будет . Позиции  с учётом этого отрезка будет соответствовать позиция , ответ в которой равен . Очевидно, что таким значением инициализировать  нельзя, оно совершенно некорректно. Максимум, каким значением мы могли проинициализировать — это , поскольку это наибольшее значение, которое не выходит за пределы отрезка .

Таким образом, в качестве начального приближения для  безопасно брать только выражение

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


4 ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ МЕТОДА

4.1. Описание исследования

Проведём сравнительный анализ быстродействия, сравнив скорость работы метода конечного автомата со скоростью работы стандартной функции языка C и линейного поиска.

Запустим реализацию каждого из трёх методов поиска в цикле 1000000 итераций (для того, чтобы повысить время работы и сделать возможным его измерение).

Замерять время будем с помощью специальной функции clock() из библиотеки time.h, которая возвращает текущее количество миллисекунд, прошедших с 1 января 1970 года. Для получения времени работы методов узнаем значение времени до и после цикла и вычтем первое из второго.

4.2. Содержание тестов

Будем проводить исследование на различных входных данных:

  •  строка, где не присутствует ни одного символа искомой подстроки
  •  строка, в которую не входит вся подстрока, но входят отдельные её подстроки.
  •  строка где присутствует несколько идущих друг за другом префиксов подстроки
  •  для подстроки a++b++a++c, где a,b,c – строки, ++ - конкатенация: строка, в которую входит фрагмент типа a++b++a++b++…++a++b++a++c
  •  подстроки с присутствием большого количества переходов на отдельных состояниях автомата (например, "0102", "01020103", "01020103010201040102010301020105" – см. переход из предпоследнего состояния)
  •  такая строка, что искомая подстрока является её префиксом
  •  для подстроки вида "0001" строка вида "0010010010010010010010001001001001001001001001001001" – несколько наборов с различным количеством нулей в подстроке (худший случай для линейного поиска)


4.3. Таблица сравнения быстродействия

Таблица 4.3.1 – сравнительные данные времени работы различных алгоритмов поиска

Данные

Время (мс, 1000000 запусков)

Строка

Подстрока

Стандартный поиск

Линейный поиск

Поиск через автомат

abcdef

OPQRSTUVWXYZ

46

79

1687

12345

000000000000000

62

109

2094

012345

78901987894932190123979879230138

219

312

5657

mystring

abcmysmymymmaystrmystringmysssam

94

266

3640

aabab

aeracbwqabaabaabadabaabaababaabq

328

391

7359

0120145

00120012010120120120120145201204

375

406

8875

0102010302

010200101020110102010301020102010302

594

719

14437

0102010302

02010103001010201030201

266

312

9453

abcdaef

abcdaefarqvzv

63

47

2515

01

010203

31

16

656

001

0101010101010101010101010100101010101

204

312

6359

0000000001

0000000010000000010000000001000000001

875

735

8031

4.4. Анализ полученных результатов

Как видно из приведённых выше результатов тестов, метод поиска подстроки с помощью конечного автомата является неэффективным и по неизвестным причинам, вопреки теоретическим ожиданиям, работает в большинстве случаев более чем в 10 раз медленнее линейного поиска.

Следовательно, несмотря на теоретическую изящность и асимптотическую оптимальность, метод не может быть применён на практике.

В качестве предположительных причин подобной ситуации можно назвать:

  •  необходимость поиска элемента в бинарном дереве контейнера map при каждом изменении состояния требует  сравнений, где  - количество переходов из данного состояния (экспериментально было проверено, что даже при хранении автомата как статического массива результат улучшается довольно незначительно)
  •  так как хранение автомата происходит с помощью массива (вектора), то определённое время занимает обращение к определённой ячейке массива (которое является, по сути, сложением адреса массива и индекса ячейки)
  •  лишнее время может занимать также проверка на равенство номера текущего состояния автомата с номером конечного состояния, которое происходит при каждой итерации цикла, рассматривающего все символы (хотя её можно сопоставить проверке на равенство двух символов строки и подстроки в линейном поиске)


ВЫВОДЫ

         При выполнении курсового проекта для достижения поставленной цели был проведен анализ алгоритмов, в результате которого была выявлена сложность и детали реализации алгоритмов.

         Результатом анализа алгоритмов стал программный продукт, реализующий поиск подстроки в множество строк с помощью конечного автомата.


СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. Н. Вирт, Алгоритмы и структуры данных

2. Д. Кнут, Искусство программирования


Приложение А

Техническое задание

А.1 Общие сведения

Полное наименование создаваемого программного продукта: «Поиск подстроки с помощью конечного автомата».  

Программный продукт  проектируется студентом  группы ПОС-12а Ольмезовым Константином Ивановичем.

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

Плановый срок начала работы по созданию программного продукта: 09 сентября 2013 года и срок окончания: 12 декабря 2013 года.

А.2 Назначение и цели создания программы

Программа предназначена для автоматизации процесса построения функции «поиск подстроки в строке с помощью конечного автомата» и работы с ней.

Основной целью проекта является программная реализация алгоритма построения функции «поиск подстроки в строке с помощью конечного автомата».

А.3 Характеристика объекта автоматизации

А.3.1 Сведения об объекте автоматизации

Объектом автоматизации является процесс организации поиска подстроки в строке с помощью конечных автоматов.

А.3.2 Сведения об условиях эксплуатации программного продукта

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

А.4 Требования к программному продукту

А.4.1 Требования к ПП в целом

В целом к программному продукту предъявляются следующие требования:

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

А.4.2 Требования к задачам и функциям, выполняемым программой

Система должна обеспечивать решение таких задач:

  •  выбрать оптимальный способ хранения «конечного автомата» в оперативной памяти компьютера;
  •  реализация алгоритма построения автомата по подстроке;
  •  реализация нахождения z-функции строки для последующего построения автомата на её основы;
  •  реализация алгоритма поиска подстроки по заданному автомату;
  •  реализация алгоритма построения автомата;
  •  реализация поиска подстроки по заданному автомату.

А.4.3 Требования к видам обеспечения

А.4.3.1 Требования к техническому обеспечению

Для нормального функционирования проектируемого продукта:

  •  достаточно IBM совместимого ПК с процессором не менее 500 мГц;
  •  необходимо наличие  ОС Windows XP или 7;

А.4.3.2 Требования к информационному обеспечению

Информационная модель должна включать в себя организацию структуры данных для хранения данной структуры данных в памяти (в оперативной памяти и в файле);

А.4.3.3 Требования к программному обеспечению

Программный продукт создается для операционной системы Windows XP, Windows 7, Windows 8/8.1. Разработка проекта предусматривается на языке C++.

А.4.3.4 Требования к организационному обеспечению

В программную документацию должны входить:

  1.  пояснительная записка;
  2.  приложения:

а) техническое задание;

б) листинги основных блоков программы;

в) руководство пользователя;

г) экранные формы.

Таблица А.1 - Стадии и этапы разработки программного продукта

                            Этапы работы                                                                              

Срок выполнения

1 Постановка задачи (определений требований к ПП, формулировка постановки задачи: исходные данные, ограничения,  результаты, связь).

1-2 недели

2 Составление технического задания.

2-я неделя

3 Сбор и изучение информации по  заданному алгоритму.

3-я неделя

4 Техническое проектирование (разработка методов решения задачи и модульный анализ: определение структуры программы, выделение модулей, организация или взаимосвязи).

4-5 недели

5 Рабочее программирование: определение структур входных и выходных данных, алгоритмов работы модулей, оценки структур данных и алгоритмов, описание входных и выходных данных.

6-я неделя

6 Разработка самого алгоритма функционирования программы, составление спецификаций модулей.

7 неделя

7 Написание программы:

  •  отладка программы на верхнем уровне
  •  комплексная отладка и тестирование
  •  написание пояснительной записки.

8-10 недели

11-12 недели

12-13 недели

11-14 недели

8 Защита курсового проекта.

14-16 недели


Приложение Б

РУКОВОДСТВО ПОЛЬЗОВАТЕЛЯ

Основное меню состоит из нескольких пунктов:

  •  Ввод подстроки – позволяет ввести подстроку, которую впоследствии необходимо будет искать, или ввести имя файла, из которого будет прочитана подстрока
  •  Ввод строки – позволяет ввести строку, в которой будет производится поиск подстроки, или ввести имя файла, из которого будет прочитана строка
  •  Исследовать алгоритм – позволяет запустить и измерить время 1000000 прогонов работы трёх алгоритмов поиска – стандартной функции strstr из библиотеки stdio.h, линейного поиска и поиска с помощью конечного автомата
  •  Наглядный поиск – позволяет произвести наглядный поиск введённой подстроки во введённой строке с отображением текущего состояния автомата и последовательных переходов по всем символам
  •  Показать автомат – отображает автомат, построенный по введённой подстроке
  •  О методе конечного автомата – справочная информация о методе поиска подстроки с помощью автомата
  •  О программе – информация о программе
  •  Выход – выход из программы, закрытие окна


Приложение В

ЭКРАННЫЕ ФОРМЫ

Рисунок B.1 – вид главного меню программы

Рисунок B.2 – панель ввода подстроки

Рисунок B.3 – панель исследования алгоритма

Рисунок B.4 – наглядный поиск подстроки с отображением автомата

Рисунок B.5 – отображение автомата программой
Приложение Г

ЛИСТИНГ ПРОГРАММЫ

Г1. Файл AutomatFunctions.h

typedef map<char,int> automat_state;

typedef vector<automat_state> automat;

//Поиск z-функции строки

vector<int> get_z_function(char *t,int N)

{

   vector<int> z(N,0);

   int l=0,r=0;

   for (int i=1;i<N;i++)

   {

       if (i<r)

           z[i]=min(z[i-l],r-i+1);

       while (i+z[i]<N && t[z[i]]==t[i+z[i]])

           z[i]++;

       if (i+z[i]>r)

       {

           l=i;

           r=i+z[i]-1;

       }

   }

   return z;

}

void build_automat(char *substr,automat &machine)

{

   int i,j;

   int len=strlen(substr);

   automat_state::iterator search;

   vector<int> z=get_z_function(substr,len);

   //machine - автомат

   //Автомат хранится как вектор множеств

   //Каждый элемент вектора - состояние автомата

   //Множество каждого вектора хранит в себе пары -

   //символ и номер состояния, в которое ведёт

   //переход по этому символу

   machine.assign(len+1,automat_state());

   //Добавляем самые очевидные переходы -

   //от символа к следующему по всей строк

   machine[0][substr[0]]=1;

   for (i=1;i<len;i++)

       machine[i][substr[i]]=i+1;

   //Зацикливание на первом символе

   if (substr[0]!=substr[1])//Только если первые два символа не повторяются

       machine[1][substr[0]]=1;

   for (i=1;i<len;i++)

   {

       for (j=0;j<=z[i];j++)//Переходим по всем символам совпадающего префикса

       {

           if (!machine[i+j].count(substr[j]))

               machine[i+j][substr[j]]=j+1;

       }

   }

}

int automat_search_substring(char *str,automat &machine,char *substr)

{

   int i;

   int len=machine.size()-1;

   int now_state=0;

   char *now=str;

   char c;

   while (*now)

   {

               if (machine[now_state].count(*now))

                       now_state=machine[now_state][*now];

               else

                       now_state=0;

       //now_state=machine[now_state][*now];

       if (now_state==len)

           return now-len-str+1;

       ++now;

   }

   return 0;

}

Г2. Файл Unit1.h

//---------------------------------------------------------------------------

#ifndef Unit1H

#define Unit1H

//---------------------------------------------------------------------------

#include <Classes.hpp>

#include <Controls.hpp>

#include <StdCtrls.hpp>

#include <Forms.hpp>

#include <ExtCtrls.hpp>

//---------------------------------------------------------------------------

class TForm1 : public TForm

{

__published:    // IDE-managed Components

       TPanel *InputSubstringPanel;

       TEdit *KeyboardInputSubstringText;

       TButton *KeyboarInputSubstringButton;

       TEdit *FileInputSubstringText;

       TButton *FileInputSubstringButton;

       TLabel *Label1;

       TLabel *InputSubstringError;

       TPanel *InputStringPanel;

       TLabel *Label2;

       TLabel *InputStringError;

       TEdit *KeyboardInputStringText;

       TButton *KeyboardInputStringButton;

       TEdit *FileInputStringText;

       TButton *FileInputStringButton;

       TPanel *MainMenuPanel;

       TLabel *Label3;

       TButton *MainMenuInputSubstringButton;

       TButton *MainMenuInputStringButton;

       TButton *MainMenuStudyAlgorithmButton;

       TButton *MainMenuVisualSearchButton;

       TButton *MainMenuShowAutomat;

       TButton *MainMenuByMethodButton;

       TButton *MainMenuByProgramButton;

       TButton *MainMenuExitButton;

       TButton *InputStringCancelButton;

       TButton *InputSubstringCancelButton;

       TPanel *ShowAutomatPanel;

       TPaintBox *ShowAutomatPaintBox;

       TButton *ShowAutomatCancelButton;

       TPanel *StudyAlgorithmPanel;

       TLabel *StudySubstringLabel;

       TLabel *StudyStringLabel;

       TButton *StudyButton;

       TLabel *StudyInfoLabel;

       TPanel *VisualSearchPanel;

       TPaintBox *VisualSearchAutomatPaintBox;

       TButton *VisualSearchCancelButton;

       TButton *VisualSearchGoButton;

       TPaintBox *VisualSearchStringPaintBox;

       TButton *StudyAlgorithmCancelButton;

       TPanel *MethodInfoPanel;

       TLabel *MethodInfoLabel;

       TButton *MethodInfoCancelButton;

       TButton *MethodInfoNextPageButton;

       TButton *MethodInfoPrevPageButton;

       TPanel *ProgramInfoPanel;

       TLabel *ProgramInfoLabel;

       TButton *ProgramInfoCancelButton;

       void __fastcall KeyboarInputSubstringButtonClick(TObject *Sender);

       void __fastcall FileInputSubstringButtonClick(TObject *Sender);

       void __fastcall KeyboarInputStringButtonClick(TObject *Sender);

       void __fastcall FileInputStringButtonClick(TObject *Sender);

       void __fastcall MainMenuInputSubstringButtonClick(TObject *Sender);

       void __fastcall BeginWork();

       void __fastcall InputSubstringCancelButtonClick(TObject *Sender);

       void __fastcall InputStringCancelButtonClick(TObject *Sender);

       void __fastcall MainMenuInputStringButtonClick(TObject *Sender);

       void __fastcall ShowAutomatCancelButtonClick(TObject *Sender);

       void __fastcall MainMenuShowAutomatClick(TObject *Sender);

       void __fastcall ShowAutomatPaintBoxPaint(TObject *Sender);

       void __fastcall MainMenuExitButtonClick(TObject *Sender);

       void __fastcall MainMenuStudyAlgorithmButtonClick(TObject *Sender);

       void __fastcall StudyButtonClick(TObject *Sender);

       void __fastcall VisualSearchCancelButtonClick(TObject *Sender);

       void __fastcall MainMenuVisualSearchButtonClick(TObject *Sender);

       void __fastcall VisualSearchAutomatPaintBoxClick(TObject *Sender);

       void __fastcall VisualSearchStringPaintBoxPaint(TObject *Sender);

       void __fastcall VisualSearchGoButtonClick(TObject *Sender);

       void __fastcall StudyAlgorithmCancelButtonClick(TObject *Sender);

       void __fastcall MainMenuByMethodButtonClick(TObject *Sender);

       void __fastcall MethodInfoNextPageButtonClick(TObject *Sender);

       void __fastcall MethodInfoPrevPageButtonClick(TObject *Sender);

       void __fastcall MethodInfoCancelButtonClick(TObject *Sender);

       void __fastcall MainMenuByProgramButtonClick(TObject *Sender);

       void __fastcall ProgramInfoCancelButtonClick(TObject *Sender);

private:    // User declarations

public:     // User declarations

       __fastcall TForm1(TComponent* Owner);

};

//---------------------------------------------------------------------------

extern PACKAGE TForm1 *Form1;

//---------------------------------------------------------------------------

#endif

Г3. Файл Unit1.cpp

//---------------------------------------------------------------------------

#include <vcl.h>

#pragma hdrstop

#include "Unit1.h"

//---------------------------------------------------------------------------

#pragma package(smart_init)

#pragma resource "*.dfm"

#include <Windows.h>

#include <stdio.h>

#include <time.h>

#include <algorithm>

#include <map>

#include <vector>

#include <string>

#include <stdlib.h>

using namespace std;

#include "AutomatFunctions.h"

TForm1 *Form1;

//AnsiString str="abvdsweertyygvedrszbresvzemkmzokcosef",substr="0102x0103abc";

AnsiString str="010200101020110102010301020102010302",substr="0102010302";

automat machine;

bool begin_work=false;

const int COUNT_PAGE_METHOD_INFO=4;

int now_method_info_page=1;

AnsiString MethodInfo[]=

{

"Метод конечных автоматов позволяет определить вхождение подстроки \

за один проход по строке (линейное время, пропорционально длине \

строки). При этом препроцессинг (построение автомата) требует \

квадратичного времени (пропорционального квадрату длины подстроки).",

"Количество состояний автомата равно количеству символов в подстроке \

плюс одно начальное. Входной алфавит автомата - строка, где производится \

поиск. Нахождение автомата в i-том состоянии означает, что i символов \

справа от текущей позиции строки являются префиксом подстроки.",

"Очевидно, что в автомате будет присутствовать переходы из i-того в \

(i+1)-ое состояние по i-тому символу строки (индексация с нуля). Главную \

сложность представляет необходимость учитывать повторение префиксов в \

строке. Например, переход из третьего состояния по символу 'b' в строке \

\"abac\"",

"При выполнении всех вышеописанных условий можно будет подавать строку на \

вход построенному автомату. В позиции, где автомат достигает конечного \

состояния, находится конец вхождения подстроки."

};

//Функция отрисовки автомата на Canvas-е

void ShowAutomat(TPaintBox *Box,int now_state,char c='\0')

{

       const int BeginX=10,BeginY=10;

       const int StateWidth=40,StateHeight=70;

       const int TextInterval=5;

       const int TextLineInterval=15;

       const int HorizInterval=0,VertInterval=30;

       const int CircleRadius=30;

       const int Width=11;

       int i;

       int x;

       bool f;

       automat_state::iterator I;

       int X=BeginX,Y=BeginY;

       Box->Canvas->Brush->Color=clMedGray;

       #include <Windows.h>

       PatBlt(Box->Canvas->Handle,0,0,

               Box->Width,Box->Height, clWhite);

       for (i=0,x=0;i<machine.size();i++)

       {

               //Прорисовка круга

               TRect TR(X+(StateWidth-CircleRadius)/2,

                                    Y,X+(StateWidth+CircleRadius)/2,

                                    Y+CircleRadius);

               AnsiString text;

               Box->Canvas->Brush->Color=clMedGray;

               if (i==now_state)

                       Box->Canvas->Brush->Style=bsSolid;

               else

                       Box->Canvas->Brush->Style=bsClear;

               Box->Canvas->Ellipse(TR.Left,TR.Top,TR.Right,TR.Bottom);

               //Прорисовка символа

               Box->Canvas->Brush->Style=bsClear;

               Box->Canvas->Font->Color=clBlack;

               if (i<machine.size()-1)

                       text=IntToStr(i);

               else

                       text="";

               Box->Canvas->TextRect(TR,TR.Left+CircleRadius/2-6,

                               TR.Top+CircleRadius/2-7,text);

               //Прорисовка переходов

               if (i<machine.size()-1)//Только не для конечного состояния

               {

                       int LineY=TR.Bottom+TextInterval;

                       f=false;

                       for (I=machine[i].begin();I!=machine[i].end();++I)

                       {

                               if (i==now_state && I->first==c)

                               {

                                       Box->Canvas->Font->Color=clRed;

                                       f=true;

                               }

                               else

                               {

                                       Box->Canvas->Font->Color=clBlack;

                               }

                               if (I->second<machine.size()-1)

                                       Box->Canvas->TextOut(TR.Left,

                                               LineY,"'"+AnsiString(I->first)+"'->"+IntToStr(I->second));

                               else

                                       Box->Canvas->TextOut(TR.Left,

                                               LineY,"'"+AnsiString(I->first)+"'->[K]");

                               LineY+=TextLineInterval;

                       }

                       if (!f && c!='\0' && i==now_state)

                       {

                               Box->Canvas->Font->Color=clRed;

                               Box->Canvas->TextOut(TR.Left,

                                       LineY,"to 0");

                       }

               }

               X+=StateWidth+HorizInterval;

               ++x;

               if (x==Width)

               {

                       X=BeginX;

                       Y+=StateHeight+VertInterval;

               }

       }

}

//Функция отрисовки строки на Canvas-е

void ShowString(TPaintBox *Box,int now_pos,int L=1)

{

       const int BeginX=0,BeginY=0;

       const int HorizInterval=10;

       char *arr=str.c_str();

       int len=str.Length();

       int i;

       Box->Canvas->Font->Name="Courier";

       Box->Canvas->Font->Color=clBlack;

       for (i=0;i<len;i++)

       {

               if (i>=now_pos && i<now_pos+L)

                       Box->Canvas->Font->Color=clRed;

               else if (i==now_pos+L)

                       Box->Canvas->Font->Color=clBlack;

               Box->Canvas->TextOut(BeginX+i*HorizInterval,BeginY,

                               AnsiString(arr[i]));

       }

}

void SetMethodInfoPage(int page)

{

       now_method_info_page=page;

       Form1->MethodInfoLabel->Caption=MethodInfo[now_method_info_page];

       Form1->MethodInfoPrevPageButton->Visible=(now_method_info_page!=0);

       Form1->MethodInfoNextPageButton->Visible=

                       (now_method_info_page!=COUNT_PAGE_METHOD_INFO-1);

}

void InitPanel(TPanel *P)

{

       P->Left=1;

       P->Top=1;

       P->Visible=false;

}

//---------------------------------------------------------------------------

__fastcall TForm1::TForm1(TComponent* Owner)

       : TForm(Owner)

{

       InitPanel(MainMenuPanel);

       InitPanel(InputSubstringPanel);

       InitPanel(InputStringPanel);

       InitPanel(ShowAutomatPanel);

       InitPanel(StudyAlgorithmPanel);

       InitPanel(VisualSearchPanel);

       InitPanel(MethodInfoPanel);

       InitPanel(ProgramInfoPanel);

       MainMenuPanel->Visible=true;

       build_automat(substr.c_str(),machine);

       InputSubstringCancelButton->Visible=false;

       InputStringCancelButton->Visible=false;

       ProgramInfoLabel->Caption =

"Программа является курсовым проектом студента 2 курса\n\

ДонНТУ (КНТ, ПОС-12а)\n\

Ольмезова Константина Ивановича\n\

© 2014";

}

void __fastcall TForm1::BeginWork()

{

       begin_work=true;

       InputSubstringCancelButton->Visible=true;

       InputStringCancelButton->Visible=true;

}

//---------------------------------------------------------------------------

void __fastcall TForm1::KeyboarInputSubstringButtonClick(TObject *Sender)

{

       if (KeyboardInputSubstringText->Text.Length()==0)

       {

               InputSubstringError->Caption="Введена пустая строка!";

               return;

       }

       substr=KeyboardInputSubstringText->Text;

       build_automat(substr.c_str(),machine);

       InputSubstringPanel->Visible=false;

       if (!begin_work)

       {

               InputStringPanel->Visible=true;

               Form1->Caption="Поиск подстроки через автомат - ввод строки";

       }

       else

       {

               MainMenuPanel->Visible=true;

               Form1->Caption="Поиск подстроки через автомат";

       }

       StudyInfoLabel->Caption="";

}

//---------------------------------------------------------------------------

void __fastcall TForm1::FileInputSubstringButtonClick(TObject *Sender)

{

       if (FileInputSubstringText->Text.Length()==0)

       {

               InputSubstringError->Caption="Пустое имя файла!";

               return;

       }

       FILE *F=fopen(FileInputSubstringText->Text.c_str(),"rt");

       if (!F)

       {

               InputSubstringError->Caption="Чтение из файла невозможно!";

               return;

       }

       char t[1024];

       fscanf(F,"%s",t);

       substr=t;

       fclose(F);

       build_automat(substr.c_str(),machine);

       InputSubstringPanel->Visible=false;

       if (!begin_work)

       {

               InputStringPanel->Visible=true;

               Form1->Caption="Поиск подстроки через автомат - ввод строки";

       }

       else

       {

               MainMenuPanel->Visible=true;

               Form1->Caption="Поиск подстроки через автомат";

       }

       StudyInfoLabel->Caption="";

}

//---------------------------------------------------------------------------

void __fastcall TForm1::KeyboarInputStringButtonClick(TObject *Sender)

{

       if (KeyboardInputStringText->Text.Length()==0)

       {

               InputStringError->Caption="Введена пустая строка!";

               return;

       }

       str=KeyboardInputStringText->Text;

       InputStringPanel->Visible=false;

       MainMenuPanel->Visible=true;

       StudyInfoLabel->Caption="";

       Form1->Caption="Поиск подстроки через автомат";

       BeginWork();

}

//---------------------------------------------------------------------------

void __fastcall TForm1::FileInputStringButtonClick(TObject *Sender)

{

       if (FileInputStringText->Text.Length()==0)

       {

               InputStringError->Caption="Пустое имя файла!";

               return;

       }

       FILE *F=fopen(FileInputStringText->Text.c_str(),"rt");

       if (!F)

       {

               InputStringError->Caption="Чтение из файла невозможно!";

               return;

       }

       char t[1024];

       fscanf(F,"%s",t);

       str=t;

       fclose(F);

       InputStringPanel->Visible=false;

       MainMenuPanel->Visible=true;

       StudyInfoLabel->Caption="";

       Form1->Caption="Поиск подстроки через автомат";

       BeginWork();

}

//---------------------------------------------------------------------------

void __fastcall TForm1::MainMenuInputSubstringButtonClick(TObject *Sender)

{

       MainMenuPanel->Visible=false;

       InputSubstringPanel->Visible=true;

       InputSubstringError->Caption="";

       KeyboardInputSubstringText->Text=substr;

       FileInputSubstringText->Text="";

       Form1->Caption="Поиск подстроки через автомат - ввод подстроки";

}

//---------------------------------------------------------------------------

void __fastcall TForm1::InputSubstringCancelButtonClick(TObject *Sender)

{

       InputSubstringPanel->Visible=false;

       MainMenuPanel->Visible=true;

       Form1->Caption="Поиск подстроки через автомат";

}

//---------------------------------------------------------------------------

void __fastcall TForm1::InputStringCancelButtonClick(TObject *Sender)

{

       InputStringPanel->Visible=false;

       MainMenuPanel->Visible=true;

       Form1->Caption="Поиск подстроки через автомат";

}

//---------------------------------------------------------------------------

void __fastcall TForm1::MainMenuInputStringButtonClick(TObject *Sender)

{

       MainMenuPanel->Visible=false;

       InputStringPanel->Visible=true;

       InputStringError->Caption="";

       KeyboardInputStringText->Text=str;

       FileInputStringText->Text="";

       Form1->Caption="Поиск подстроки через автомат - ввод строки";

}

//---------------------------------------------------------------------------

void __fastcall TForm1::ShowAutomatCancelButtonClick(TObject *Sender)

{

       ShowAutomatPanel->Visible=false;

       MainMenuPanel->Visible=true;

       Form1->Caption="Поиск подстроки через автомат";

}

//---------------------------------------------------------------------------

void __fastcall TForm1::MainMenuShowAutomatClick(TObject *Sender)

{

       MainMenuPanel->Visible=false;

       ShowAutomatPanel->Visible=true;

       Form1->Caption="Поиск подстроки через автомат - отображение автомата";

}

//---------------------------------------------------------------------------

void __fastcall TForm1::ShowAutomatPaintBoxPaint(TObject *Sender)

{

       ShowAutomat(ShowAutomatPaintBox,machine.size());

}

//---------------------------------------------------------------------------

void __fastcall TForm1::MainMenuExitButtonClick(TObject *Sender)

{

       Form1->Close();        

}

//---------------------------------------------------------------------------

void __fastcall TForm1::MainMenuStudyAlgorithmButtonClick(TObject *Sender)

{

       MainMenuPanel->Visible=false;

       StudyAlgorithmPanel->Visible=true;

       StudySubstringLabel->Caption="Substring: "+substr;

       StudyStringLabel->Caption="String: "+str;

       Form1->Caption="Поиск подстроки через автомат - исследование алгоритма";

}

//---------------------------------------------------------------------------

void __fastcall TForm1::StudyButtonClick(TObject *Sender)

{

       const int COUNT=1000000;

       int i,j,q;

       DWORD begin,time;

       int pos;

       char *str_arr,*sub_arr;

       int str_len=str.Length(),sub_len=substr.Length();

       str_arr=str.c_str();

       sub_arr=substr.c_str();

       AnsiString text=IntToStr(COUNT)+" run search\n================\n";

       begin=GetTickCount();

       for (q=0;q<COUNT;q++)

               pos=strstr(str_arr,sub_arr)-str_arr;

       time=GetTickCount()-begin;

       text+="Standart search time: "+IntToStr(time)+"\n";

       StudyInfoLabel->Caption=text;

       begin=GetTickCount();

       for (q=0;q<COUNT;q++)

       {

               pos=0;

               for (i=0;i<=str_len-sub_len;i++)

               {

                       for (j=0;j<sub_len;j++)

                                if (str_arr[i+j]!=sub_arr[j])

                                       break;

                       if (j==sub_len)

                       {

                                pos=i+1;

                                       break;

                       }

                }

       }

       time=GetTickCount()-begin;

       text+="Linear search time: "+IntToStr(time)+"\n";

       StudyInfoLabel->Caption=text;

       begin=GetTickCount();

       for (q=0;q<COUNT;q++)

               pos=automat_search_substring(str_arr,machine,sub_arr);

       time=GetTickCount()-begin;

       text+="Automat search time: "+IntToStr(time)+"\n";

       StudyInfoLabel->Caption=text;

}

//---------------------------------------------------------------------------

void __fastcall TForm1::VisualSearchCancelButtonClick(TObject *Sender)

{

       VisualSearchPanel->Visible=false;

       MainMenuPanel->Visible=true;

       Form1->Caption="Поиск подстроки через автомат";

}

//---------------------------------------------------------------------------

void __fastcall TForm1::MainMenuVisualSearchButtonClick(TObject *Sender)

{

       MainMenuPanel->Visible=false;

       VisualSearchPanel->Visible=true;

       Form1->Caption="Поиск подстроки через автомат - наглядный поиск";

}

//---------------------------------------------------------------------------

void __fastcall TForm1::VisualSearchAutomatPaintBoxClick(TObject *Sender)

{

       ShowAutomat(VisualSearchAutomatPaintBox,machine.size());

}

//---------------------------------------------------------------------------

void __fastcall TForm1::VisualSearchStringPaintBoxPaint(TObject *Sender)

{

       ShowString(VisualSearchStringPaintBox,str.Length());

}

//---------------------------------------------------------------------------

void __fastcall TForm1::VisualSearchGoButtonClick(TObject *Sender)

{

       int i;

       int now=0;

       int len=str.Length();

       char *arr=str.c_str();

       ShowString(VisualSearchStringPaintBox,-1);

       ShowAutomat(VisualSearchAutomatPaintBox,now);

       for (i=0;i<len;i++)

       {

               Sleep(300);

               ShowString(VisualSearchStringPaintBox,i);

               Sleep(300);

               ShowAutomat(VisualSearchAutomatPaintBox,now,*arr);

               if (machine[now].count(*arr))

                       now=machine[now][*arr];

               else

                       now=0;

               Sleep(300);

               ShowString(VisualSearchStringPaintBox,-1);

               ShowAutomat(VisualSearchAutomatPaintBox,now);

               ++arr;

               if (now==machine.size()-1)

                       break;

       }

       if (i!=len)

       {

               ShowString(VisualSearchStringPaintBox,

                               i-substr.Length()+1,substr.Length());

       }

       else

       {

       }

}

//---------------------------------------------------------------------------

void __fastcall TForm1::StudyAlgorithmCancelButtonClick(TObject *Sender)

{

       StudyAlgorithmPanel->Visible=false;

       MainMenuPanel->Visible=true;

       Form1->Caption="Поиск подстроки через автомат";

}

//---------------------------------------------------------------------------

void __fastcall TForm1::MainMenuByMethodButtonClick(TObject *Sender)

{

       MainMenuPanel->Visible=false;

       MethodInfoPanel->Visible=true;

       SetMethodInfoPage(0);

       Form1->Caption="Поиск подстроки через автомат - о методе";

}

//---------------------------------------------------------------------------

void __fastcall TForm1::MethodInfoNextPageButtonClick(TObject *Sender)

{

       SetMethodInfoPage(++now_method_info_page);

}

//---------------------------------------------------------------------------

void __fastcall TForm1::MethodInfoPrevPageButtonClick(TObject *Sender)

{

       SetMethodInfoPage(--now_method_info_page);        

}

//---------------------------------------------------------------------------

void __fastcall TForm1::MethodInfoCancelButtonClick(TObject *Sender)

{

       MethodInfoPanel->Visible=false;

       MainMenuPanel->Visible=true;

       Form1->Caption="Поиск подстроки через автомат";      

}

//---------------------------------------------------------------------------

void __fastcall TForm1::MainMenuByProgramButtonClick(TObject *Sender)

{

       MainMenuPanel->Visible=false;

       ProgramInfoPanel->Visible=true;

       Form1->Caption="Поиск подстроки через автомат - о программе";

}

//---------------------------------------------------------------------------

void __fastcall TForm1::ProgramInfoCancelButtonClick(TObject *Sender)

{

       ProgramInfoPanel->Visible=false;

       MainMenuPanel->Visible=true;

       Form1->Caption="Поиск подстроки через автомат";

}

//---------------------------------------------------------------------------




1. і Для вирішення поставленої мети останнім часом широкого застосування набуло додавання різних наповнювач
2. А. С. Пушкин и Москва
3. отцов церкви наиболее авторитетных церковных авторов с чьими именами связан период формирования христи
4. Структура и содержание контрактов
5. нанесення складів забарвлень на поверхні конструкцій будівель і споруд з метою збільшення терміну їх служб
6. є -гактивним; 7
7. геодезические работы выполняются с целью нанесения границ углов поворота и площади ЗУ
8. тематическое планирование по русскому языку для 10 класса гуманитарного профиля на 20092010 учебный год Со
9. Казаки
10. на тему- Экономическая обоснование эфективности использавоние основных фондов на предприятии Вып

Материалы собраны группой SamZan и находятся в свободном доступе