Лекция по РА от 24.03.20

[admin]

Тема лекции "Алгоритмы обхода"

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

- определение алгоритма обхода (Тель, стр. 215)
- маркер обхода
- алгоритм f-обхода
Алгоритмы:
а) клик
б) обход торов
в) обход гиперкубов
г) обход связных сетей

Литература к лекции:
1. Тель

Интернет-источники:
- https://mydocx.ru/6-112263.html
- https://www.intuit.ru/studies/courses/1 ... cture/6163

Контрольные вопросы:
- что такое торический граф?
- какие сети являются связными?
- как передается маркер в алгоритмах а)-г) ?
- почему алгоритм Тарри является алгоритмом обхода?
- какова сложность по времени алгоритмов а)-г) ?

[Mag_PI]

Лабораторки согласно индивидуального задания?