WWW.KNIGI.KONFLIB.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

 
<< HOME
Научная библиотека
CONTACTS

Pages:     | 1 |   ...   | 6 | 7 ||

«САМАРСКИЙ ИНСТИТУТ ИНЖЕНЕРОВ ЖЕЛЕЗНОДОРОЖНОГО ТРАНСПОРТА Кафедра телекоммуникаций на железнодорожном транспорте СОВРЕМЕННЫЕ ТЕХНОЛОГИИ РАЗРАБОТКИ И ТЕСТИРОВАНИЯ ...»

-- [ Страница 8 ] --

Эффективность зависит от связности графа. Для полносвязанного графа реализуется полный просмотр всех схем маршрутов. В остальных случаях число проверок реализуемости маршрутов на графе G равно сумме мощностей множеств достижимости и недостижимости. Для случая, рассмотренного в примере, таких проверок было произведено 25 и обнаружено 4 схемы, в то время как общее число проверок 5!=120. G для некоторого графа G, можно оценить по формуле:

где k —мощность множества достижимости или недостижимости И/ИЛИ-графа.

Для того чтобы выяснить, как связана топологическая сложность графа со сложностью алгоритма, рассмотрим наиболее распространенный метод оценки топологической сложности, основанный на цикломатической метрике Маккейба [26].

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

Цикломатическая метрика программы определяется из ее управляющего графа следующим образом:

где m — число дуг в графе, n — число вершин.

Многие авторы подчеркивают адекватность этой метрики интуитивному пониманию сложности программного модуля [16]. На основании опыта программирования и статистического материала [4] была определена разумная верхняя граница сложности G, равная 10. Рассмотрим, как связана эта метрика со сложностью алгоритма построения непериодических маршрутов, определяемой с помощью топологического дерева. С этой целью проведем эксперимент, который заключается в построении полного множества графов заданного порядка и оценки их сложности с помощью метрики Маккейба.

Для проведения эксперимента реализован алгоритм, который порождает графы, удовлетворяющие определенным условиям. Эти условия накладываются концепциями технологии графо-символического программирования и подразумевают наличие в графе корневой и концевой вершин. Алгоритм порождения графов основан на методе частичного перебора из полного комбинаторного множества всех существующих графов заданного порядка.

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

Зависимость разброса усредненной сложности алгоритма АПЧ в зависимости от степени графа получена экспериментально, в результате моделирования орграфов различной структуры (см. рис.3.11).

Просматривались варианты от линейных графов (нижняя линия) до полносвязанных графов (верхняя линия). “Средняя” линия на рисунке разбивает приблизительно пополам множество топологически разных графов. Около этой линии “концентрируется” наибольшее число топологически разных графов одинакового порядка. Из рисунка видно, что с ростом n сложность алгоритма АЧП увеличивается даже для линейных графов, и рациональным порядком графа можно считать n [ 6,8].

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

СПИСОК ЛИТЕРАТУРЫ

1. Агафонов В.Н. Типы и абстракция данных в языках программирования // Данные в языках программирования. - М.: Мир, 1982.- с. 265-327.

2. Архангельский Б.В., Кучма И.Б. Система ГРАФ-ФОРТРАН, осуществляющая построение и анализ управляющего графа программ // УСиМ. 1989.№1, с.41-45.

3. Батищев Д.И., Высоцкий Г.О., Кузьмичев А.С. Рациональный синтез структуры “персональных” пакетов программ. // Сб. научн. трудов.

“Математическое и алгоритмическое обеспечение оптимизации сложных систем”. - Воронеж: ВПИ, 1987, с. 20-24.

4. Бетелин В.Б. Системы автоматизации труда программиста. - М.: Наука, 5. Богданов В.В., Иванов В.Н. Информация и технологизация социального пространства: проблемы и предотвращение катастроф, взрывов и напряжений // Информация и технологизация социального пространства:

Материалы к 1 Международному симпозиуму по информационным технологиям. М.- Нижний Новгород, 1994, с. 56-62.

