22. Структура данных в эвм

Любая информация, обрабатываемая в ЭВМ, должна быть представлена двоичными цифрами {0,1}, т.е. должна быть закодирована комбинацией этих цифр. Различные виды информации (числа, тексты, графика, звук) имеют свой правила кодирования. Коды отдельных значений, относящиеся к различным видам информации, могут совпадать.( все в матрицах (смежности и инцедентности))

23. Способы предст графа в эвм:

-матрица смежности – матрица инцидентности – список пар в соответствии с ребрами ( см след вопр)

24. Матрицы смеж. И инцидент. Список рёбер — это тип представления графа в памяти компьютерной программы, подразумевающий, что каждое ребро представляется двумя числами — номерами вершин этого ребра. Список рёбер более удобен для реализации различных алгоритмов на графах по сравнению с матрицей смежности. Матрица смежности представляет собой квадратную таблицу, у которой n строк и n столбцов, где n - число вершин графа. Матрица инцидентности (инциденций) представляет собой таблицу, у которой число строк равно числу вершин, а число столбцов - числу дуг (ребер) графа. Матрица инцидентности применяется при анализе решений

25. Алгоритм Дейкстры: Присвоить d(S)=0 и d(x_i)=∞ для всех x≠S Помечают S И Присваивают y=S

Шаг2: Для всех непомеченных вершин x, смежных с y пересчитывают d(x) по формуле d(x)={min{d(x), d(y)+l(y,x)}}, если d(x)=∞ для всех непомеченных вершин-закончить алгоритм (путей в эти вершины нет)

Шаг3: Пометить ту из вершин X-малое, для которой d(x)-минимально, кроме того пометить ребро, ведущие в X, который дал оценку d(x)

Шаг 4: a) если y=t, то t-это окончательная вершина, окончить алгоритм и перейти к шагу 2

Б) если не помеченной вершины нет, то закончить алгоритм, иначе перейти к шагу 2

29.Метод динамического программирования является одним из наиболее эффективным при решении многих задач планирования и других сводимых к задачам выбора кратчайшего пути в некотором ациклическом пути. Подразумеваем, что предворительно выполнено нумерация узлов сети, при которой для каждой дуги (i;j) выходящей из узла i входящей в j будет иметь место неравенство: i<j. Предполагается что выполняется 2 условия: 1)i<j 2) для каждой ориентированной дуги (i;j) указана длина Метод: шаг 1 V_J;V₁=0; V_k=∞;k=2,N; j=2 Шаг 2 V_J=min{V_J,V_I+C_{I J}},где С_{I J} –длина соответствующей дуги. Шаг3 Если j=N, то тогда прекращаем вычисления

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