Приложения теории графов в компьютерных системах

  • Опубликовано:

Международный Журнал компьютерных и информационных наук том 5 , страницы 9–31 (1976) Цитируйте эту статью

  • 487 доступов

  • 11 цитат

  • Сведения о показателях

Аннотация

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

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

Параметры доступа

Купить отдельную статью

Мгновенный доступ к полной версии PDF статьи.

34,95 €

Расчет налога будет завершен во время оформления заказа.

Подписка на журнал

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

111,21 €

Расчет налога будет завершен во время оформления заказа.

Взять напрокат эту статью через DeepDyve.

Ссылки

  1. 1.

    F. Харари, Теория графов (Addison-Wesley, 1969).

  2. 2.

    С. Бердж, Теория графов и их приложения , (Wiley, New York, 1962).

    Google Scholar

  3. 3.

    О. Ore, Графики и их использование (Random House, Нью-Йорк, 1963).

    Google Scholar

  4. 4.

    Р. Дж. Бусакер и Т.Л. Саати, Конечные графы и сети: Введение в приложения (McGraw-Hill, New York, 1965).

    Google Scholar

  5. 5.

    А. В. Ахо, Дж. Э. Хопкрофт и Дж. Д. Уллман, Дизайн и анализ компьютерных алгоритмов (Addison-Wesley, 1974).

  6. 6.

    P. Д. Стигалл и О. Тасар, «Обзор ориентированных графов применительно к компьютерам», Computer 7 (10): 39–47 (1974). .

    Google Scholar

  7. 7.

    S. Уоршалл, “Теорема о булевых матрицах”, J. ACM 9 (1): 11–12 (1962).

    Google Scholar

  8. 8.

    Дж. Дж. Бейкер, «Замечание об умножении булевых матриц», Commun. ACM 5 (2): 102 (1962)..

    Google Scholar

  9. 9.

    H. С. Уоррен младший, «Модификация алгоритма Уоршолла для транзитивного замыкания бинарных отношений», Commun. ACM 18 (4): 218–220 (1975).

    Google Scholar

  10. 10.

    LE Торелли, «Алгоритм вычисления всех путей в графе», BIT 6 : 347–349 (1966).

    Google Scholar

  11. 11.

    Стр. Пурдом, «Алгоритм транзитивного замыкания», BIT 10 (l): 76–94 (1970).

    Google Ученый

  12. 12.

    I. Манро, “Эффективное определение транзитивного замыкания ориентированного графа”, Inf. Proc. Буквы 1 : 56–58 (1971).

    Google Scholar

  13. 13.

    V. Штрассен, «Гауссово исключение не является оптимальным», Numerische Mathematik 13 : 354–356 (1969).

    Google Scholar

  14. 14.

    Дж. К. Тирнан, «Эффективный алгоритм поиска для поиска элементарных схем графа», Commun. ACM 13 (12): 722–726 (1970).

    Google Scholar

  15. 15.

    H. Вайнблатт, “Новый алгоритм поиска простых циклов конечного ориентированного графа”, J. ACM 19 (l): 43–56 (1972).

    Google Scholar

  16. 16.

    Р. Э. Тарьян, «Перечисление элементарных схем ориентированного графа», SIAM J. Comp. 2 (3; сентябрь): 211–216 ( 1973).

    Google Scholar

  17. 17.

    C. В. Рамамурти, «Анализ графов по соображениям связности», J. ACM 13 (2 апреля): 211–222 (1966).

    Google Scholar

  18. 18.

    Р. Э. Тарьян, «Поиск в глубину и алгоритмы линейного графа», SIAM J. Comp. 1 (2; июнь): 146–160 (1972). .

    Google Scholar

  19. 19.

    C. П. Эрнест, К. Г. Балке и Дж. Андерсон, «Анализ графов путем упорядочения узлов», J. ACM 19 (1): 23–42 (1972).

    Google Scholar

  20. 20.

    D. Ф. Мартин и Г. Эстрин, «Модели вычислений и систем — оценка вероятностей вершин в графовых моделях вычислений», J. ACM 14 (2; апрель): 281–299 (1967).

    Google Scholar

  21. 21.

    D. Ф. Мартин и Г. Эстрин, «Модели вычислений и систем — преобразования циклического графа в ациклический», IEEE Trans, on Electronic Computers EC-16 ( Февраль): 70–79 (1967).

    Google Scholar

  22. 22.

    D. Ф. Мартин и Г. Эстрин, «Эксперименты на моделях вычислений и систем», IEEE Trans, on Electronic Computers EC-16 (февраль): 59 –69 (1967).

    Google Scholar

  23. 23.

    D. Ф. Мартин и Г.. Эстрин, «Вычисления длины пути на графовых моделях вычислений», IEEE Trans, on Computers C-18 (июнь): 530–536 (1969).

    Google Scholar

  24. 24.

    Дж. Л. Баер, «Обзор некоторых теоретических аспектов многопроцессорной обработки», Computing Surveys 5 (1; March): 31–80 (1973).

    Google Scholar

  25. 25.

    Дж. Л. Бэр и Дж. Эстрин, «Границы максимального параллелизма в модели вычислений на билогическом графе», IEEE Trans, on Computers C-18 (11 ): 1012–1014 (1969).

    Google Scholar

  26. 26.

    Дж. Л. Баер, Д. П. Бове и Г. Эстрин, «Законность и другие свойства графовых моделей вычислений», J. ACM 17 (3; июль): 543–554 (1970).

    Google Scholar

  27. 27.

    Дж. Л. Бэр и Г. Эстрин, «Априорное планирование моделей вычислений на билогическом графе», в Project Planning by Network Analysis (North-Holland, 1969).

  28. 28.

    Дж. Л. Баер и Э. К. Рассел, «Подготовка и оценка компьютерных программ для систем параллельной обработки», В Параллельные процессорные системы, технологии и приложения , LC Hobbs et al. , ред. (Spartan Books, New York 1970), стр. 375–415.

    Google Scholar

  29. 29.

    Дж. Л. Баер, «Графические модели вычислений», Отчет отдела электротехники Калифорнийского университета в Лос-Анджелесе 6846 (1968).

  30. 30.

    Р. М. Карп и Р. А. Миллер, «Свойства модели для параллельных вычислений: детерминированность, завершение, организация очереди», SIAM J. Appl. Математика. 14 (11): 1390–1411 (1966).

    Google Scholar

  31. 31.

    Y. Э. Чен и Д. Л. Эпли, «Требования к памяти в многопроцессорной среде», J. ACM 19 (1): 57–69 (1972).

    Google Scholar

  32. 32.

    Р. Проссер Т. Применение булевых матриц к анализу блок-схем// Proc. Eeastern Joint Computer Conf. (1960), Vol. 16, pp. 133–138.

    Google Scholar

  33. 33.

    A . Шурманн, «Применение графов к анализу распределения циклов в программе», Информация и управление 7 (3): 275–282 (1964). ).

    Google Scholar

  34. 34.

    А. Т. Берцтисс, «Заметка о сегментации компьютерных программ», Информация и управление 12 (1): 21–22 (1968).

    Google Scholar

  35. 35.

    C. В. Рамамурти, «Аналитический дизайн системы динамического прогнозирования и сегментации программ для многопрограммных компьютеров», в Proc. 21-й ACM Nat. Conf. (1966), pp. 229–239.

  36. 36.

    Т. К. Лоу, «Анализ моделей логических программ для сред с разделением времени и разбиением по страницам», Commun. ACM 12 (4): 199–205 (1969).

    Google Scholar

  37. 37.

    Т. C. Лоу, «Автоматическая сегментация циклических программных структур на основе возможности подключения и синхронизации процессора», Commun. ACM 13 (l): 3–6 (1970).

    Google Scholar

  38. 38.

    К. Саттли и Р. Миллстайн, «Комментарии к статье Лоу», Commun. ACM 13 (7): 450–451 (1970).

    Google Scholar

  39. 39.

    E. W. Ver Hoef, «Автоматическая сегментация программ на основе логической связи», в Proc. AFIPS SJCC (1971), Vol. 38 , pp. 491–495.

    Google Scholar

  40. 40.

    Дж. Л. Бэр и Р. Кауги, «Сегментация и оптимизация программ на основе анализа циклической структуры», в Proc. AFIPS SJCC (1972), Vol. 40 , pp. 23–36.

    Google Scholar

  41. 41.

    B. В. Керниган, “Оптимальные последовательные разбиения графов”, J. ACM 18 (1): 34–40 (1971).

    Google Scholar

  42. 42.

    С. Эрнест, «Некоторые темы по оптимизации кода», J. ACM 21 (1): 76–102 (1974).

    Google Scholar

  43. 43.

    Дж. Кок и Р. Э. Миллер, «Некоторые методы анализа для оптимизации компьютерных программ», в Proc. 2-я Международная конференция по системным наукам, Гавайи (1969).

  44. 44.

    Дж. Кок и Дж. Т. Шварц, «Языки программирования и их компиляторы», Предварительные заметки, Courant Inst, of Math. Наук, Нью-Йоркский университет, Нью-Йорк (1970).

    Google Scholar

  45. 45.

    К. Кеннеди, «Алгоритм анализа глобального потока», Int. J. Comp. Математика. 3 (1): 5–15 (1971).

    Google Scholar

  46. 46.

    F. Э. Аллен, «Оптимизация программ», в Annual Review in Automatic Programming (1969), Vol. 5.

  47. 47.

    F. Э. Аллен, «Анализ потока управления», ACM SIGPLAN Notices 5 , 7 (июль 1970 г.), стр. 1–19.

    Google Scholar

  48. 48.

    F. Э. Чужой, «Основа для оптимизации программы», в Proc. Конгресс ИФИП 1971 г. (Северная Голландия).

  49. 49.

    М. С. Хехт, Дж. Д. Ульман, “Характеризации приводимых потоковых графов”, J. ACM 21 (3; июль): 367–375 (1974).

    Google Scholar

  50. 50.

    Р. Э. Тарьян, “Проверка сводимости потокового графа”, в Proc. 5-й ежегодный симпозиум ACM. по теории вычислений , стр. 96–107.

  51. 51.

    M. S. Hecht и JD Ullman, «Сводимость потокового графа», SIAM J. Comp. 1 (2; июнь): 188–202 (1972).

    Google Scholar

  52. 52.

    Дж. Кок, «Глобальное исключение общих подвыражений», ACM SIGPLAN Notices, 5, 7 (июль 1970), стр. 20–24.

    Google Scholar

  53. 53.

    Дж. Д. Ульман, «Быстрые алгоритмы исключения общих подвыражений», Acta Informatica 2 (3; декабрь): 191–213 (1973)..

    Google Scholar

  54. 54.

    D. Х. Р. Хакстейбл, «О написании оптимизирующего транслятора для АЛГОЛА 60», в Introduction to System Programming , P. Wegner, ed. (Academic Press, 1964), стр. 137–155.

  55. 55.

    E. Н. Хокинс и Д. Х. Р. Хакстейбл, «Схема многопроходного перевода для АЛГОЛА 60», в Annual Review in Automatic Programming (1962), Vol. 3. С. 163–205.

    Google Scholar

  56. 56.

    E . С. Лоури и К. В. Медлок, «Оптимизация объектного кода», Commun. ACM 12 (1): 13–22 (1969).

    Google Scholar

  57. 57.

    Р. Л. Клейр и К. В. Рамамурти, «Стратегии оптимизации для микропрограмм», Trans. IEEE на компьютерах C-20 (7): 783–794 (1971).

    Google Scholar

  58. 58.

    С. Рамамурти В. и Клейр Р. Л., «Обзор методов оптимизации микропрограмм», в Proc. 3-й ежегодный семинар по микропрограммированию, Буффало, Нью-Йорк (1970).

  59. 59.

    Дж. Л. Шварцфитер и П. Э. Лауэр, «Нахождение элементарных циклов ориентированного графа в O (N + M) за цикл», Tech. Представитель № 60, Лаборатория вычислительной техники. Univ. Ньюкасл-апон-Тайн, Англия (май 1974 г.).

    Google Scholar

  60. 60. С. В. Рамамурти и М. Дж. Гонсалес, «Обзор методов распознавания параллельных обрабатываемых потоков в компьютерных программах», в Proc. AFIPS FJCC (1969), Vol. 35, стр. 1–15.

    Google Scholar

  61. 61.

    C. В. Рамамурти и М. Дж. Гонсалес, «Распознавание и представление параллельных обрабатываемых потоков в компьютерных программах II (параллелизм задачи/процесса)», в Proc. 24-й ACM Nat. Conf. (1969), pp. 387–397.

  62. 62.

    E. К. Рассел, «Автоматический анализ программ», Ph.D. Диссертация, кафедра электр. Eng., UCLA (1969).

  63. 63.

    Дж. М. С. Симоэс-Перейра, «О булевом матричном уравнении M ′ = U i = 1 M ′», Дж. ACM 12 (3; июль): 376–382 (1965).

    Google Scholar

  64. 64.

    L. У. Джексон и С. Дасгупта, «Идентификация параллельных микроопераций», Inf. Proc. Письма 2 : 180–184 (1974).

    Google Scholar

  65. 65.

    Р. М. Карп, «Заметка о применении теории графов к программированию цифровых компьютеров», Информация и управление 3 (6): 179–190 (1960). ).

    Google Scholar

  66. 66.

    C. Рамамурти В. Дискретный марковский анализ компьютерных программ// Proc. 20-й ACM Nat. Conf. (1965), pp. 386–392.

  67. 67.

    J. Д. Фоли, «Марковская модель исполнительной системы Мичиганского университета», Commun. ACM 10 (9): 584–589 (1967).

    Google Scholar

  68. 68.

    W. С. Боуи, «К распределенной архитектуре для OS/360», Ph.. Докторская диссертация, кафедра прикладного анализа и компьютерных наук, Univ. Ватерлоо, Ватерлоо, Онтарио, Канада (1974).

    Google Scholar

  69. 69.

    W. С. Боуи, Дж. Г. Линдерс и У. Раштон, «Программа отслеживания трассировки для OS/360», в Proc. Canadian Inf. Proc. Soc. Конф. Регина, Саскачеван, Канада (июнь 1975 г.) .

  70. 70.

    М. Дж. Гонсалес и К.В. Рамамурти, «Параллельное выполнение задач в децентрализованной системе», IEEE Trans, on Computers C-21 (12): 1310–1322 (1972).

    Google Scholar

  71. 71.

    Дж. М. Фили, «Монитор производительности компьютера и марковский анализ для оценки многопроцессорной системы», в Statistical Computer Performance Evaluation , W. Frieberger, ed. (Academic Press, 1972), стр. 165–225.

  72. 72.

    Т. К. Лоу, «Анализ модели информационной системы со штрафами за передачу», IEEE Trans, on Computers C-22 (5): 469–480 ( 1973).

    Google Scholar

  73. 73.

    Р. К. Холт, «Некоторые тупиковые свойства компьютерных систем», Computing Surveys 4 (3; сентябрь): 179–196 (1972).

    Google Scholar

  74. 74.

    Дж. Э. Мерфи, «Распределение ресурсов с обнаружением блокировки в многозадачной системе», в Proc. AFIPS FJCC (1968), том 33 , часть 2, стр. 1169–1176.

    Google Scholar

  75. 75.

    стр. Г. Хебалкар, “Графическая модель для анализа предотвращения тупиковых ситуаций в системах с параллельными вычислениями”, в Proc. Конгресс ИФИП, 1971 , стр. 498–503.

  76. 76.

    E. Дж. Коффман, MJ Элфик и А. Шошани, «Системные тупики», Computing Surveys 3 (2; июнь): 67–78 (1971). .

    Google Scholar

  77. 77.

    К. М. Чанди и К.В. Рамамурти, «Стратегии отката и восстановления для компьютерных программ», IEEE Trans, on Computers C-21 (6): 546–556 (1972).

    Google Scholar

  78. 78.

    W. Майеда и К.В. Рамамурти, «Критерии различимости ориентированных графов и их применение в компьютерной диагностике — I», IEEE Trans, по теории цепей CT-16 (ноябрь ): 448–454 (1969).

    Google Scholar

  79. 79.

    С. Рамамурти В. Структурная теория машинной диагностики// Proc. AFIPS SJCC (1967), Vol. 30 , pp. 743–756.

    Google Scholar

  80. 80.

    C. В. Рамамурти и Л. К. Чанг, «Системное моделирование и процедуры тестирования для микродиагностики», IEEE Trans, on Computers C-21 (11): 1169–1183 (1972).

    Google Scholar

  81. 81.

    С. В. Рамамурти и Л. К. Чанг, «Системная сегментация для параллельной диагностики компьютеров», IEEE Trans, on Computers C-20 (3): 261– 270 (1971).

    Google Scholar

Загрузить ссылки

Информация об авторе

Заметки об авторе
  1. Уильям С. Боуи

    Нынешний адрес: факультет математики, университет штата Виктория, Виктория, Британская Колумбия, Канада

Филиалы

  1. Департамент вычислительной техники и Информационные науки, Университет Гвельфа, Гвельф, Онтарио, Канада

    Уильям С. Боуи

Авторы
  1. Уильям С. Боуи
    Просмотреть публикации автора

    Вы также можете выполнить поиск этого автора в PubMed Google Scholar

Права и разрешения

Перепечатки и разрешения

Об этой статье

Цитируйте эту статью

Боуи, WS Приложения теории графов в компьютерных системах. Международный журнал компьютерных и информационных наук 5, 9–31 (1976). https://doi.org/10.1007/BF00991069

Скачать ссылку

  • Получено:

  • Исправлено:

  • Дата выпуска:

  • DOI : https://doi.org/10.1007/BF00991069

Ключевые слова

  • Направленный граф
  • компьютерные системы
  • модели
  • приложения
  • теория графов
Оцените статью
Botgadget.ru
Добавить комментарий