6. Братко И. Программирование на языке ПРОЛОГ для искусственного интеллекта. - М.: Мир, 1990.- 560 с.

7. Бусленко Н.П. Моделирование сложных систем. - М.: Наука, 1968. -356 с.

8. Вагин В.Н. Дедукция и обобщение в системах принятия решений.- М.:

Наука, 1988.- 384 с.

9. Вальковский В.А., Котов В.Е., Марчик А.Г., Миренков Н.Н. Элементы параллельного программирования. - М.: Радио и связь, 1983.- 240 с.

10. Ван Тассел Д. Стиль, разработка, эффективность, отладка и испытание программ.- М.: Мир, 1985. - 332 с.

11. Вельбицкий И.В. Технология программирования. - К.: Техника, 1984.с.

12. Вельбицкий И.В., Ковалев А.Л., Лизенко С.Л. Графический интерфейс представления алгоритмов и программ // УСиМ. 1988. №4, с.42- 13. Вирт Н. Систематическое программирование. Введение. - М.: Мир, 1977. с.

автоматизированных систем с использованием концепции состояний // М.:

Известия АН СССР. Техническая кибернетика. 1981. №4, с 86-93.

15. Глушков В.М. Основы безбумажной информатики. - М.: Наука, 1987. - 16. Горбатов В.А. Основы дискретной математики. - М.: Высшая школа, 1986.с.

17. Григорьев В.Л. i486. Архитектура и программирование. - М.: ГРАНАЛ, 18. Громов Г.Р. Национальные информационные ресурсы: проблемы промышленной эксплуатации. - М.: Наука, 1985. - 240 с.

19. Дал У.И. Языки для моделирования систем с дискретными событиями // В сб. “Языки программирования”. - М.: Мир, 1972, с. 344-401.

20. Дейкстра Э.В. Дисциплина программирования. - М.: Мир, 1978.- 275 c.

22. Ефимова М.Н. Алгоритмические языки. - М.: Мир, 23. Зелковиц М., Шоу А., Гэннон Дж. Принципы разработки программного обеспечения. - М.: Мир, 1982. - 368 с.

24. Кинг А. Windows 95 изнутри.- СПб:Питер, 1995. -512 с.

25. Кахо М.И., Калья А.П., Тыугу Э.Х. Инструментальная система программирования ЕС ЭВМ (ПРИЗ). - М.: Финансы и статистика, 1988.с.

26. Коварцев А.Н. Автоматизация разработки и тестирования программных средств. - Самар. гос. аэрокосм. ун-т., Самара, 1999. - 150 с.

27. Лавров С.С. Синтез программ // Кибернетика, 1982.- №6. - с.11-16.

28. Липаев В.В. Отладка сложных программ.Методы, средства, технология. М.: Энергратомиздат, 1993. -384 с.

29. Сван Т. Программирование для Windows в Borland C++. - М.: БИНОМ, 30. Столяров Г.К. Языки и функциональные возможности системы АСПИД- // Алгоритмы и организация решений экономических задач. - М.:

Статистика. 1979. Вып. 3, с. 131-158.

31. Тыугу Э.Х. Концептуальное программирование. - М.: Наука, 1984. - 256 с.

32. Хемминг Р.В. Численные методы.- М.: Наука, 1972.- 400 с.

33. Шаракшанэ А.С., Шахин В.П., Халецкий А.К. Испытания программ сложных автоматизированных систем. - М.: Высшая школа, 1982. - 192 с.

34. Шлеер С., Меллор С. Объектно-ориентированный анализ: моделирование мира в состояниях.- Киев: Диалектика, 1993. - 240 с.

35. Штрик А. CASE: автоматизированное проектирование программного обеспечения // Монитор. 1992. №4, с. 4-6.

36. Brachman R. J. What IS-A Is and Isn’t: An Analysis of Taxonomic Links in Semantic Networks. - Computer 16:10, 1983, pp. 30-36.

