Освоение методов анализа трудоемкости вычислительных алгоритмов. Оценка сложности алгоритма в битах, байтах, количестве символов определенного языка. Количество вычислительной работы, требуемой для его реализации. Операции, выполняемые при одном прогоне.
Аннотация к работе
ЛАБОРАТОРНАЯ РАБОТА № 1Для определения среднего числа обращений ni к оператору Vi (i=1,2,...,k-1) обычно делаются следующие допущения: - вероятность выполнения после оператора Vi оператора Vj равна Pij и является постоянной величиной; вероятность Pij зависит только от оператора Vi, но никак не связана со способом попадания в оператор Vj, т.е. не зависит от предыстории вычислительного процесса; Сетевой подход удобен для анализа вручную и позволяет вычислять среднюю, минимальную и максимальную трудоемкость алгоритма на графах, не содержащих циклы. Для оценки максимальной и минимальной трудоемкости алгоритма необходимо перебрать все возможные пути, ведущие из начальной вершины графа алгоритма в конечную, и выбрать из них пути, дающие максимальную и минимальную трудоемкость. Для упрощения примем, что все операторы имеют трудоемкость, равную 1000 процессорных операций.Расписание двухфазной модели без учета ограничения со стороны ОЗУ. Расписание двухфазной модели с учетом ограничений со стороны ОЗУ.
Список литературы
1. Теория расписаний и вычислительные машины / Под редакцией Коффмана Э.Г. - М.: Наука, 1984. - 335 с.