- Опубликовано:
Международный Журнал компьютерных и информационных наук том 5 , страницы 9–31 (1976) Цитируйте эту статью
-
487 доступов
-
11 цитат
-
Сведения о показателях
Аннотация
Многие проблемные ситуации в компьютерных системах можно анализировать с помощью моделей, основанных на ориентированных графах. Вершины графа представляют состояния системы, а направленные дуги представляют переходы между этими состояниями. Этот документ состоит из двух частей. Первый знакомит с концепциями ориентированных графов и их представлений на компьютерах, а также представляет некоторые основные проблемы и алгоритмы. Во второй части исследуется применение теории графов к различным областям компьютерных систем.
Это предварительный просмотр содержимого подписки, авторизуйтесь, чтобы проверить доступ.
Параметры доступа
Купить отдельную статью
Мгновенный доступ к полной версии PDF статьи.
34,95 €
Расчет налога будет завершен во время оформления заказа.
Подписка на журнал
Немедленный онлайн-доступ ко всем выпускам с 2019 года. Подписка будет автоматически продлеваться ежегодно.
111,21 €
Расчет налога будет завершен во время оформления заказа.
Взять напрокат эту статью через DeepDyve.
Ссылки
- 1.
F. Харари, Теория графов (Addison-Wesley, 1969).
- 2.
С. Бердж, Теория графов и их приложения , (Wiley, New York, 1962).
Google Scholar
- 3.
О. Ore, Графики и их использование (Random House, Нью-Йорк, 1963).
Google Scholar
- 4.
Р. Дж. Бусакер и Т.Л. Саати, Конечные графы и сети: Введение в приложения (McGraw-Hill, New York, 1965).
Google Scholar
- 5.
А. В. Ахо, Дж. Э. Хопкрофт и Дж. Д. Уллман, Дизайн и анализ компьютерных алгоритмов (Addison-Wesley, 1974).
- 6.
P. Д. Стигалл и О. Тасар, «Обзор ориентированных графов применительно к компьютерам», Computer 7 (10): 39–47 (1974). .
Google Scholar
- 7.
S. Уоршалл, “Теорема о булевых матрицах”, J. ACM 9 (1): 11–12 (1962).
Google Scholar
- 8.
Дж. Дж. Бейкер, «Замечание об умножении булевых матриц», Commun. ACM 5 (2): 102 (1962)..
Google Scholar
- 9.
H. С. Уоррен младший, «Модификация алгоритма Уоршолла для транзитивного замыкания бинарных отношений», Commun. ACM 18 (4): 218–220 (1975).
Google Scholar
- 10.
LE Торелли, «Алгоритм вычисления всех путей в графе», BIT 6 : 347–349 (1966).
Google Scholar
- 11.
Стр. Пурдом, «Алгоритм транзитивного замыкания», BIT 10 (l): 76–94 (1970).
Google Ученый
- 12.
I. Манро, “Эффективное определение транзитивного замыкания ориентированного графа”, Inf. Proc. Буквы 1 : 56–58 (1971).
Google Scholar
- 13.
V. Штрассен, «Гауссово исключение не является оптимальным», Numerische Mathematik 13 : 354–356 (1969).
Google Scholar
- 14.
Дж. К. Тирнан, «Эффективный алгоритм поиска для поиска элементарных схем графа», Commun. ACM 13 (12): 722–726 (1970).
Google Scholar
- 15.
H. Вайнблатт, “Новый алгоритм поиска простых циклов конечного ориентированного графа”, J. ACM 19 (l): 43–56 (1972).
Google Scholar
- 16.
Р. Э. Тарьян, «Перечисление элементарных схем ориентированного графа», SIAM J. Comp. 2 (3; сентябрь): 211–216 ( 1973).
Google Scholar
- 17.
C. В. Рамамурти, «Анализ графов по соображениям связности», J. ACM 13 (2 апреля): 211–222 (1966).
Google Scholar
- 18.
Р. Э. Тарьян, «Поиск в глубину и алгоритмы линейного графа», SIAM J. Comp. 1 (2; июнь): 146–160 (1972). .
Google Scholar
- 19.
C. П. Эрнест, К. Г. Балке и Дж. Андерсон, «Анализ графов путем упорядочения узлов», J. ACM 19 (1): 23–42 (1972).
Google Scholar
- 20.
D. Ф. Мартин и Г. Эстрин, «Модели вычислений и систем — оценка вероятностей вершин в графовых моделях вычислений», J. ACM 14 (2; апрель): 281–299 (1967).
Google Scholar
- 21.
D. Ф. Мартин и Г. Эстрин, «Модели вычислений и систем — преобразования циклического графа в ациклический», IEEE Trans, on Electronic Computers EC-16 ( Февраль): 70–79 (1967).
Google Scholar
- 22.
D. Ф. Мартин и Г. Эстрин, «Эксперименты на моделях вычислений и систем», IEEE Trans, on Electronic Computers EC-16 (февраль): 59 –69 (1967).
Google Scholar
- 23.
D. Ф. Мартин и Г.. Эстрин, «Вычисления длины пути на графовых моделях вычислений», IEEE Trans, on Computers C-18 (июнь): 530–536 (1969).
Google Scholar
- 24.
Дж. Л. Баер, «Обзор некоторых теоретических аспектов многопроцессорной обработки», Computing Surveys 5 (1; March): 31–80 (1973).
Google Scholar
- 25.
Дж. Л. Бэр и Дж. Эстрин, «Границы максимального параллелизма в модели вычислений на билогическом графе», IEEE Trans, on Computers C-18 (11 ): 1012–1014 (1969).
Google Scholar
- 26.
Дж. Л. Баер, Д. П. Бове и Г. Эстрин, «Законность и другие свойства графовых моделей вычислений», J. ACM 17 (3; июль): 543–554 (1970).
Google Scholar
- 27.
Дж. Л. Бэр и Г. Эстрин, «Априорное планирование моделей вычислений на билогическом графе», в Project Planning by Network Analysis (North-Holland, 1969).
- 28.
Дж. Л. Баер и Э. К. Рассел, «Подготовка и оценка компьютерных программ для систем параллельной обработки», В Параллельные процессорные системы, технологии и приложения , LC Hobbs et al. , ред. (Spartan Books, New York 1970), стр. 375–415.
Google Scholar
- 29.
Дж. Л. Баер, «Графические модели вычислений», Отчет отдела электротехники Калифорнийского университета в Лос-Анджелесе 6846 (1968).
- 30.
Р. М. Карп и Р. А. Миллер, «Свойства модели для параллельных вычислений: детерминированность, завершение, организация очереди», SIAM J. Appl. Математика. 14 (11): 1390–1411 (1966).
Google Scholar
- 31.
Y. Э. Чен и Д. Л. Эпли, «Требования к памяти в многопроцессорной среде», J. ACM 19 (1): 57–69 (1972).
Google Scholar
- 32.
Р. Проссер Т. Применение булевых матриц к анализу блок-схем// Proc. Eeastern Joint Computer Conf. (1960), Vol. 16, pp. 133–138.
Google Scholar
- 33.
A . Шурманн, «Применение графов к анализу распределения циклов в программе», Информация и управление 7 (3): 275–282 (1964). ).
Google Scholar
- 34.
А. Т. Берцтисс, «Заметка о сегментации компьютерных программ», Информация и управление 12 (1): 21–22 (1968).
Google Scholar
- 35.
C. В. Рамамурти, «Аналитический дизайн системы динамического прогнозирования и сегментации программ для многопрограммных компьютеров», в Proc. 21-й ACM Nat. Conf. (1966), pp. 229–239.
- 36.
Т. К. Лоу, «Анализ моделей логических программ для сред с разделением времени и разбиением по страницам», Commun. ACM 12 (4): 199–205 (1969).
Google Scholar
- 37.
Т. C. Лоу, «Автоматическая сегментация циклических программных структур на основе возможности подключения и синхронизации процессора», Commun. ACM 13 (l): 3–6 (1970).
Google Scholar
- 38.
К. Саттли и Р. Миллстайн, «Комментарии к статье Лоу», Commun. ACM 13 (7): 450–451 (1970).
Google Scholar
- 39.
E. W. Ver Hoef, «Автоматическая сегментация программ на основе логической связи», в Proc. AFIPS SJCC (1971), Vol. 38 , pp. 491–495.
Google Scholar
- 40.
Дж. Л. Бэр и Р. Кауги, «Сегментация и оптимизация программ на основе анализа циклической структуры», в Proc. AFIPS SJCC (1972), Vol. 40 , pp. 23–36.
Google Scholar
- 41.
B. В. Керниган, “Оптимальные последовательные разбиения графов”, J. ACM 18 (1): 34–40 (1971).
Google Scholar
- 42.
С. Эрнест, «Некоторые темы по оптимизации кода», J. ACM 21 (1): 76–102 (1974).
Google Scholar
- 43.
Дж. Кок и Р. Э. Миллер, «Некоторые методы анализа для оптимизации компьютерных программ», в Proc. 2-я Международная конференция по системным наукам, Гавайи (1969).
- 44.
Дж. Кок и Дж. Т. Шварц, «Языки программирования и их компиляторы», Предварительные заметки, Courant Inst, of Math. Наук, Нью-Йоркский университет, Нью-Йорк (1970).
Google Scholar
- 45.
К. Кеннеди, «Алгоритм анализа глобального потока», Int. J. Comp. Математика. 3 (1): 5–15 (1971).
Google Scholar
- 46.
F. Э. Аллен, «Оптимизация программ», в Annual Review in Automatic Programming (1969), Vol. 5.
- 47.
F. Э. Аллен, «Анализ потока управления», ACM SIGPLAN Notices 5 , 7 (июль 1970 г.), стр. 1–19.
Google Scholar
- 48.
F. Э. Чужой, «Основа для оптимизации программы», в Proc. Конгресс ИФИП 1971 г. (Северная Голландия).
- 49.
М. С. Хехт, Дж. Д. Ульман, “Характеризации приводимых потоковых графов”, J. ACM 21 (3; июль): 367–375 (1974).
Google Scholar
- 50.
Р. Э. Тарьян, “Проверка сводимости потокового графа”, в Proc. 5-й ежегодный симпозиум ACM. по теории вычислений , стр. 96–107.
- 51.
M. S. Hecht и JD Ullman, «Сводимость потокового графа», SIAM J. Comp. 1 (2; июнь): 188–202 (1972).
Google Scholar
- 52.
Дж. Кок, «Глобальное исключение общих подвыражений», ACM SIGPLAN Notices, 5, 7 (июль 1970), стр. 20–24.
Google Scholar
- 53.
Дж. Д. Ульман, «Быстрые алгоритмы исключения общих подвыражений», Acta Informatica 2 (3; декабрь): 191–213 (1973)..
Google Scholar
- 54.
D. Х. Р. Хакстейбл, «О написании оптимизирующего транслятора для АЛГОЛА 60», в Introduction to System Programming , P. Wegner, ed. (Academic Press, 1964), стр. 137–155.
- 55.
E. Н. Хокинс и Д. Х. Р. Хакстейбл, «Схема многопроходного перевода для АЛГОЛА 60», в Annual Review in Automatic Programming (1962), Vol. 3. С. 163–205.
Google Scholar
- 56.
E . С. Лоури и К. В. Медлок, «Оптимизация объектного кода», Commun. ACM 12 (1): 13–22 (1969).
Google Scholar
- 57.
Р. Л. Клейр и К. В. Рамамурти, «Стратегии оптимизации для микропрограмм», Trans. IEEE на компьютерах C-20 (7): 783–794 (1971).
Google Scholar
- 58.
С. Рамамурти В. и Клейр Р. Л., «Обзор методов оптимизации микропрограмм», в Proc. 3-й ежегодный семинар по микропрограммированию, Буффало, Нью-Йорк (1970).
- 59.
Дж. Л. Шварцфитер и П. Э. Лауэр, «Нахождение элементарных циклов ориентированного графа в O (N + M) за цикл», Tech. Представитель № 60, Лаборатория вычислительной техники. Univ. Ньюкасл-апон-Тайн, Англия (май 1974 г.).
Google Scholar
- 60. С. В. Рамамурти и М. Дж. Гонсалес, «Обзор методов распознавания параллельных обрабатываемых потоков в компьютерных программах», в Proc. AFIPS FJCC (1969), Vol. 35, стр. 1–15.
Google Scholar
- 61.
C. В. Рамамурти и М. Дж. Гонсалес, «Распознавание и представление параллельных обрабатываемых потоков в компьютерных программах II (параллелизм задачи/процесса)», в Proc. 24-й ACM Nat. Conf. (1969), pp. 387–397.
- 62.
E. К. Рассел, «Автоматический анализ программ», Ph.D. Диссертация, кафедра электр. Eng., UCLA (1969).
- 63.
Дж. М. С. Симоэс-Перейра, «О булевом матричном уравнении M ′ = U i = 1 ∞ M ′», Дж. ACM 12 (3; июль): 376–382 (1965).
Google Scholar
- 64.
L. У. Джексон и С. Дасгупта, «Идентификация параллельных микроопераций», Inf. Proc. Письма 2 : 180–184 (1974).
Google Scholar
- 65.
Р. М. Карп, «Заметка о применении теории графов к программированию цифровых компьютеров», Информация и управление 3 (6): 179–190 (1960). ).
Google Scholar
- 66.
C. Рамамурти В. Дискретный марковский анализ компьютерных программ// Proc. 20-й ACM Nat. Conf. (1965), pp. 386–392.
- 67.
J. Д. Фоли, «Марковская модель исполнительной системы Мичиганского университета», Commun. ACM 10 (9): 584–589 (1967).
Google Scholar
- 68.
W. С. Боуи, «К распределенной архитектуре для OS/360», Ph.. Докторская диссертация, кафедра прикладного анализа и компьютерных наук, Univ. Ватерлоо, Ватерлоо, Онтарио, Канада (1974).
Google Scholar
- 69.
W. С. Боуи, Дж. Г. Линдерс и У. Раштон, «Программа отслеживания трассировки для OS/360», в Proc. Canadian Inf. Proc. Soc. Конф. Регина, Саскачеван, Канада (июнь 1975 г.) .
- 70.
М. Дж. Гонсалес и К.В. Рамамурти, «Параллельное выполнение задач в децентрализованной системе», IEEE Trans, on Computers C-21 (12): 1310–1322 (1972).
Google Scholar
- 71.
Дж. М. Фили, «Монитор производительности компьютера и марковский анализ для оценки многопроцессорной системы», в Statistical Computer Performance Evaluation , W. Frieberger, ed. (Academic Press, 1972), стр. 165–225.
- 72.
Т. К. Лоу, «Анализ модели информационной системы со штрафами за передачу», IEEE Trans, on Computers C-22 (5): 469–480 ( 1973).
Google Scholar
- 73.
Р. К. Холт, «Некоторые тупиковые свойства компьютерных систем», Computing Surveys 4 (3; сентябрь): 179–196 (1972).
Google Scholar
- 74.
Дж. Э. Мерфи, «Распределение ресурсов с обнаружением блокировки в многозадачной системе», в Proc. AFIPS FJCC (1968), том 33 , часть 2, стр. 1169–1176.
Google Scholar
- 75.
стр. Г. Хебалкар, “Графическая модель для анализа предотвращения тупиковых ситуаций в системах с параллельными вычислениями”, в Proc. Конгресс ИФИП, 1971 , стр. 498–503.
- 76.
E. Дж. Коффман, MJ Элфик и А. Шошани, «Системные тупики», Computing Surveys 3 (2; июнь): 67–78 (1971). .
Google Scholar
- 77.
К. М. Чанди и К.В. Рамамурти, «Стратегии отката и восстановления для компьютерных программ», IEEE Trans, on Computers C-21 (6): 546–556 (1972).
Google Scholar
- 78.
W. Майеда и К.В. Рамамурти, «Критерии различимости ориентированных графов и их применение в компьютерной диагностике — I», IEEE Trans, по теории цепей CT-16 (ноябрь ): 448–454 (1969).
Google Scholar
- 79.
С. Рамамурти В. Структурная теория машинной диагностики// Proc. AFIPS SJCC (1967), Vol. 30 , pp. 743–756.
Google Scholar
- 80.
C. В. Рамамурти и Л. К. Чанг, «Системное моделирование и процедуры тестирования для микродиагностики», IEEE Trans, on Computers C-21 (11): 1169–1183 (1972).
Google Scholar
- 81.
С. В. Рамамурти и Л. К. Чанг, «Системная сегментация для параллельной диагностики компьютеров», IEEE Trans, on Computers C-20 (3): 261– 270 (1971).
Google Scholar
Загрузить ссылки
Информация об авторе
-
Уильям С. Боуи
Нынешний адрес: факультет математики, университет штата Виктория, Виктория, Британская Колумбия, Канада
Филиалы
-
Департамент вычислительной техники и Информационные науки, Университет Гвельфа, Гвельф, Онтарио, Канада
Уильям С. Боуи
- Уильям С. Боуи
Просмотреть публикации автора
Вы также можете выполнить поиск этого автора в PubMed Google Scholar
Права и разрешения
Перепечатки и разрешения
Об этой статье
Цитируйте эту статью
Боуи, WS Приложения теории графов в компьютерных системах. Международный журнал компьютерных и информационных наук 5, 9–31 (1976). https://doi.org/10.1007/BF00991069
Скачать ссылку
-
Получено:
-
Исправлено:
-
Дата выпуска:
-
DOI : https://doi.org/10.1007/BF00991069
Ключевые слова
- Направленный граф
- компьютерные системы
- модели
- приложения
- теория графов