37. Liskov B., Atkinson R., Bloom T. e.a. CLU Reference Manual // Lecture Notes in Comp. Sci.- 1981.- Vol. 38. Martin J., Murch R. Application development without programmers.- In Savant Inst. seminar documentation by J. Martin. Carnfoth: Savant Res.

Studies, 39. Wegner P. Notes on object-oriented programming. - Dansk Datamatic Center, 40. Williams T. CASE-tool adds dinamic simulation of requirements analysis. // Computer Desing, 1991. N1, - p 40- 41. Yourdon E. The Texas instruments vision of CASE. - American programmer, Aprial 1990, v. 3, pp. 1-

Pages:     | 1 |   ...   | 6 | 7 ||
 


Похожие работы:

«9/17/3 Одобрено кафедрой Эксплуатация железных дорог УПРАВЛЕНИЕ ПРЕДПРИЯТИЕМ Задание на контрольную работу с методическими указаниями для студентов V курса специальности 190701 ОРГАНИЗАЦИЯ ПЕРЕВОЗОК И УПРАВЛЕНИЕ НА ТРАНСПОРТЕ (ЖЕЛЕЗНОДОРОЖНЫЙ ТРАНСПОРТ) (Д) РОАТ Москва – 2010 С о с т а в и т е л и : канд. техн. наук, доц. Кузнецова Т.Г.; канд. техн. наук, ст. преп. Сухогузова И.В.; ст. преп. Буракова А.В. Р е ц е н з е н т : д-р техн. наук, проф. Апатцев В.И. УПРАВЛЕНИЕ ПРЕДПРИЯТИЕМ Задание на...»

«rr.by СООБЩЕНИЯ. РАЗНОЕ Витебск 38 i КАК ПОДАТЬ ЧАСТНОЕ ОБЪЯВЛЕНИЕ В ГАЗЕТУ “ИЗ РУК В РУКИ”? ГАЗЕТА ЧАСТНЫХ ОБЪЯВЛЕНИЙ Условия приема на стр. 39 № 96(958) Витебск и Витебская область Рекламное издание СП “БЕЛПРОНТО”...»

«9/9/2 Одобрено кафедрой Эксплуатация железных дорог УПРАВЛЕНИЕ ГРУЗОВОЙ И КОММЕРЧЕСКОЙ РАБОТОЙ, ГРУЗОВЕДЕНИЕ Задание на курсовой проект с методическими указаниями для студентов IV курса специальности 190701.65 ОРГАНИЗАЦИЯ ПЕРЕВОЗОК И УПРАВЛЕНИЕ НА ТРАНСПОРТЕ (железнодорожный транспорт) (ПП) РОАТ Москва – 2011 С о с т а в и т е л ь — канд. техн. наук, доц. Б.П. Голубкин Р е ц е н з е н т — канд. техн. наук, доц. А.М.Орлов УПРАВЛЕНИЕ ГРУЗОВОЙ И КОММЕРЧЕСКОЙ РАБОТОЙ, ГРУЗОВЕДЕНИЕ Задание на...»

«МОРСКОЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени адмирала Г.И. НЕВЕЛЬСКОГО Конталев В.А. ПРАКТИКУМ по дисциплине Организационное поведение Владивосток 2008 УДК 658.3 ББК 62721.656.615 Конталев В.А. Практикум по дисциплине Организационное поведение: учебное пособие. – Владивосток: МГУ, 2008.-118 с. Пособие предназначено для самостоятельного изучения и выполнения практических заданий по дисциплине Организационное поведение студентами специальностей Управление персоналом и Менеджмент организации. Особое...»

«УТВЕРЖДАЮ 7%j O Y 2014 г. ОТЧЕТ о самообследовании Ф едеральным государственны м бю джетны м образовательны м учреждением высш его профессионального образования У льяновское высшее авиационное училищ е гражданской авиации (институт) Рассмотрен и одобрен на заседании Ученого совета института 03.04.2014, протокол № 3 Ульяновск 2014 СОДЕРЖАНИЕ стр. Введение 6 Общие сведения об УВАУ ГА (И) 7 1. 2. Организационно-правовое обеспечение образовательной деятельности 2.1. Учредительные документы...»

