Развитие графовых и матричных способов представления алгоритмов
Рассмотрение вопроса последовательного доопределения граф-схемы абстрактного алгоритма и представления его двудольным графом. Определение возможности задания алгоритмов в матрично-предикатном виде. Анализ особенностей доопределения оператора действия.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | статья |
| Язык | русский |
| Дата добавления | 30.07.2017 |
| Размер файла | 232,7 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Волгоградский государственный технический университет
Развитие графовых и матричных способов представления алгоритмов
Поляков В.С., Поляков С.В., Авдеюк О.А., Наумов В.Ю., Павлова Е.С., Скворцов М.Г.
Аннотация
В статье рассмотрен вопрос последовательного доопределения граф-схемы абстрактного алгоритма и представления его двудольным графом. Приведен пример возможности задания алгоритмов в матрично-предикатном виде. В заключении указано, что полученный в результате матрично-предикатный вид полностью идентичен графической форме, но вместе с тем позволяет работать с алгоритмами значительно эффективнее, так как появляется возможность задавать их в матрично-предикатном виде и частично автоматизировать эвристические методы их построения.
Ключевые слова: алгоритм, граф-схема, двудольный граф, множество, матрица, предикат, логический оператор.
Известно, что алгоритм - это конечный набор правил, позволяющий чисто механически решить поставленную задачу. Большинство алгоритмов, применяемых в настоящее время, являются последовательными. Запись алгоритма осуществляется в следующем виде: словесная или вербальная (языковая, формульно-словесная и т.д.); графическая (например, блок-схемы, ДРАКОН-схемы, диаграммы Насси- Шнейдермана); в виде псевдокодов, представляющие собой частично формализованные описания алгоритмов, которое состоит из отдельных фраз естественного языка и некоторых элементов языка программирования; - программная - тексты алгоритма записывается на языке программирования (программа). Разработка алгоритмов осуществляется, как правило, человеком и носит эвристический характер. Процессы разработки алгоритмов и формализации взаимодействия их между собой сложны и трудоёмки, поэтому плохо поддаются автоматизации. Поэтому актуальной задачей является разработки такой формы представления алгоритма, которая позволит автоматизировать эвристические методы их построения.
Организацию взаимодействия алгоритмов между собой (например, параллельную их работу) можно разбить на два этапа:
- представление алгоритма в виде удобном для обработки в ЭВМ,
- разработка операций над алгоритмами.
Рассмотрим произвольный алгоритм, заданный в виде граф-схемы (рис. 1). При таком задании выделяются два типа вершин:
- вершины, определяющие выполнение отдельных операций (множество , операторы действия);
- вершины, определяющие логику (порядок) перемещения от выполнения одной операции к выполнению следующей (,операторы логики).
Рис. 1. - Граф-схема произвольного алгоритма
Такой способ работы с алгоритмами имеет следующие недостатки: переход от одного оператора действия к другому в некоторых случаях ничем не обозначен; определяющие логику выполнения алгоритма условия часто задаются несколькими логическими функциями. Для устранения этих проблем предлагается доопределить соответствующие операторы следующим образом и использовать указанную ниже последовательность действий:
1. Будем задавать конец выполнения каждого оператора действия Аj с помощью соответствующего оператора логики б j (рис. 2).
Рис. 2. - Доопределение оператора действия Аj оператором логики б j
2. Различные композиции операторов логики заменим на один многозначный оператор. На рис. 3а приведены две логические функции б и в , а на рис. 3б реализующий аналогичную функцию многозначный оператор б?в.
Рис. 3. - Замена двух операторов логики одним многозначным оператором граф предикатный матричный
3. Доопределяем каждый оператор действия исходного алгоритма Аi алгоритма А как показано на рисунках 4а, б, в, г, д.
4. Введем следующие обозначения:
Таблица 1 Композиция и логические значения функций
|
Композиция функций |
Логические значения функций |
||||
|
б00 =м0 |
I= м00 |
I= м01 |
|||
|
б01?б1 =м1 |
б01 =м10 |
б01 б1-1 =м11 |
б01 б1-1 б1-2 =м12 |
б01 б1-1 б1-2=м13 |
|
|
б 02?б2-1?б2-2=м2 |
б02 =м20 |
б02 б2-1 =м21 |
б02 б2-1 б2-2=м22 |
б02 б2-1 б2-2=м23 |
|
|
б 3=м3 |
б3 =м30 |
б 3=м31 |
|||
|
б 4 =м4 |
б4 =м40 |
б 4 =м41 |
Рис. 4. - Доопределение оператора действия Аi алгоритма А
5. Применим доопределённые операторы действия (рис.4) и новые обозначения (таблица 1) для исходного алгоритма (рис. 1) и получим новый доопределённый алгоритм (рис. 5).
Рис. 5 - Доопределённый алгоритма А с новыми обозначениями
6. Доопределённый алгоритм (рис. 5), можно представить двудольным графом, то есть ориентированным графом с двумя типами непересекающихся вершин (рис. 6) [3]. При этом вводятся обозначения: м11,2 = м11? м12 и м20,1 = м20? м21
Рис. 6 - Двудольный граф алгоритма А
7. Двудольный граф (рис. 6) запишем оператором действия исходного алгоритма OpA в матрично-предикатном виде :
Полученный в результате матрично-предикатный вид полностью идентичен графической форме, но вместе с тем позволяет работать с алгоритмами значительно эффективнее, так как появляется возможность задавать их в матрично-предикатном виде и частично автоматизировать эвристические методы их построения.
Литература
1. Поляков В.С., Поляков С.В., Муха Ю.П. Представление транспортно-информационного потока взаимодействием операторов трассы и движущихся по ней объектов // Телекоммуникации. 2013. № 7. С. 3-7.
2. Рутковская Д., Пилиньский М., Рутковский Л. Нейронные сети, генетические алгоритмы и нечеткие системы. М.: Горячая Линия - Телеком, 2007. 452 с.
3. Дворецкий С.И., Муромцев Ю.Л. и др. Моделирование систем. М.: Academia, 2009. 320 с.
4. Поляков С.В., Поляков В.С. Моделирование параллельно протекающих процессов блоками взаимодействующих компонентов. // Контроль. Диагностика. 2008. № 8. С. 70-72.
5. Астанин С.В., Драгныш Н.В., Жуковская Н.К. Вложенные метаграфы как модели сложных объектов // Инженерный вестник Дона, 2012, №4. URL: ivdon.ru/magazine/archive/n4p2y2012/1434/.
6. Поляков В.С., Поляков С.В., Муха Ю.П. Применение совокупности новых установок, представлений и терминов при моделировании информационных потоков в сложных системах // Телекоммуникации. 2013. № 1. С. 2-5.
7. Поляков В.С., Поляков С.В., Нефедьев А.И. Математическая модель подвески подвижной части электроизмерительного прибора.// Инженерный вестник Дона, 2013. №3. URL: ivdon.ru/magazine/archive/n3y2013/1788.
8. Лацис А.О. Параллельная обработка данных. М.: Academia, 2010. 336 с.
9. Voevodin V.V. Information structure of sequential programs // Russ. J. of Num. An. and Math. Modelling. - 1995. V.10. №3. P. 279-286.
10. Voevodin V.V. Mathematical foundations of parallel computing. World Scientific Publishing Co., Series in computer science. 1992. V.33. 343 p.
Размещено на Allbest.ru
...Подобные документы
Понятие и свойства алгоритма, виды, характеристики. Роль алгоритма в построении программы, представление и запись. Словесный, графический, табличный способ. Псевдокод. Примеры известных алгоритмов. Операции над массивами. Уточнение корней уравнения.
курсовая работа [1,1 M], добавлен 10.11.2016- Разработка алгоритмов и программ для определения сходства семантических сетей на основе их сложности
Семантические сети как модели представления знаний. Основные методы определения сходства графовых моделей систем. Метод решения задач определения сходства семантических сетей на основе их сложности. Разработка алгоритмов и их программная реализация.
дипломная работа [1,3 M], добавлен 17.12.2011 Основные этапы и принципы решения задач на ЭВМ, порядок постановки задачи и построения алгоритма. Сущность теории алгоритмов, ее основные элементы и взаимосвязь, свойства, методика представления в виде схемы, ее обозначения и использующиеся символы.
лекция [136,3 K], добавлен 11.03.2010Общее понятие алгоритма и меры его сложности. Временная и емкостная сложность алгоритмов. Основные методы и приемы анализа сложности. Оптимизация, связанная с выбором метода построения алгоритма и с выбором методов представления данных в программе.
реферат [90,6 K], добавлен 27.11.2012Комплексное исследование истории развития, основных понятий, области применения и особенностей генетических алгоритмов. Анализ преимуществ генетических алгоритмов. Построение генетического алгоритма, позволяющего находить максимум целочисленной функции.
курсовая работа [27,9 K], добавлен 23.07.2011Основные свойства алгоритмов, формы их представления, примеры блок-схем. Семейство шрифта, размер, стиль, цвет, автокернинг как основные атрибуты шрифта. Функции и внутреннее устройство микропроцессоров, технические характеристики и реализация.
контрольная работа [1,5 M], добавлен 17.07.2011Применение теории графов и алгоритмов на графах среди дисциплин и методов дискретной математики. Граф как совокупность двух множеств. Основные способы численного представления графа. Элементы и изоморфизмы графов. Требования к представлению графов в ЭВМ.
курсовая работа [162,2 K], добавлен 04.02.2011Исследование особенностей разработки линейных алгоритмов и их реализации в среде Delphi. Составление тестов для проверки программы. Характеристика основных элементов интерфейса, компонентов, значения их свойств. Построение графической схемы алгоритма.
лабораторная работа [316,6 K], добавлен 08.11.2012Понятие и классификация алгоритмов маршрутизации. Основное определение теории графов. Анализ и разработка алгоритмов Дейкстры и Флойда на языке программирования C# для определения наилучшего пути пакетов, передаваемых через сеть. Их сравнительный анализ.
курсовая работа [1,2 M], добавлен 16.05.2015Принцип микропрограммного управления. Управляющие автоматы с жесткой и программируемой логикой. Граф-схемы алгоритмов. Синтез управляющего автомата по граф-схеме алгоритма. Построение управляющего автомата с программируемой логикой на основе ПЗУ.
курсовая работа [263,8 K], добавлен 25.01.2011Построение граф-схем и матричной схемы алгоритмов. Формулы фазовых переходов. Выполнение операции "Пересечение" над заданными отношениями базы данных. Принципы взаимосвязи страниц виртуальной памяти с сегментами оперативно запоминающих устройств.
контрольная работа [239,4 K], добавлен 10.10.2015Основные этапы создания алгоритмов, представление в виде программы. Рассмотрение методов решения задач. Метод поэтапных уточнений. Различие между численными и логическими алгоритмами. Реализация цикла со счетчиком. Процесс разработки сложного алгоритма.
презентация [1,3 M], добавлен 22.10.2013Основные особенности эволюционных алгоритмов. Описание алгоритмов селекции, мутации, скрещивания, применяемых для реализации генетических алгоритмов. Вычисление функции приспособленности. Программная реализация. Тестирование и руководство пользователя.
курсовая работа [1,3 M], добавлен 11.03.2014Особенности разработки и реализации обучающей программы и схемы алгоритмов на языке программирования С++. Понятие равномерной и неравномерной дискретизации. Представление информации (составление кода) в виде таблицы перекодировки или многочлена.
курсовая работа [704,6 K], добавлен 06.03.2013Изучение особенностей создания алгоритмов вычислительных задач. Визуальное программирование стандартных компонентов среды программирования Delphi. Технология создания компонента Delphi для решения производственной задачи. Выполнение блок-схемы алгоритма.
курсовая работа [638,0 K], добавлен 30.01.2015Анализ алгоритмов, оценка параметров алгоритма (эффективности, сложности, правильности). Комплексный анализ эффективности алгоритма на основе комплексной оценки ресурсов формальной системы. Верификация при коллективной разработке программных систем.
презентация [234,9 K], добавлен 22.10.2013Основные понятия и определения алгоритмов на графах. Связные графы без циклов, свободное дерево или дерево без корня. Ориентированные графы (орграфы), их использование для представления отношений между объектами. Матрицы смежности и инциденций.
презентация [93,9 K], добавлен 13.09.2013Описание формальной модели алгоритма на основе рекурсивных функций. Разработка аналитической и программной модели алгоритма для распознающей машины Тьюринга. Разработка аналитической модели алгоритма с использованием нормальных алгоритмов Маркова.
курсовая работа [1,5 M], добавлен 07.07.2013Разработка модифицированных алгоритмов поиска оптимального маршрута в графе. Задание дополнительных условий и ограничений. Реализация модели для внутреннего представления транспортной сети. Создание программного комплекса в среде Visual Studio 2010.
курсовая работа [1,1 M], добавлен 16.04.2015Основные понятия теории графов. Ценность системного подхода. Представления операций во времени. Структурно-лингвистическое (знаковое) моделирование. Формы и средства графического представления информации. Методы формализованного представления систем.
курсовая работа [2,2 M], добавлен 15.06.2015
