Участник:Shovkoplyas Grigory - История изменений

46.175.24.28: /* Просмотр таблицы маршрутизации */

2017-01-02T01:28:34Z

‎Просмотр таблицы маршрутизации

46.175.24.28 в 01:28, 2 января 2017

2017-01-02T01:28:04Z

46.175.24.28 в 20:08, 1 января 2017

2017-01-01T20:08:29Z

46.175.24.28 в 15:56, 1 января 2017

2017-01-01T15:56:39Z

46.175.24.28 в 15:46, 1 января 2017

2017-01-01T15:46:19Z

Внесённые изменения

Shovkoplyas Grigory в 14:11, 1 января 2017

2017-01-01T14:11:45Z

Shovkoplyas Grigory в 17:17, 18 января 2016

2016-01-18T17:17:04Z

Shovkoplyas Grigory в 17:13, 18 января 2016

2016-01-18T17:13:54Z

Shovkoplyas Grigory в 17:07, 18 января 2016

2016-01-18T17:07:40Z

Shovkoplyas Grigory в 17:05, 18 января 2016

2016-01-18T17:05:25Z

← Предыдущая		Версия 01:28, 2 января 2017
Строка 82:		Строка 82:

	Windows: '''route print'''		Windows: '''route print'''
		+
	Linux: '''route -n'''		Linux: '''route -n'''

@@ Строка 75: / Строка 75: @@
 Внутри каждого пакета есть поле TTL (Time to live) при каждой пересылке значение уменьшается на единицу, и если оно становится нулем, то пакет выбрасывается.
-ICMP-сообщение в данном случае''TTL expired in transit''.
+ICMP-сообщение в данном случае ''TTL expired in transit''.
@@ Строка 82: / Строка 82: @@
 Windows: '''route print'''
 ==Источники информации==

@@ Строка 52: / Строка 52: @@
 |}
-Чтобы вычислить адрес сети, нужно применить логическое ''или'' к адресу и маске.
+Чтобы вычислить адрес сети, нужно применить логическое ''и'' к адресу и маске.
 {{Определение
@@ Строка 66: / Строка 66: @@
 {{Определение
 |definition =
-Метрика (Metric) {{---}} числовой показатель, задающий предпочтительность маршрута. Чем меньше число, тем более предпочтителен маршрут. Интуитивно представляется как расстояние.
+Метрика (Metric) {{---}} числовой показатель, задающий предпочтительность маршрута. Чем меньше число, тем более предпочтителен маршрут. Интуитивно представляется как расстояние (необязательный параметр).
 }}
 ==Принцип действия==
 При отправке сетевого пакета, операционная система смотрит, по какому именно маршруту он должен быть отправлен, основываясь на таблице маршрутизации.
-Как правило, выбирается наиболее конкретный (т.е. с наиболее длинной сетевой маской) маршрут из тех, которые соответствуют адресу отправителя.
+Как правило, выбирается наиболее конкретный (т.е. с наиболее длинной сетевой маской) маршрут из тех, которые соответствуют адресу отправителя и имеют наименьшую метрику.
 Если ни один из маршрутов не подходит, пакет уничтожается, а его отправителю возвращается ICMP-сообщение ''No route to host''.

← Предыдущая		Версия 15:56, 1 января 2017
Строка 64:		Строка 64:
	}}		}}

		+	{{Определение
		+	\|definition =
		+	Метрика (Metric) {{---}} числовой показатель, задающий предпочтительность маршрута. Чем меньше число, тем более предпочтителен маршрут. Интуитивно представляется как расстояние.
		+	}}

		+	==Принцип действия==
		+	При отправке сетевого пакета, операционная система смотрит, по какому именно маршруту он должен быть отправлен, основываясь на таблице маршрутизации.
		+	Как правило, выбирается наиболее конкретный (т.е. с наиболее длинной сетевой маской) маршрут из тех, которые соответствуют адресу отправителя.
		+	Если ни один из маршрутов не подходит, пакет уничтожается, а его отправителю возвращается ICMP-сообщение ''No route to host''.

		+
		+	==Просмотр таблицы маршрутизации==
		+	Ниже приведены команды в разных операционных системах, с помощью которых можно посмотреть таблицу маршрутизации
		+
		+	Windows: '''route print'''

	==Источники информации==		==Источники информации==

@@ Строка 1: / Строка 1: @@
 '''Алгоритм Эрли''' позволяет определить, выводится ли данное слово <tex>w</tex> в данной [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободной]] грамматике <tex>G</tex>.
