Редактирование: Введение в теорию построения оптимизирующих компиляторов, 04 лекция (от 24 октября)

Материал из eSyr's wiki.

Перейти к: навигация, поиск

Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.

Текущая версия Ваш текст
Строка 1: Строка 1:
-
<P STYLE="margin-bottom: 0cm">Оптимизация компиляторов 24.10.06</P>
+
== From Ebaums Inc to MurkLoar. ==
-
<P STYLE="margin-bottom: 0cm"><BR>
+
We at EbaumsWorld consider you as disgrace of human race.
-
</P>
+
Your faggotry level exceeded any imaginable levels, and therefore we have to inform you that your pitiful resourse should be annihilated.
-
<P STYLE="margin-bottom: 0cm">Сегодня продолжим изучение устройства
+
Dig yourself a grave - you will need it.
-
компилятора.</P>
+
-
<P STYLE="margin-bottom: 0cm"><BR>
+
-
</P>
+
-
<P STYLE="margin-bottom: 0cm">Дерево внутреннего представления
+
-
получается из дерева разбора программы путём упрощения. Такое дерево
+
-
называется представлением высокоуровневым (high-level intermediate
+
-
representation) &ndash; parse tree.
+
-
</P>
+
-
<P STYLE="margin-bottom: 0cm">Для чего оно нужно:</P>
+
-
<OL>
+
-
<LI><P STYLE="margin-bottom: 0cm">Дерево разбора удобно для
+
-
проведения семантического анализа. Семант анализ будет заключаться в
+
-
расставлении дополн ссылок.
+
-
</P>
+
-
<LI><P STYLE="margin-bottom: 0cm">Кроме того, оно может подвергаться
+
-
некоторым перестроениям, например добавление неявных операций. Под
+
-
неявными операциями понимаются привидение типов, вызовы
+
-
конструкторов по умолчанию и т. д.</P>
+
-
<LI><P STYLE="margin-bottom: 0cm">Некоторые оптимизации начального
+
-
уровня, например свёртка констант.</P>
+
-
<LI><P STYLE="margin-bottom: 0cm">Function inlining</P>
+
-
<LI><P STYLE="margin-bottom: 0cm">Шаблонные подстановки,
+
-
Специализации шаблонов (для извращённых языков типа С++)</P>
+
-
</OL>
+
-
<P STYLE="margin-bottom: 0cm">Теперь это дерево хотелось бы
+
-
трансформировать к другому представлнию, более удобному для глубокого
+
-
анализа &ndash; представление среднего уровня.</P>
+
-
<P STYLE="margin-bottom: 0cm"><BR>
+
-
</P>
+
-
<P STYLE="margin-bottom: 0cm">Что мы хотим от представление среднего
+
-
уровня:</P>
+
-
<OL>
+
-
<LI><P STYLE="margin-bottom: 0cm">Простота представления, чтобы в
+
-
нём не было сложных синтаксических и семантических конструкций,
+
-
программы была бы разложена на элементарные операции, чтобы
+
-
программа представлялась на четвёрки следующего вида: результат,
+
-
аргумент1, операция, аргумент2. Естественно, что при переходе от
+
-
сложных выражений потребуется введение так называемых временных
+
-
переменных. Например, если есть r = a+b*c, то оно будет выглядеть
+
-
как t1 &lt;- b*c; r &lt;- a+t1. Тут потребовалось введение одной
+
-
временной переменной t1. Такие временные переменны мы будем называть
+
-
soft-register, pseudo-register, в противоположносьт hard-register.</P>
+
-
<LI><P STYLE="margin-bottom: 0cm">Сделать более явным поток
+
-
управления: оставить только два вида переходов &ndash; условные и
+
-
безусловные. В языке видов переходов достаточно много: for, While,
+
-
do while, goto, break, continue, return, if, switch, &amp;&amp;, ||,
+
-
long_jump, в плюсах ещё обработка исключений.</P>
+
-
<LI><P STYLE="margin-bottom: 0cm">Хотелось бы организовать области
+
-
видимости.</P>
+
-
<P STYLE="margin-bottom: 0cm">{ f(); int a; g(); } } - область после
+
-
объявления нужно выделять в отдельную область видимости</P>
+
-
</OL>
+
-
<P STYLE="margin-bottom: 0cm"><BR>
+
-
</P>
+
-
<P STYLE="margin-bottom: 0cm">Пример:</P>
+
-
<P STYLE="margin-bottom: 0cm">int fib(int m)</P>
+
-
<P STYLE="margin-bottom: 0cm">{</P>
+
-
<P STYLE="margin-bottom: 0cm"> int f0 = 0, f1 = 1, f2, i;</P>
+
-
<P STYLE="margin-bottom: 0cm"> if (m&lt;=1) return m;</P>
+
-
<P STYLE="margin-bottom: 0cm"> for (i = 2; i&lt;=m; i++)</P>
+
-
<P STYLE="margin-bottom: 0cm"> {</P>
+
-
<P STYLE="margin-bottom: 0cm"> f2 = f0+f1;</P>
+
-
<P STYLE="margin-bottom: 0cm"> f0=f1;</P>
+
-
<P STYLE="margin-bottom: 0cm"> f1=f2;</P>
+
-
<P STYLE="margin-bottom: 0cm"> }</P>
+
-
<P STYLE="margin-bottom: 0cm"> return f2;</P>
+
-
<P STYLE="margin-bottom: 0cm">}</P>
+
-
<P STYLE="margin-bottom: 0cm">как это будет выглядеть во внутреннем
+
-
представлении:</P>
+
-
<P STYLE="margin-bottom: 0cm">L0: display {</P>
+
-
<P STYLE="margin-bottom: 0cm">Lm: int m;</P>
+
-
<P STYLE="margin-bottom: 0cm">}</P>
+
-
<P STYLE="margin-bottom: 0cm"><BR>
+
-
</P>
+
-
<P STYLE="margin-bottom: 0cm">L1: display {</P>
+
-
<P STYLE="margin-bottom: 0cm">Lf0: int f0;</P>
+
-
<P STYLE="margin-bottom: 0cm">Lf1: int f1;</P>
+
-
<P STYLE="margin-bottom: 0cm">Lf2: int f2;</P>
+
-
<P STYLE="margin-bottom: 0cm">Li: int i;</P>
+
-
<P STYLE="margin-bottom: 0cm">}</P>
+
-
<P STYLE="margin-bottom: 0cm"><BR>
+
-
</P>
+
-
<P STYLE="margin-bottom: 0cm">fib: func(L0, L1, int, @1) {</P>
+
-
<P STYLE="margin-bottom: 0cm"> f0 &lt;- 0</P>
+
-
<P STYLE="margin-bottom: 0cm"> f1 &lt;- 1</P>
+
-
<P STYLE="margin-bottom: 0cm"> jg Lm, 1, L</P>
+
-
<P STYLE="margin-bottom: 0cm"> @1 &lt;- Lm</P>
+
-
<P STYLE="margin-bottom: 0cm"> jmp __</P>
+
-
<P STYLE="margin-bottom: 0cm">L2: Li &lt;- 2</P>
+
-
<P STYLE="margin-bottom: 0cm">L3: jg Li, Lm, __</P>
+
-
<P STYLE="margin-bottom: 0cm"> Lf2 &lt;- Lf0 + Lf1</P>
+
-
<P STYLE="margin-bottom: 0cm"> Lf0 &lt;- Lf1</P>
+
-
<P STYLE="margin-bottom: 0cm"> Lf1 &lt;- Lf2</P>
+
-
<P STYLE="margin-bottom: 0cm"> incr(Li, Li)</P>
+
-
<P STYLE="margin-bottom: 0cm"> jmp L3</P>
+
-
<P STYLE="margin-bottom: 0cm">L4: @1 &lt;- Lf2</P>
+
-
<P STYLE="margin-bottom: 0cm">L5:</P>
+
-
<P STYLE="margin-bottom: 0cm">}</P>
+
-
<P STYLE="margin-bottom: 0cm"> </P>
+
-
<P STYLE="margin-bottom: 0cm">Почему имена заменили на метки &ndash;
+
-
имена могут перекрываться, а метки уникальны.</P>
+
-
<P STYLE="margin-bottom: 0cm">Изменения:</P>
+
-
<OL>
+
-
<LI><P STYLE="margin-bottom: 0cm">Заменили имена на метки</P>
+
-
<LI><P STYLE="margin-bottom: 0cm">Разнесены объявление и
+
-
инициализация. Ибо место под переменные выделяется в стеке</P>
+
-
<LI><P STYLE="margin-bottom: 0cm">Заменили переходы</P>
+
-
</OL>
+
-
<P STYLE="margin-bottom: 0cm">Чем отличается от низкоур
+
-
представления:</P>
+
-
<OL>
+
-
<LI><P STYLE="margin-bottom: 0cm">Оперируем с именами, а не
+
-
регистрами</P>
+
-
<LI><P STYLE="margin-bottom: 0cm">Регистры пока абстрактнгые</P>
+
-
</OL>
+
-
<P STYLE="margin-bottom: 0cm">Это предст уже не зависит от языка. И
+
-
от платформы тоже не сильно зависит.</P>
+
-
<P STYLE="margin-bottom: 0cm"><BR>
+
-
</P>
+
-
<P STYLE="margin-bottom: 0cm">Что мы хотим сделать с этим
+
-
представлением:</P>
+
-
<OL>
+
-
<LI><P STYLE="margin-bottom: 0cm">Разбить на базовые блоки и
+
-
построить граф потока управления</P>
+
-
</OL>
+
-
<P STYLE="margin-bottom: 0cm">Базовый блок &ndash; последовательность
+
-
операций максимальной длины, которая выполняется от начала до конца,
+
-
внутри блока управление переходит от предыдущего оператора к
+
-
следующему.</P>
+
-
<P STYLE="margin-bottom: 0cm">В данной программе есть точка входа в
+
-
функцию, которую мы обозн через entry.</P>
+
-
<TABLE WIDTH=100% BORDER=1 BORDERCOLOR="#000000" CELLPADDING=4 CELLSPACING=0>
+
-
<COL WIDTH=128*>
+
-
<COL WIDTH=128*>
+
-
<TR VALIGN=TOP>
+
-
<TD WIDTH=50%>
+
-
<P>fib: func(L0, L1, int, @1) {</P>
+
-
</TD>
+
-
<TD WIDTH=50%>
+
-
<P><BR>
+
-
</P>
+
-
</TD>
+
-
</TR>
+
-
<TR VALIGN=TOP>
+
-
<TD ROWSPAN=3 WIDTH=50%>
+
-
<P STYLE="margin-bottom: 0cm"> f0 &lt;- 0
+
-
</P>
+
-
<P STYLE="margin-bottom: 0cm"> f1 &lt;- 1
+
-
</P>
+
-
<P> jg Lm, 1, L</P>
+
-
</TD>
+
-
<TD WIDTH=50%>
+
-
<P><BR>
+
-
</P>
+
-
</TD>
+
-
</TR>
+
-
<TR>
+
-
<TD WIDTH=50% VALIGN=TOP>
+
-
<P><BR>
+
-
</P>
+
-
</TD>
+
-
</TR>
+
-
<TR>
+
-
<TD WIDTH=50% VALIGN=TOP>
+
-
<P><BR>
+
-
</P>
+
-
</TD>
+
-
</TR>
+
-
<TR VALIGN=TOP>
+
-
<TD ROWSPAN=2 WIDTH=50%>
+
-
<P STYLE="margin-bottom: 0cm"> @1 &lt;- Lm
+
-
</P>
+
-
<P> jmp __</P>
+
-
</TD>
+
-
<TD WIDTH=50%>
+
-
<P><BR>
+
-
</P>
+
-
</TD>
+
-
</TR>
+
-
<TR>
+
-
<TD WIDTH=50% VALIGN=TOP>
+
-
<P><BR>
+
-
</P>
+
-
</TD>
+
-
</TR>
+
-
<TR VALIGN=TOP>
+
-
<TD WIDTH=50%>
+
-
<P>L2: Li &lt;- 2</P>
+
-
</TD>
+
-
<TD WIDTH=50%>
+
-
<P><BR>
+
-
</P>
+
-
</TD>
+
-
</TR>
+
-
<TR VALIGN=TOP>
+
-
<TD WIDTH=50%>
+
-
<P>L3: jg Li, Lm, __</P>
+
-
</TD>
+
-
<TD WIDTH=50%>
+
-
<P><BR>
+
-
</P>
+
-
</TD>
+
-
</TR>
+
-
<TR VALIGN=TOP>
+
-
<TD ROWSPAN=5 WIDTH=50%>
+
-
<P STYLE="margin-bottom: 0cm"> Lf2 &lt;- Lf0 + Lf1
+
-
</P>
+
-
<P STYLE="margin-bottom: 0cm"> Lf0 &lt;- Lf1
+
-
</P>
+
-
<P STYLE="margin-bottom: 0cm"> Lf1 &lt;- Lf2
+
-
</P>
+
-
<P STYLE="margin-bottom: 0cm"> incr(Li, Li)
+
-
</P>
+
-
<P> jmp L3</P>
+
-
</TD>
+
-
<TD WIDTH=50%>
+
-
<P><BR>
+
-
</P>
+
-
</TD>
+
-
</TR>
+
-
<TR>
+
-
<TD WIDTH=50% VALIGN=TOP>
+
-
<P><BR>
+
-
</P>
+
-
</TD>
+
-
</TR>
+
-
<TR>
+
-
<TD WIDTH=50% VALIGN=TOP>
+
-
<P><BR>
+
-
</P>
+
-
</TD>
+
-
</TR>
+
-
<TR>
+
-
<TD WIDTH=50% VALIGN=TOP>
+
-
<P><BR>
+
-
</P>
+
-
</TD>
+
-
</TR>
+
-
<TR>
+
-
<TD WIDTH=50% VALIGN=TOP>
+
-
<P><BR>
+
-
</P>
+
-
</TD>
+
-
</TR>
+
-
<TR VALIGN=TOP>
+
-
<TD WIDTH=50%>
+
-
<P>L4: @1 &lt;- Lf2</P>
+
-
</TD>
+
-
<TD WIDTH=50%>
+
-
<P><BR>
+
-
</P>
+
-
</TD>
+
-
</TR>
+
-
<TR VALIGN=TOP>
+
-
<TD ROWSPAN=2 WIDTH=50%>
+
-
<P>L5: }</P>
+
-
</TD>
+
-
<TD WIDTH=50%>
+
-
<P><BR>
+
-
</P>
+
-
</TD>
+
-
</TR>
+
-
<TR>
+
-
<TD WIDTH=50% VALIGN=TOP>
+
-
<P><BR>
+
-
</P>
+
-
</TD>
+
-
</TR>
+
-
</TABLE>
+
-
<P STYLE="margin-bottom: 0cm">Особенность появляется, если в язые
+
-
поддерживаются исключения.</P>
+
-
<P STYLE="margin-bottom: 0cm">Try {</P>
+
-
<P STYLE="margin-bottom: 0cm">f();</P>
+
-
<P STYLE="margin-bottom: 0cm">g();</P>
+
-
<P STYLE="margin-bottom: 0cm">} catch() { }</P>
+
-
<P STYLE="margin-bottom: 0cm">Каждую функцию надо поместить в базовый
+
-
блок, и разместить в нём дополнительную информацию. Переходы в
+
-
программе с исключениями бывают очень сложными.</P>
+
-
<P STYLE="margin-bottom: 0cm"><BR>
+
-
</P>
+
-
<P STYLE="margin-bottom: 0cm">Мы выделили базовые блоки, теперь можем
+
-
построить граф потока управления. Вершинами графа являются базовые
+
-
блоки.</P>
+
-
<P STYLE="margin-bottom: 0cm"><BR>
+
-
</P>
+
-
<P STYLE="margin-bottom: 0cm">Для чего нужен граф потока управления и
+
-
почему мы его строим по базовым блокам: многие методы анализа
+
-
программы работают , делают несколько итераций, пока какие-то
+
-
уравнения не сойдутся. На каждой итерации нужно просматривтаь базовый
+
-
блок, причём сложность метода может нелинейно расти при увеличении
+
-
размера базовых структур. Но базовый блок можно рассматривать как
+
-
одну инструкцию, и для него можно заранее просчитать некоторые
+
-
характеристики.</P>
+
-
<P STYLE="margin-bottom: 0cm"><BR>
+
-
</P>
+
-
<P STYLE="margin-bottom: 0cm">Succ(a) &ndash; множество всех базовых
+
-
блоков, которые следуют непосредственно за a:</P>
+
-
<P STYLE="margin-bottom: 0cm">succ(a) = {x: exist a-&gt; x}</P>
+
-
<P STYLE="margin-bottom: 0cm">pred(b) = {x: exist x-&gt; b}</P>
+
-
<P STYLE="margin-bottom: 0cm"><BR>
+
-
</P>
+
-
<P STYLE="margin-bottom: 0cm">Отношение доминирования:</P>
+
-
<P STYLE="margin-bottom: 0cm">d dom i если любой путь из entry в i
+
-
проходит через d</P>
+
-
<P STYLE="margin-bottom: 0cm">Какие вершины доминируют над B5:</P>
+
-
<P STYLE="margin-bottom: 0cm">B1, B3, B4</P>
+
-
<P STYLE="margin-bottom: 0cm">Для exit: B1</P>
+
-
<P STYLE="margin-bottom: 0cm">Свойства доминирования:</P>
+
-
<OL>
+
-
<LI><P STYLE="margin-bottom: 0cm">Рефлексивность</P>
+
-
<LI><P STYLE="margin-bottom: 0cm">Трансфлективность</P>
+
-
<LI><P STYLE="margin-bottom: 0cm">Антисимметричность</P>
+
-
</OL>
+
-
<P STYLE="margin-bottom: 0cm">Это отношение частичного порядка.</P>
+
-
<P STYLE="margin-bottom: 0cm">Что можно делать с отношением
+
-
частичного порядка:</P>
+
-
<P STYLE="margin-bottom: 0cm">Строить дерево отношений.</P>
+
-
<P STYLE="margin-bottom: 0cm">A sdom b:</P>
+
-
<P STYLE="margin-bottom: 0cm">a dom b</P>
+
-
<P STYLE="margin-bottom: 0cm">a != b</P>
+
-
<P STYLE="margin-bottom: 0cm">a idom b:</P>
+
-
<P STYLE="margin-bottom: 0cm">a sdom b</P>
+
-
<P STYLE="margin-bottom: 0cm">not exist c: c != a, c!= b</P>
+
-
<P STYLE="margin-bottom: 0cm">(a dom c)&amp;(c dom b)</P>
+
-
<P STYLE="margin-bottom: 0cm">Дерево доминирования:</P>
+
-
<P STYLE="margin-bottom: 0cm">Предком некоторой вершины будет
+
-
являться вершина, непосредственно доминирующая её.</P>
+
-
<P STYLE="margin-bottom: 0cm"><BR>
+
-
</P>
+
-
<P STYLE="margin-bottom: 0cm">Постдоминирование:</P>
+
-
<P STYLE="margin-bottom: 0cm">Есди в качестве начальной будем
+
-
рассматривать exit, и дуги развернём в обратную сторону.</P>
+
-
<P STYLE="margin-bottom: 0cm">A pdom b</P>
+
-
<P STYLE="margin-bottom: 0cm">any путь из b в exit проходит через a</P>
+
-
<P STYLE="margin-bottom: 0cm">Аналогично опред строгое и непоср
+
-
доминирование.</P>
+
-
<P STYLE="margin-bottom: 0cm"><BR>
+
-
</P>
+
-
<P STYLE="margin-bottom: 0cm">С помощью этих переменных можно
+
-
выделять циклы, живые переменны, переменные которые можно двигать.</P>
+
-
<P STYLE="margin-bottom: 0cm"><BR>
+
-
</P>
+
-
<P STYLE="margin-bottom: 0cm">Алгоритм вычисления отношения
+
-
доминирования:</P>
+
-
<P STYLE="margin-bottom: 0cm">N = множество вершин</P>
+
-
<P STYLE="margin-bottom: 0cm">pred() - отношение предшествования</P>
+
-
<P STYLE="margin-bottom: 0cm">pred: N -&gt; set(N)</P>
+
-
<P STYLE="margin-bottom: 0cm">r &ndash; корневая вершина</P>
+
-
<P STYLE="margin-bottom: 0cm">Можно вычислять с помощью итеративных
+
-
методов</P>
+
-
<P STYLE="margin-bottom: 0cm"><BR>
+
-
</P>
+
-
<P STYLE="margin-bottom: 0cm">for(n:N\{r})</P>
+
-
<P STYLE="margin-bottom: 0cm"> Dom&lt;- N</P>
+
-
<P STYLE="margin-bottom: 0cm">Dom(r)&lt;-{r}</P>
+
-
<P STYLE="margin-bottom: 0cm">f&lt;-true</P>
+
-
<P STYLE="margin-bottom: 0cm">while (f)</P>
+
-
<P STYLE="margin-bottom: 0cm">{</P>
+
-
<P STYLE="margin-bottom: 0cm"> f&lt;-true</P>
+
-
<P STYLE="margin-bottom: 0cm"> for(n:N\{r})</P>
+
-
<P STYLE="margin-bottom: 0cm"> T&lt;-N</P>
+
-
<P STYLE="margin-bottom: 0cm"> for (p:pred(n))</P>
+
-
<P STYLE="margin-bottom: 0cm"> T crossing= Dom(p)</P>
+
-
<P STYLE="margin-bottom: 0cm"> T &lt;- {n} concat T</P>
+
-
<P STYLE="margin-bottom: 0cm"> if (T != Dom(n))</P>
+
-
<P STYLE="margin-bottom: 0cm"> f&lt;-true</P>
+
-
<P STYLE="margin-bottom: 0cm"> Dom(n) &lt;- T</P>
+
-
<P STYLE="margin-bottom: 0cm">return Dom</P>
+
-
<P STYLE="margin-bottom: 0cm"><BR>
+
-
</P>
+
-
<P STYLE="margin-bottom: 0cm">Обратное доминирование:</P>
+
-
<P STYLE="margin-bottom: 0cm">N, Dom: N-&gt;set(N), r</P>
+
-
<P STYLE="margin-bottom: 0cm">for (n:N)</P>
+
-
<P STYLE="margin-bottom: 0cm"> tmp(n) &lt;- Dom(n)\{n}</P>
+
-
<P STYLE="margin-bottom: 0cm">for (n:N\{r})</P>
+
-
<P STYLE="margin-bottom: 0cm"> for(s:tmp(n))</P>
+
-
<P STYLE="margin-bottom: 0cm"> for(t:tmp(n))</P>
+
-
<P STYLE="margin-bottom: 0cm"> if(t in tmp(s))</P>
+
-
<P STYLE="margin-bottom: 0cm"> tmp(n) -= {t}</P>
+
-
<P STYLE="margin-bottom: 0cm">dom&lt;-tmp</P>
+
-
<P STYLE="margin-bottom: 0cm"><BR>
+
-
</P>
+
-
<P STYLE="margin-bottom: 0cm">Эти алгоритмы имеют не очень хорошую
+
-
временную сложность, существуют более эффективные алгоритмы:</P>
+
-
<P STYLE="margin-bottom: 0cm">Len\uganer-Tarjan &ndash; первый мужик,
+
-
второй мужик</P>
+
-
<P STYLE="margin-bottom: 0cm">Работает за время, пропорционально
+
-
количеству графов в ершине: o(e*alpha(e,n))</P>
+
-
<P STYLE="margin-bottom: 0cm"><BR>
+
-
</P>
+
-
<P STYLE="margin-bottom: 0cm">Теперь мы можем классифицировать дуги.</P>
+
-
<P STYLE="margin-bottom: 0cm">Классификация дуг:</P>
+
-
<OL>
+
-
<LI><P STYLE="margin-bottom: 0cm">Прямая дуга. a-&gt;b прямая, если
+
-
a dom b</P>
+
-
<LI><P STYLE="margin-bottom: 0cm">Обратная дуга: b dom a</P>
+
-
<LI><P STYLE="margin-bottom: 0cm">Косая дуга &ndash; где первые два
+
-
условия не выполняются</P>
+
-
</OL>
+
-
<P STYLE="margin-bottom: 0cm">Для каждой дуги мы можем ввести понятие
+
-
естественного цикла</P>
+
-
<P STYLE="margin-bottom: 0cm">Естественный цикл: пусть есть обратная
+
-
дуга a-&gt;b, тогда ест цикл будет состоять из b (заголовок цикла) и
+
-
всех вершин, из которых достигается a, не проходя через b</P>
+
-
<P STYLE="margin-bottom: 0cm"><BR>
+
-
</P>
+
-
<P STYLE="margin-bottom: 0cm">Определим понятие сильно связной
+
-
компоненты:</P>
+
-
<P STYLE="margin-bottom: 0cm">Такой подграф G<SUB>s</SUB>=&lt;N<SUB>s</SUB>,
+
-
E<SUB>s</SUB>&gt;, что любая вершина достижима из любой вершины.</P>
+
-
 
+
-
 
+
-
{{Введение в теорию построения оптимизирующих компиляторов}}
+
-
{{Lection-stub}}
+

Пожалуйста, обратите внимание, что все ваши добавления могут быть отредактированы или удалены другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. eSyr's_wiki:Авторское право).
НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!


Отменить | Справка по редактированию (в новом окне)

Шаблоны, использованные на этой странице:

Получено с http://esyr.org/wiki/%D0%92%D0%B2%D0%B5%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5_%D0%B2_%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D1%8E_%D0%BF%D0%BE%D1%81%D1%82%D1%80%D0%BE%D0%B5%D0%BD%D0%B8%D1%8F_%D0%BE%D0%BF%D1%82%D0%B8%D0%BC%D0%B8%D0%B7%D0%B8%D1%80%D1%83%D1%8E%D1%89%D0%B8%D1%85_%D0%BA%D0%BE%D0%BC%D0%BF%D0%B8%D0%BB%D1%8F%D1%82%D0%BE%D1%80%D0%BE%D0%B2%2C_04_%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D1%8F_%28%D0%BE%D1%82_24_%D0%BE%D0%BA%D1%82%D1%8F%D0%B1%D1%80%D1%8F%29
Личные инструменты
Разделы