«rr.by СООБЩЕНИЯ. РАЗНОЕ Витебск 30 i КАК ПОДАТЬ ЧАСТНОЕ ОБЪЯВЛЕНИЕ В ГАЗЕТУ “ИЗ РУК В РУКИ”? ГАЗЕТА ЧАСТНЫХ ОБЪЯВЛЕНИЙ Условия приема на стр. 31 № 2(964) Витебск и Витебская область Рекламное издание СП “БЕЛПРОНТО”...»

«К АТАЛОГ Д ЕТАЛЕИ И СБОРОЧНЫХ Е ДИНИЦ ЧАСТЬ 3 СИСТЕМЫ ПЛАНЕРА КНИГА 3 Главы 34, 35 КАТАЛОГ ДЕТАЛЕЙ И СБОРОЧНЫХ ЕДИНИЦ ПЕРЕЧЕНЬ ГЛАВ КАТАЛОГА Номер Наименование главы ВВЕДЕНИЕ Часть I - УКАЗАНИЯ ПО ОБЩЕМУ ОБСЛУЖИВАНИЮ Хранение самолета (наземное оборудование) 12 Часть 2 - ПЛАНЕР. Книга I 20 Общие указания 21 Фюзеляж Часть 2 - ПЛАНЕР. Книга 2 Двери и люки 22 Окна 23 Оперение 25 26 Пилоны Часть 2. - ПЛАНЕР. Книга 3 Крыло (включая раздел 24.43.00) 24 Часть 2 - ПЛАНЕР. Книга 4 Крыло (с раздела...»

«Утверждена Постановлением Правительства Российской Федерации от 5 декабря 2001 г. N 848 ФЕДЕРАЛЬНАЯ ЦЕЛЕВАЯ ПРОГРАММА РАЗВИТИЕ ТРАНСПОРТНОЙ СИСТЕМЫ РОССИИ (2010 - 2015 ГОДЫ) (в ред. Постановлений Правительства РФ от 20.05.2008 N 377, от 22.04.2010 N 278, от 12.10.2010 N 828, от 21.12.2010 N 1076, с изм., внесенными Постановлениями Правительства РФ от 21.12.2009 N 1035, от 22.12.2010 N 1088) ПАСПОРТ ФЕДЕРАЛЬНОЙ ЦЕЛЕВОЙ ПРОГРАММЫ РАЗВИТИЕ ТРАНСПОРТНОЙ СИСТЕМЫ РОССИИ (2010 - 2015 ГОДЫ)...»

«К ВОПРОСУ О ТРАНСПОРТИРОВКЕ КАСПИЙСКОЙ НЕФТИ Проблемам освоения ресурсов углеводородов Каспийского моря в последнее время уделяется значительное внимание. Каспийская тематика не сходит со страниц прессы, как общеделовой, так и специальной нефтегазовой - особенно нацеленной на инвестиционно-нефтяную ее часть аудитории. На Западе специализированная нефтяная пресса (Oil & Gas Journal, World Oil, Petroleum Economist, International Petroleum Encyclopedia и др.) стала уделять пристальное внимание...»

«Приложения к методике определения запаздывания ответной реакции систем авиационного тренажера. Шибаев В.М. Аполлонов Д.В. Еркин И.Н. ПРИЛОЖЕНИЕ стр. 1 из 22 Приложения к Методике определения запаздывания ответной реакции систем авиационного тренажера: Методы определения транспортной задержки в соответствии с требованиями международных нормативных документов Приложение 1. IATA FSTD edition 7-v0 ТРЕБОВАНИЯ К ДАННЫМ, НЕОБХОДИМЫМ ПРИ ПРОЕКТИРОВАНИИ АВИАЦИОННЫХ ТРЕНАЖЕРОВ(АТ), А ТАКЖЕ ПРИ...»






 
© 2013 www.knigi.konflib.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.