@@ Строка 4: / Строка 34: @@
 '''Выход:''' <tex>true</tex>, если <tex>w</tex> выводится в <tex>G</tex>; <tex>false</tex> — иначе.
 {{Определение
 |definition =

@@ Строка 77: / Строка 77: @@
-=====<tex>\Longrightarrow</tex>=====
+<b><tex>\Longrightarrow</tex></b><br/>
 Докажем индукцией по исполнению алгоритма.<br/>
 <u> ''База  индукции:'' </u><br/>
@@ Строка 101: / Строка 101: @@
 Cледовательно <tex>\alpha = \alpha ' A' \Rightarrow^* w_i...w_{i'-1} w_{i'}...w_{j} = w_i...w_{j-1}</tex>, что дает нам второй пункт утверждения, а так как первый пункт следует из индукционного предположения, все хорошо.
-=====<tex>\Longleftarrow</tex>=====
+<b><tex>\Longleftarrow</tex></b><br/>
 В обратную сторону будем доказывать индукцией по суммарной длине вывода  <tex>w_0...w_{i-1} A \delta</tex> из <tex>S'</tex> и  <tex>w_i...w_{j-1}</tex> из <tex>\alpha</tex>. После чего применим
 индукцию по длине вывода <tex>w_i...w_{j-1}</tex> из <tex>\alpha</tex>.<br/>

← Предыдущая		Версия 17:13, 18 января 2016
Строка 307:		Строка 307:
	[[Категория: Теория формальных языков]]		[[Категория: Теория формальных языков]]
	[[Категория: Контекстно-свободные грамматики]]		[[Категория: Контекстно-свободные грамматики]]
		+	[[Категория: Алгоритмы разбора]]

← Предыдущая		Версия 17:07, 18 января 2016
Строка 304:		Строка 304:
	*[http://lpcs.math.msu.su/~sk/lehre/fivt2013/Earley.pdf Алексей Сорокин {{---}} Алгоритм Эрли]		*[http://lpcs.math.msu.su/~sk/lehre/fivt2013/Earley.pdf Алексей Сорокин {{---}} Алгоритм Эрли]
	* Ахо А., Ульман Д.{{---}} Теория синтакcического анализа, перевода и компиляции. Том 1. Синтаксический анализ. Пер. с англ. {{---}} М.:«Мир», 1978. С. 358 — 364.		* Ахо А., Ульман Д.{{---}} Теория синтакcического анализа, перевода и компиляции. Том 1. Синтаксический анализ. Пер. с англ. {{---}} М.:«Мир», 1978. С. 358 — 364.
		+
		+	[[Категория: Теория формальных языков]]
		+	[[Категория: Контекстно-свободные грамматики]]

@@ Строка 8: / Строка 8: @@
 |definition =
 Пусть <tex>G = \langle N, \Sigma, P, S \rangle</tex> {{---}} [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная]] грамматика и <tex>w = w_0 w_1 ... w_{n-1}</tex> {{---}} входная цепочка из <tex>\Sigma^*</tex>.
-Объект вида <tex>[A \rightarrow \alpha \cdot \beta, i]</tex>, где <tex>A \rightarrow \alpha \beta </tex> — правило из <tex>P</tex> и <tex>0 \leqslant i \leqslant n</tex> — позиция в <tex>w</tex>, называется '''ситуацией''', относящейся к цепочке <tex>w</tex>. '''<tex> \cdot </tex>''' {{---}} вспомогательный символ, который не явлется терминалом или нетерминалом ( <tex> \cdot \notin \Sigma \cup N</tex>).
+Объект вида <tex>[A \rightarrow \alpha \cdot \beta, i]</tex>, где <tex>A \rightarrow \alpha \beta </tex> — правило из <tex>P</tex> и <tex>0 \leqslant i \leqslant n</tex> — позиция в <tex>w</tex>, называется '''ситуацией''', относящейся к цепочке <tex>w</tex>, где '''<tex> \cdot </tex>''' {{---}} вспомогательный символ, который не явлется терминалом или нетерминалом ( <tex> \cdot \notin \Sigma \cup N</tex>).
 }}
 {{Определение
 |definition =
-Ситуации хранятся в множествах <tex>D_0,...,D_{n-1}</tex>, называемых спиками ситуаций. Причем наличие ситуации <tex>[A \rightarrow \alpha \cdot \beta , i]</tex> в <tex>j</tex>-м списке ситуаций <tex>D_j</tex> равносильно тому, что
+Ситуации хранятся в множествах <tex>D_0,...,D_{n-1}</tex>, называемых '''списками ситуаций'''. Причем наличие ситуации <tex>[A \rightarrow \alpha \cdot \beta , i]</tex> в <tex>j</tex>-м списке ситуаций <tex>D_j</tex> равносильно тому, что
-<tex>\exists \delta \in \Sigma \cup N : ((S' \Rightarrow^* w_0...w_{i-1} A \delta) \wedge A \Rightarrow^* w_i...w_{j-1})</tex>
+<tex>\exists \delta \in \Sigma \cup N : ((S' \Rightarrow^* w_0...w_{i-1} A \delta) \wedge A \Rightarrow^* w_i...w_{j-1})</tex>.
 }}
@@ Строка 36: / Строка 36: @@
     <font color=green>// Инициализация </font>
     <tex> D_{0} = \lbrace [S' \rightarrow \cdot S, 0] \rbrace </tex>
-    '''for''' i = 1 '''to''' len(w) - 1
+    '''for''' <tex>i = 1</tex> '''to''' <tex>len(w) - 1</tex>
       <tex>D_i</tex> = <tex>\varnothing </tex>
     <font color=green>// Вычисление ситуаций </font>
-    '''for''' j = 0 '''to''' len(w) - 1
+    '''for''' <tex>j = 0</tex> '''to''' <tex>len(w) - 1</tex>
       <tex>\mathtt{scan}(D, j, G, w)</tex>
       '''while''' <tex>D_j</tex> изменяется
@@ Строка 46: / Строка 46: @@
     <font color=green>// Результат </font>
     '''if'''  <tex>[S' \rightarrow S \cdot, 0] \in D_{len(w)} </tex>
-      '''return''' ''True''
+      '''return''' ''true''
     '''else'''
-      '''return''' ''False''
+      '''return''' ''false''
   <font color=green>// Первое правило </font>
@@ Строка 79: / Строка 79: @@
 =====<tex>\Longrightarrow</tex>=====
 Докажем индукцией по исполнению алгоритма.<br/>
-База {{---}} <tex>[S' \rightarrow \cdot S, 0] \in D_0</tex>. Осталось разобраться, в результате применения какого правила ситуация <tex> [A \rightarrow \alpha \cdot \beta, i] </tex> попала в <tex>D_{j}</tex><br/>
+<u> ''База  индукции:'' </u><br/>
 . Включаем по правилу <tex> \mathtt{scan}</tex>.<br/>
@@ Строка 108: / Строка 111: @@
 . <tex>\alpha = \alpha ' B</tex>, тогда <tex>\exists i' : \alpha ' \Rightarrow^* w_i...w_{i'-1} \wedge B ' \Rightarrow^* w_{i'}...w_{j-1}</tex>.<br/>
 Тогда имеем <tex>[A \rightarrow \alpha ' a \cdot  \beta, i] \in D_{j}</tex>. Также можно записать <tex>S' \Rightarrow^* w_0...w_{i-1} A \delta</tex>, как <tex>S' \Rightarrow^* w_0...w_{i-1} w_i...w_{i'-1}B \beta \delta</tex>,
-а также <tex>B \rightarrow \eta \wedge \eta \rightarrow w_{i'}...w_{j-1}<tex>.<br/>
+а также <tex>B \rightarrow \eta \wedge \eta \rightarrow w_{i'}...w_{j-1}</tex>.<br/>
 Применяя индукцию по второму параметру получим <tex>[B \rightarrow \eta \cdot, i'] \in D_j</tex>, откуда по правилу <tex> \mathtt{complete}</tex> получаем <tex>[A \rightarrow \alpha ' B \cdot \beta, i] \in D_{j}</tex>.
@@ Строка 122: / Строка 125: @@
 ==Пример==
 Построим список разбора для строки <tex>w = (a + a)</tex> в грамматике со следующими правилами:
-* <tex>S \rightarrow T + S</tex>;
+* <tex>S \rightarrow T + S</tex>
-* <tex>S \rightarrow T </tex>;
+* <tex>S \rightarrow T </tex>
-* <tex>T \rightarrow F * T</tex>;
+* <tex>T \rightarrow F * T</tex>
-* <tex>T \rightarrow F</tex>;
+* <tex>T \rightarrow F</tex>
-* <tex>F \rightarrow ( S )</tex>;
+* <tex>F \rightarrow ( S )</tex>
-* <tex>F \rightarrow a</tex>.
+* <tex>F \rightarrow a</tex>
 {|
@@ Строка 293: / Строка 296: @@
 Так как <tex>[S' \rightarrow S \cdot , 0] \in I_5</tex>, то <tex>w \in L(G) </tex>.<br>
 ==Источники информации==
 *[http://lpcs.math.msu.su/~sk/lehre/fivt2013/Earley.pdf Алексей Сорокин {{---}} Алгоритм Эрли]
 * Ахо А., Ульман Д.{{---}} Теория синтакcического анализа, перевода и компиляции. Том 1. Синтаксический анализ. Пер. с англ. {{---}} М.:«Мир», 1978. С. 358 — 364.