Викиконспекты - Вклад участника [ru]

Свойства перечислимых языков. Теорема Успенского-Райса

2014-12-14T10:18:45Z

217.118.78.38: /* Теорема Успенского-Райса */

== Свойства языков ==

Рассмотрим множество всех [[Перечислимые_языки|перечислимых]] языков <tex> \mathrm {RE} </tex>.
{{Определение
|definition='''Свойством языков''' (англ. ''property of languages'') называется множество <tex> A \subset \mathrm {RE} </tex>.
}}
'''Примеры свойств''':
* Язык должен содержать слово ''hello''.
* Язык должен содержать хотя бы одно простое число.

{{Определение
|definition=Свойство называется '''тривиальным''' (англ. ''trivial''), если <tex> A = \varnothing </tex> или <tex> A = \mathrm {RE} </tex>.
}}
Псевдокод для <tex>A = \mathrm {RE} </tex>
<tex>p_A(p_X)</tex>
'''return <tex>L(p_X) \in \mathrm{RE}</tex>

{{Определение
|definition='''Язык свойства''' (англ. ''language of property'') <tex> A </tex> {{---}} множество программ, языки которых обладают этим свойством: <tex>L(A) \overset{\underset{\mathrm{def}}{}}{=} \lbrace p \mid L(p) \in A \rbrace </tex>.
}}
Пример.
Пусть <tex>p_X</tex> {{---}} разрешитель некоторого языка
p(<tex>p_X</tex>)
'''return''' <tex>p_X</tex>('hello')
{{Определение
|definition=Свойство <tex> A </tex> называется '''разрешимым''' (англ. ''recursive''), если <tex>L(A) </tex> является [[Разрешимые_(рекурсивные)_языки|разрешимым]].
}}

== Теорема Успенского-Райса ==
{{Теорема
|statement=
Язык никакого нетривиального свойства не является разрешимым.
|proof=
Приведём доказательство от противного.

Предположим, что <tex>A</tex> разрешимо и нетривиально, <tex>p_A</tex> {{---}} программа, разрешающая <tex>A</tex>.

Не умаляя общности, можно считать, что <tex>\varnothing \notin A</tex> (в противном случае перейдём к <tex> \mathrm {RE} \setminus A</tex>, которое также будет разрешимым и нетривиальным, так как <tex> \mathrm {RE} \setminus A \neq \varnothing </tex> и <tex> \mathrm {RE} \setminus A \neq \mathrm {RE} ) </tex>.

Поскольку <tex>A</tex> непусто, то найдётся перечислимый язык <tex>X \in A</tex>. Пусть <tex>p_X</tex> {{---}} полуразрешитель <tex>X</tex>.

Рассмотрим вспомогательную программу:
<tex> U(i, x) </tex> {{---}} универсальная функция
<tex>g_{i,x}(y):</tex>
'''if''' <tex>U(i, x)</tex> == 1 <font color=green> // если i (где i - это программа), на входе x выдает 1. </font>
'''return''' <tex>p_X(y)</tex>
'''else'''
'''while''' ''true''
Исключение пустого множества нам нужно чтобы различать <tex> X</tex> и пустое.
Нетрудно понять, что в разумной модели вычислений номер этой программы можно вычислить по данным <tex>i</tex> и <tex>x</tex>. Значит, можно рассмотреть такую программу:
<tex>US(\langle i, x \rangle )</tex>
'''return''' <tex>p_A ( g_{i,x} ) </tex>

Заметим, что
<tex>
L(g_{i,x}) = \begin{cases}
X, & U(i, x) = 1; \\
\varnothing, & U(i, x) \neq 1; \\
\end{cases}
</tex>

Следовательно, <br/> <tex>
US(\langle i, x \rangle ) = p_A(g_{i,x}) = \begin{cases}
p_A(p_X), & U(i, x) = 1; \\
p_A(p_\varnothing ), & U(i, x) \neq 1; \\
\end{cases} = \begin{cases}
1, & U(i, x) = 1; \\
0, & U(i, x) \neq 1; \\
\end{cases}
</tex> {{---}} программа, разрешающая [[Универсальная функция | универсальное множество]]. Получили противоречие.
}}

== См. также ==
* [[Теорема о рекурсии]]
* [[Теорема Райса-Шапиро]]

== Источники информации ==
* [https://en.wikipedia.org/wiki/Rice%27s_theorem Wikipedia — Rice's theorem]
* Rice, H. G. "Classes of Recursively Enumerable Sets and Their Decision Problems." Trans. Amer. Math. Soc. 74, 358-366, 1953.
* Хопкрофт Д., Мотванн Р., Ульманн Д. Введение в теорию автоматов, языков и вычислений страница 397.
[[Категория: Теория вычислимости]]
[[Категория: Теория формальных языков]]

Свойства перечислимых языков. Теорема Успенского-Райса

2014-12-14T10:03:39Z

217.118.78.38: /* Свойства языков */

== Свойства языков ==

Рассмотрим множество всех [[Перечислимые_языки|перечислимых]] языков <tex> \mathrm {RE} </tex>.
{{Определение
|definition='''Свойством языков''' (англ. ''property of languages'') называется множество <tex> A \subset \mathrm {RE} </tex>.
}}
'''Примеры свойств''':
* Язык должен содержать слово ''hello''.
* Язык должен содержать хотя бы одно простое число.

{{Определение
|definition=Свойство называется '''тривиальным''' (англ. ''trivial''), если <tex> A = \varnothing </tex> или <tex> A = \mathrm {RE} </tex>.
}}
Псевдокод для <tex>A = \mathrm {RE} </tex>
<tex>p_A(p_X)</tex>
'''return <tex>L(p_X) \in \mathrm{RE}</tex>

{{Определение
|definition='''Язык свойства''' (англ. ''language of property'') <tex> A </tex> {{---}} множество программ, языки которых обладают этим свойством: <tex>L(A) \overset{\underset{\mathrm{def}}{}}{=} \lbrace p \mid L(p) \in A \rbrace </tex>.
}}
Пример.
Пусть <tex>p_X</tex> {{---}} разрешитель некоторого языка
p(<tex>p_X</tex>)
'''return''' <tex>p_X</tex>('hello')
{{Определение
|definition=Свойство <tex> A </tex> называется '''разрешимым''' (англ. ''recursive''), если <tex>L(A) </tex> является [[Разрешимые_(рекурсивные)_языки|разрешимым]].
}}

== Теорема Успенского-Райса ==
{{Теорема
|statement=
Язык никакого нетривиального свойства не является разрешимым.
|proof=
Приведём доказательство от противного.

Предположим, что <tex>A</tex> разрешимо и нетривиально, <tex>p_A</tex> {{---}} программа, разрешающая <tex>A</tex>.

Не умаляя общности, можно считать, что <tex>\varnothing \notin A</tex> (в противном случае перейдём к <tex> \mathrm {RE} \setminus A</tex>, которое также будет разрешимым и нетривиальным, так как <tex> \mathrm {RE} \setminus A \neq \varnothing </tex> и <tex> \mathrm {RE} \setminus A \neq \mathrm {RE} ) </tex>.

Поскольку <tex>A</tex> непусто, то найдётся перечислимый язык <tex>X \in A</tex>. Пусть <tex>p_X</tex> {{---}} полуразрешитель <tex>X</tex>.

Рассмотрим вспомогательную программу:
<tex> U(i, x) </tex> {{---}} универсальная функция
<tex>g_{i,x}(y):</tex>
'''if''' <tex>U(i, x)</tex> == 1 <font color=green> // если i (где i - это программа), на входе x выдает 1. </font>
'''return''' <tex>p_X(y)</tex>
'''else'''
'''while''' ''true''
Нетрудно понять, что в разумной модели вычислений номер этой программы можно вычислить по данным <tex>i</tex> и <tex>x</tex>. Значит, можно рассмотреть такую программу:
<tex>US(\langle i, x \rangle )</tex>
'''return''' <tex>p_A ( g_{i,x} ) </tex>

Заметим, что
<tex>
L(g_{i,x}) = \begin{cases}
X, & U(i, x) = 1; \\
\varnothing, & U(i, x) \neq 1; \\
\end{cases}
</tex>

Исключение пустого множества нам нужно чтобы различать <tex> X</tex> и пустое.
Следовательно, <br/> <tex>
US(\langle i, x \rangle ) = p_A(g_{i,x}) = \begin{cases}
p_A(p_X), & U(i, x) = 1; \\
p_A(p_\varnothing ), & U(i, x) \neq 1; \\
\end{cases} = \begin{cases}
1, & U(i, x) = 1; \\
0, & U(i, x) \neq 1; \\
\end{cases}
</tex> {{---}} программа, разрешающая [[Универсальная функция | универсальное множество]]. Получили противоречие.
}}

== См. также ==
* [[Теорема о рекурсии]]
* [[Теорема Райса-Шапиро]]

== Источники информации ==
* [https://en.wikipedia.org/wiki/Rice%27s_theorem Wikipedia — Rice's theorem]
* Rice, H. G. "Classes of Recursively Enumerable Sets and Their Decision Problems." Trans. Amer. Math. Soc. 74, 358-366, 1953.
* Хопкрофт Д., Мотванн Р., Ульманн Д. Введение в теорию автоматов, языков и вычислений страница 397.
[[Категория: Теория вычислимости]]
[[Категория: Теория формальных языков]]

Свойства перечислимых языков. Теорема Успенского-Райса

2014-12-14T10:02:07Z

217.118.78.38: /* Свойства языков */

== Свойства языков ==

Рассмотрим множество всех [[Перечислимые_языки|перечислимых]] языков <tex> \mathrm {RE} </tex>.
{{Определение
|definition='''Свойством языков''' (англ. ''property of languages'') называется множество <tex> A \subset \mathrm {RE} </tex>.
}}
'''Примеры свойств''':
* Язык должен содержать слово ''hello''.
* Язык должен содержать хотя бы одно простое число.

{{Определение
|definition=Свойство называется '''тривиальным''' (англ. ''trivial''), если <tex> A = \varnothing </tex> или <tex> A = \mathrm {RE} </tex>.
}}
Псевдокод для <tex> A = \varnothing </tex>
<tex>p_A(p_X)</tex>
'''return <tex>L(p_X) \in A</tex>

Псевдокод для <tex> A = \mathrm {RE} </tex>.
<tex>p(A)</tex>
'''return''' ''true''
{{Определение
|definition='''Язык свойства''' (англ. ''language of property'') <tex> A </tex> {{---}} множество программ, языки которых обладают этим свойством: <tex>L(A) \overset{\underset{\mathrm{def}}{}}{=} \lbrace p \mid L(p) \in A \rbrace </tex>.
}}
Пример.
Пусть <tex>p_X</tex> {{---}} разрешитель некоторого языка
p(<tex>p_X</tex>)
'''return''' <tex>p_X</tex>('hello')
{{Определение
|definition=Свойство <tex> A </tex> называется '''разрешимым''' (англ. ''recursive''), если <tex>L(A) </tex> является [[Разрешимые_(рекурсивные)_языки|разрешимым]].
}}

== Теорема Успенского-Райса ==
{{Теорема
|statement=
Язык никакого нетривиального свойства не является разрешимым.
|proof=
Приведём доказательство от противного.

Предположим, что <tex>A</tex> разрешимо и нетривиально, <tex>p_A</tex> {{---}} программа, разрешающая <tex>A</tex>.

Не умаляя общности, можно считать, что <tex>\varnothing \notin A</tex> (в противном случае перейдём к <tex> \mathrm {RE} \setminus A</tex>, которое также будет разрешимым и нетривиальным, так как <tex> \mathrm {RE} \setminus A \neq \varnothing </tex> и <tex> \mathrm {RE} \setminus A \neq \mathrm {RE} ) </tex>.

Поскольку <tex>A</tex> непусто, то найдётся перечислимый язык <tex>X \in A</tex>. Пусть <tex>p_X</tex> {{---}} полуразрешитель <tex>X</tex>.

Рассмотрим вспомогательную программу:
<tex> U(i, x) </tex> {{---}} универсальная функция
<tex>g_{i,x}(y):</tex>
'''if''' <tex>U(i, x)</tex> == 1 <font color=green> // если i (где i - это программа), на входе x выдает 1. </font>
'''return''' <tex>p_X(y)</tex>
'''else'''
'''while''' ''true''
Нетрудно понять, что в разумной модели вычислений номер этой программы можно вычислить по данным <tex>i</tex> и <tex>x</tex>. Значит, можно рассмотреть такую программу:
<tex>US(\langle i, x \rangle )</tex>
'''return''' <tex>p_A ( g_{i,x} ) </tex>

Заметим, что
<tex>
L(g_{i,x}) = \begin{cases}
X, & U(i, x) = 1; \\
\varnothing, & U(i, x) \neq 1; \\
\end{cases}
</tex>

Исключение пустого множества нам нужно чтобы различать <tex> X</tex> и пустое.
Следовательно, <br/> <tex>
US(\langle i, x \rangle ) = p_A(g_{i,x}) = \begin{cases}
p_A(p_X), & U(i, x) = 1; \\
p_A(p_\varnothing ), & U(i, x) \neq 1; \\
\end{cases} = \begin{cases}
1, & U(i, x) = 1; \\
0, & U(i, x) \neq 1; \\
\end{cases}
</tex> {{---}} программа, разрешающая [[Универсальная функция | универсальное множество]]. Получили противоречие.
}}

== См. также ==
* [[Теорема о рекурсии]]
* [[Теорема Райса-Шапиро]]

== Источники информации ==
* [https://en.wikipedia.org/wiki/Rice%27s_theorem Wikipedia — Rice's theorem]
* Rice, H. G. "Classes of Recursively Enumerable Sets and Their Decision Problems." Trans. Amer. Math. Soc. 74, 358-366, 1953.
* Хопкрофт Д., Мотванн Р., Ульманн Д. Введение в теорию автоматов, языков и вычислений страница 397.
[[Категория: Теория вычислимости]]
[[Категория: Теория формальных языков]]

Свойства перечислимых языков. Теорема Успенского-Райса

2014-12-14T09:59:06Z

217.118.78.38: /* Свойства языков */

== Свойства языков ==

Рассмотрим множество всех [[Перечислимые_языки|перечислимых]] языков <tex> \mathrm {RE} </tex>.
{{Определение
|definition='''Свойством языков''' (англ. ''property of languages'') называется множество <tex> A \subset \mathrm {RE} </tex>.
}}
'''Примеры свойств''':
* Язык должен содержать слово ''hello''.
* Язык должен содержать хотя бы одно простое число.

{{Определение
|definition=Свойство называется '''тривиальным''' (англ. ''trivial''), если <tex> A = \varnothing </tex> или <tex> A = \mathrm {RE} </tex>.
}}
Псевдокод для <tex> A = \varnothing </tex>
p_A(p_X)
'''return <tex>L(p_X) \in A</tex>

Псевдокод для <tex> A = \mathrm {RE} </tex>.
<tex>p(A)</tex>
'''return''' ''true''
{{Определение
|definition='''Язык свойства''' (англ. ''language of property'') <tex> A </tex> {{---}} множество программ, языки которых обладают этим свойством: <tex>L(A) \overset{\underset{\mathrm{def}}{}}{=} \lbrace p \mid L(p) \in A \rbrace </tex>.
}}
Пример.
Пусть <tex>p_X</tex> {{---}} разрешитель некоторого языка
p(<tex>p_X</tex>)
'''return''' <tex>p_X</tex>('hello')
{{Определение
|definition=Свойство <tex> A </tex> называется '''разрешимым''' (англ. ''recursive''), если <tex>L(A) </tex> является [[Разрешимые_(рекурсивные)_языки|разрешимым]].
}}

== Теорема Успенского-Райса ==
{{Теорема
|statement=
Язык никакого нетривиального свойства не является разрешимым.
|proof=
Приведём доказательство от противного.

Предположим, что <tex>A</tex> разрешимо и нетривиально, <tex>p_A</tex> {{---}} программа, разрешающая <tex>A</tex>.

Не умаляя общности, можно считать, что <tex>\varnothing \notin A</tex> (в противном случае перейдём к <tex> \mathrm {RE} \setminus A</tex>, которое также будет разрешимым и нетривиальным, так как <tex> \mathrm {RE} \setminus A \neq \varnothing </tex> и <tex> \mathrm {RE} \setminus A \neq \mathrm {RE} ) </tex>.

Поскольку <tex>A</tex> непусто, то найдётся перечислимый язык <tex>X \in A</tex>. Пусть <tex>p_X</tex> {{---}} полуразрешитель <tex>X</tex>.

Рассмотрим вспомогательную программу:
<tex> U(i, x) </tex> {{---}} универсальная функция
<tex>g_{i,x}(y):</tex>
'''if''' <tex>U(i, x)</tex> == 1 <font color=green> // если i (где i - это программа), на входе x выдает 1. </font>
'''return''' <tex>p_X(y)</tex>
'''else'''
'''while''' ''true''
Нетрудно понять, что в разумной модели вычислений номер этой программы можно вычислить по данным <tex>i</tex> и <tex>x</tex>. Значит, можно рассмотреть такую программу:
<tex>US(\langle i, x \rangle )</tex>
'''return''' <tex>p_A ( g_{i,x} ) </tex>

Заметим, что
<tex>
L(g_{i,x}) = \begin{cases}
X, & U(i, x) = 1; \\
\varnothing, & U(i, x) \neq 1; \\
\end{cases}
</tex>

Исключение пустого множества нам нужно чтобы различать <tex> X</tex> и пустое.
Следовательно, <br/> <tex>
US(\langle i, x \rangle ) = p_A(g_{i,x}) = \begin{cases}
p_A(p_X), & U(i, x) = 1; \\
p_A(p_\varnothing ), & U(i, x) \neq 1; \\
\end{cases} = \begin{cases}
1, & U(i, x) = 1; \\
0, & U(i, x) \neq 1; \\
\end{cases}
</tex> {{---}} программа, разрешающая [[Универсальная функция | универсальное множество]]. Получили противоречие.
}}

== См. также ==
* [[Теорема о рекурсии]]
* [[Теорема Райса-Шапиро]]

== Источники информации ==
* [https://en.wikipedia.org/wiki/Rice%27s_theorem Wikipedia — Rice's theorem]
* Rice, H. G. "Classes of Recursively Enumerable Sets and Their Decision Problems." Trans. Amer. Math. Soc. 74, 358-366, 1953.
* Хопкрофт Д., Мотванн Р., Ульманн Д. Введение в теорию автоматов, языков и вычислений страница 397.
[[Категория: Теория вычислимости]]
[[Категория: Теория формальных языков]]

Свойства перечислимых языков. Теорема Успенского-Райса

2014-12-14T09:54:46Z

217.118.78.38: /* Теорема Успенского-Райса */

== Свойства языков ==

Рассмотрим множество всех [[Перечислимые_языки|перечислимых]] языков <tex> \mathrm {RE} </tex>.
{{Определение
|definition='''Свойством языков''' (англ. ''property of languages'') называется множество <tex> A \subset \mathrm {RE} </tex>.
}}
'''Примеры свойств''':
* Язык должен содержать слово ''hello''.
* Язык должен содержать хотя бы одно простое число.

{{Определение
|definition=Свойство называется '''тривиальным''' (англ. ''trivial''), если <tex> A = \varnothing </tex> или <tex> A = \mathrm {RE} </tex>.
}}
Псевдокод для <tex> A = \varnothing </tex>
p_A(p_X)
'''return L(p_X) \in A

Псевдокод для <tex> A = \mathrm {RE} </tex>.
p(A)
'''return''' ''true''
{{Определение
|definition='''Язык свойства''' (англ. ''language of property'') <tex> A </tex> {{---}} множество программ, языки которых обладают этим свойством: <tex>L(A) \overset{\underset{\mathrm{def}}{}}{=} \lbrace p \mid L(p) \in A \rbrace </tex>.
}}
Пример.
Пусть <tex>p_X</tex> {{---}} разрешитель некоторого языка
p(<tex>p_X</tex>)
'''return''' <tex>p_X</tex>('hello')
{{Определение
|definition=Свойство <tex> A </tex> называется '''разрешимым''' (англ. ''recursive''), если <tex>L(A) </tex> является [[Разрешимые_(рекурсивные)_языки|разрешимым]].
}}

== Теорема Успенского-Райса ==
{{Теорема
|statement=
Язык никакого нетривиального свойства не является разрешимым.
|proof=
Приведём доказательство от противного.

Предположим, что <tex>A</tex> разрешимо и нетривиально, <tex>p_A</tex> {{---}} программа, разрешающая <tex>A</tex>.

Не умаляя общности, можно считать, что <tex>\varnothing \notin A</tex> (в противном случае перейдём к <tex> \mathrm {RE} \setminus A</tex>, которое также будет разрешимым и нетривиальным, так как <tex> \mathrm {RE} \setminus A \neq \varnothing </tex> и <tex> \mathrm {RE} \setminus A \neq \mathrm {RE} ) </tex>.

Поскольку <tex>A</tex> непусто, то найдётся перечислимый язык <tex>X \in A</tex>. Пусть <tex>p_X</tex> {{---}} полуразрешитель <tex>X</tex>.

Рассмотрим вспомогательную программу:
<tex> U(i, x) </tex> {{---}} универсальная функция
<tex>g_{i,x}(y):</tex>
'''if''' <tex>U(i, x)</tex> == 1 <font color=green> // если i (где i - это программа), на входе x выдает 1. </font>
'''return''' <tex>p_X(y)</tex>
'''else'''
'''while''' ''true''
Нетрудно понять, что в разумной модели вычислений номер этой программы можно вычислить по данным <tex>i</tex> и <tex>x</tex>. Значит, можно рассмотреть такую программу:
<tex>US(\langle i, x \rangle )</tex>
'''return''' <tex>p_A ( g_{i,x} ) </tex>

Заметим, что
<tex>
L(g_{i,x}) = \begin{cases}
X, & U(i, x) = 1; \\
\varnothing, & U(i, x) \neq 1; \\
\end{cases}
</tex>

Исключение пустого множества нам нужно чтобы различать <tex> X</tex> и пустое.
Следовательно, <br/> <tex>
US(\langle i, x \rangle ) = p_A(g_{i,x}) = \begin{cases}
p_A(p_X), & U(i, x) = 1; \\
p_A(p_\varnothing ), & U(i, x) \neq 1; \\
\end{cases} = \begin{cases}
1, & U(i, x) = 1; \\
0, & U(i, x) \neq 1; \\
\end{cases}
</tex> {{---}} программа, разрешающая [[Универсальная функция | универсальное множество]]. Получили противоречие.
}}

== См. также ==
* [[Теорема о рекурсии]]
* [[Теорема Райса-Шапиро]]

== Источники информации ==
* [https://en.wikipedia.org/wiki/Rice%27s_theorem Wikipedia — Rice's theorem]
* Rice, H. G. "Classes of Recursively Enumerable Sets and Their Decision Problems." Trans. Amer. Math. Soc. 74, 358-366, 1953.
* Хопкрофт Д., Мотванн Р., Ульманн Д. Введение в теорию автоматов, языков и вычислений страница 397.
[[Категория: Теория вычислимости]]
[[Категория: Теория формальных языков]]

Свойства перечислимых языков. Теорема Успенского-Райса

2014-12-14T09:53:17Z

217.118.78.38: /* Теорема Успенского-Райса */

== Свойства языков ==

Рассмотрим множество всех [[Перечислимые_языки|перечислимых]] языков <tex> \mathrm {RE} </tex>.
{{Определение
|definition='''Свойством языков''' (англ. ''property of languages'') называется множество <tex> A \subset \mathrm {RE} </tex>.
}}
'''Примеры свойств''':
* Язык должен содержать слово ''hello''.
* Язык должен содержать хотя бы одно простое число.

{{Определение
|definition=Свойство называется '''тривиальным''' (англ. ''trivial''), если <tex> A = \varnothing </tex> или <tex> A = \mathrm {RE} </tex>.
}}
Псевдокод для <tex> A = \varnothing </tex>
p_A(p_X)
'''return L(p_X) \in A

Псевдокод для <tex> A = \mathrm {RE} </tex>.
p(A)
'''return''' ''true''
{{Определение
|definition='''Язык свойства''' (англ. ''language of property'') <tex> A </tex> {{---}} множество программ, языки которых обладают этим свойством: <tex>L(A) \overset{\underset{\mathrm{def}}{}}{=} \lbrace p \mid L(p) \in A \rbrace </tex>.
}}
Пример.
Пусть <tex>p_X</tex> {{---}} разрешитель некоторого языка
p(<tex>p_X</tex>)
'''return''' <tex>p_X</tex>('hello')
{{Определение
|definition=Свойство <tex> A </tex> называется '''разрешимым''' (англ. ''recursive''), если <tex>L(A) </tex> является [[Разрешимые_(рекурсивные)_языки|разрешимым]].
}}

== Теорема Успенского-Райса ==
{{Теорема
|statement=
Язык никакого нетривиального свойства не является разрешимым.
|proof=
Приведём доказательство от противного.

Предположим, что <tex>A</tex> разрешимо и нетривиально, <tex>p_A</tex> {{---}} программа, разрешающая <tex>A</tex>.

Не умаляя общности, можно считать, что <tex>\varnothing \notin A</tex> (в противном случае перейдём к <tex> \mathrm {RE} \setminus A</tex>, которое также будет разрешимым и нетривиальным, так как <tex> \mathrm {RE} \setminus A \neq \varnothing </tex> и <tex> \mathrm {RE} \setminus A \neq \mathrm {RE} ) </tex>.

Поскольку <tex>A</tex> непусто, то найдётся перечислимый язык <tex>X \in A</tex>. Пусть <tex>p_X</tex> {{---}} полуразрешитель <tex>X</tex>.

Рассмотрим вспомогательную программу:
<tex> U(i, x) </tex> {{---}} универсальная функция
<tex>g_{i,x}(y):</tex>
'''if''' U(i, x) == 1 <font color=green> // если i (где i - это программа), на входе x выдает 1. </font>
'''return''' <tex>p_X(y)</tex>
'''else'''
'''while''' ''true''
Нетрудно понять, что в разумной модели вычислений номер этой программы можно вычислить по данным <tex>i</tex> и <tex>x</tex>. Значит, можно рассмотреть такую программу:
<tex>US(\langle i, x \rangle )</tex>
'''return''' <tex>p_A ( g_{i,x} ) </tex>

Заметим, что
<tex>
L(g_{i,x}) = \begin{cases}
X, & U(i, x) = 1; \\
\varnothing, & U(i, x) \neq 1; \\
\end{cases}
</tex>

Исключение пустого множества нам нужно чтобы различать <tex> X</tex> и пустое.
Следовательно, <br/> <tex>
US(\langle i, x \rangle ) = p_A(g_{i,x}) = \begin{cases}
p_A(p_X), & U(i, x) = 1; \\
p_A(p_\varnothing ), & U(i, x) \neq 1; \\
\end{cases} = \begin{cases}
1, & U(i, x) = 1; \\
0, & U(i, x) \neq 1; \\
\end{cases}
</tex> {{---}} программа, разрешающая [[Универсальная функция | универсальное множество]]. Получили противоречие.
}}

== См. также ==
* [[Теорема о рекурсии]]
* [[Теорема Райса-Шапиро]]

== Источники информации ==
* [https://en.wikipedia.org/wiki/Rice%27s_theorem Wikipedia — Rice's theorem]
* Rice, H. G. "Classes of Recursively Enumerable Sets and Their Decision Problems." Trans. Amer. Math. Soc. 74, 358-366, 1953.
* Хопкрофт Д., Мотванн Р., Ульманн Д. Введение в теорию автоматов, языков и вычислений страница 397.
[[Категория: Теория вычислимости]]
[[Категория: Теория формальных языков]]

Свойства перечислимых языков. Теорема Успенского-Райса

2014-12-14T09:52:41Z

217.118.78.38: /* Теорема Успенского-Райса */

== Свойства языков ==

Рассмотрим множество всех [[Перечислимые_языки|перечислимых]] языков <tex> \mathrm {RE} </tex>.
{{Определение
|definition='''Свойством языков''' (англ. ''property of languages'') называется множество <tex> A \subset \mathrm {RE} </tex>.
}}
'''Примеры свойств''':
* Язык должен содержать слово ''hello''.
* Язык должен содержать хотя бы одно простое число.

{{Определение
|definition=Свойство называется '''тривиальным''' (англ. ''trivial''), если <tex> A = \varnothing </tex> или <tex> A = \mathrm {RE} </tex>.
}}
Псевдокод для <tex> A = \varnothing </tex>
p_A(p_X)
'''return L(p_X) \in A

Псевдокод для <tex> A = \mathrm {RE} </tex>.
p(A)
'''return''' ''true''
{{Определение
|definition='''Язык свойства''' (англ. ''language of property'') <tex> A </tex> {{---}} множество программ, языки которых обладают этим свойством: <tex>L(A) \overset{\underset{\mathrm{def}}{}}{=} \lbrace p \mid L(p) \in A \rbrace </tex>.
}}
Пример.
Пусть <tex>p_X</tex> {{---}} разрешитель некоторого языка
p(<tex>p_X</tex>)
'''return''' <tex>p_X</tex>('hello')
{{Определение
|definition=Свойство <tex> A </tex> называется '''разрешимым''' (англ. ''recursive''), если <tex>L(A) </tex> является [[Разрешимые_(рекурсивные)_языки|разрешимым]].
}}

== Теорема Успенского-Райса ==
{{Теорема
|statement=
Язык никакого нетривиального свойства не является разрешимым.
|proof=
Приведём доказательство от противного.

Предположим, что <tex>A</tex> разрешимо и нетривиально, <tex>p_A</tex> {{---}} программа, разрешающая <tex>A</tex>.

Не умаляя общности, можно считать, что <tex>\varnothing \notin A</tex> (в противном случае перейдём к <tex> \mathrm {RE} \setminus A</tex>, которое также будет разрешимым и нетривиальным, так как <tex> \mathrm {RE} \setminus A \neq \varnothing </tex> и <tex> \mathrm {RE} \setminus A \neq \mathrm {RE} ) </tex>.

Поскольку <tex>A</tex> непусто, то найдётся перечислимый язык <tex>X \in A</tex>. Пусть <tex>p_X</tex> {{---}} полуразрешитель <tex>X</tex>.

Рассмотрим вспомогательную программу:
<tex> U(i, x) </tex> {{---}} универсальная функция
<tex>g_{i,x}(y):</tex>
'''if''' U(i, x) == 1 <font color=green> // если i (где i - это программа), на входе x выдает 1
'''return''' <tex>p_X(y)</tex>
'''else'''
'''while''' ''true''
Нетрудно понять, что в разумной модели вычислений номер этой программы можно вычислить по данным <tex>i</tex> и <tex>x</tex>. Значит, можно рассмотреть такую программу:
<tex>US(\langle i, x \rangle )</tex>
'''return''' <tex>p_A ( g_{i,x} ) </tex>

Заметим, что
<tex>
L(g_{i,x}) = \begin{cases}
X, & U(i, x) = 1; \\
\varnothing, & U(i, x) \neq 1; \\
\end{cases}
</tex>

Исключение пустого множества нам нужно чтобы различать <tex> X</tex> и пустое.
Следовательно, <br/> <tex>
US(\langle i, x \rangle ) = p_A(g_{i,x}) = \begin{cases}
p_A(p_X), & U(i, x) = 1; \\
p_A(p_\varnothing ), & U(i, x) \neq 1; \\
\end{cases} = \begin{cases}
1, & U(i, x) = 1; \\
0, & U(i, x) \neq 1; \\
\end{cases}
</tex> {{---}} программа, разрешающая [[Универсальная функция | универсальное множество]]. Получили противоречие.
}}

== См. также ==
* [[Теорема о рекурсии]]
* [[Теорема Райса-Шапиро]]

== Источники информации ==
* [https://en.wikipedia.org/wiki/Rice%27s_theorem Wikipedia — Rice's theorem]
* Rice, H. G. "Classes of Recursively Enumerable Sets and Their Decision Problems." Trans. Amer. Math. Soc. 74, 358-366, 1953.
* Хопкрофт Д., Мотванн Р., Ульманн Д. Введение в теорию автоматов, языков и вычислений страница 397.
[[Категория: Теория вычислимости]]
[[Категория: Теория формальных языков]]

Свойства перечислимых языков. Теорема Успенского-Райса

2014-12-14T09:48:58Z

217.118.78.38: /* Теорема Успенского-Райса */

== Свойства языков ==

Рассмотрим множество всех [[Перечислимые_языки|перечислимых]] языков <tex> \mathrm {RE} </tex>.
{{Определение
|definition='''Свойством языков''' (англ. ''property of languages'') называется множество <tex> A \subset \mathrm {RE} </tex>.
}}
'''Примеры свойств''':
* Язык должен содержать слово ''hello''.
* Язык должен содержать хотя бы одно простое число.

{{Определение
|definition=Свойство называется '''тривиальным''' (англ. ''trivial''), если <tex> A = \varnothing </tex> или <tex> A = \mathrm {RE} </tex>.
}}
Псевдокод для <tex> A = \varnothing </tex>
p_A(p_X)
'''return L(p_X) \in A

Псевдокод для <tex> A = \mathrm {RE} </tex>.
p(A)
'''return''' ''true''
{{Определение
|definition='''Язык свойства''' (англ. ''language of property'') <tex> A </tex> {{---}} множество программ, языки которых обладают этим свойством: <tex>L(A) \overset{\underset{\mathrm{def}}{}}{=} \lbrace p \mid L(p) \in A \rbrace </tex>.
}}
Пример.
Пусть <tex>p_X</tex> {{---}} разрешитель некоторого языка
p(<tex>p_X</tex>)
'''return''' <tex>p_X</tex>('hello')
{{Определение
|definition=Свойство <tex> A </tex> называется '''разрешимым''' (англ. ''recursive''), если <tex>L(A) </tex> является [[Разрешимые_(рекурсивные)_языки|разрешимым]].
}}

== Теорема Успенского-Райса ==
{{Теорема
|statement=
Язык никакого нетривиального свойства не является разрешимым.
|proof=
Приведём доказательство от противного.

Предположим, что <tex>A</tex> разрешимо и нетривиально, <tex>p_A</tex> {{---}} программа, разрешающая <tex>A</tex>.

Не умаляя общности, можно считать, что <tex>\varnothing \notin A</tex> (в противном случае перейдём к <tex> \mathrm {RE} \setminus A</tex>, которое также будет разрешимым и нетривиальным, так как <tex> \mathrm {RE} \setminus A \neq \varnothing </tex> и <tex> \mathrm {RE} \setminus A \neq \mathrm {RE} ) </tex>.

Поскольку <tex>A</tex> непусто, то найдётся перечислимый язык <tex>X \in A</tex>. Пусть <tex>p_X</tex> {{---}} полуразрешитель <tex>X</tex>.

Рассмотрим вспомогательную программу:
<tex> U(i, x) </tex> {{---}} универсальная функция
<tex>g_{i,x}(y):</tex>
'''if''' U(i, x) == 1 //если i (где i - это программа), на входе x выдает 1
'''return''' <tex>p_X(y)</tex>
'''else'''
'''while''' ''true''
Нетрудно понять, что в разумной модели вычислений номер этой программы можно вычислить по данным <tex>i</tex> и <tex>x</tex>. Значит, можно рассмотреть такую программу:
<tex>US(\langle i, x \rangle )</tex>
'''return''' <tex>p_A ( g_{i,x} ) </tex>

Заметим, что
<tex>
L(g_{i,x}) = \begin{cases}
X, & U(i, x) = 1; \\
\varnothing, & U(i, x) \neq 1; \\
\end{cases}
</tex>

Исключение пустого множества нам нужно чтобы различать <tex> X</tex> и пустое.
Следовательно, <br/> <tex>
US(\langle i, x \rangle ) = p_A(g_{i,x}) = \begin{cases}
p_A(p_X), & U(i, x) = 1; \\
p_A(p_\varnothing ), & U(i, x) \neq 1; \\
\end{cases} = \begin{cases}
1, & U(i, x) = 1; \\
0, & U(i, x) \neq 1; \\
\end{cases}
</tex> {{---}} программа, разрешающая [[Универсальная функция | универсальное множество]]. Получили противоречие.
}}

== См. также ==
* [[Теорема о рекурсии]]
* [[Теорема Райса-Шапиро]]

== Источники информации ==
* [https://en.wikipedia.org/wiki/Rice%27s_theorem Wikipedia — Rice's theorem]
* Rice, H. G. "Classes of Recursively Enumerable Sets and Their Decision Problems." Trans. Amer. Math. Soc. 74, 358-366, 1953.
* Хопкрофт Д., Мотванн Р., Ульманн Д. Введение в теорию автоматов, языков и вычислений страница 397.
[[Категория: Теория вычислимости]]
[[Категория: Теория формальных языков]]

Свойства перечислимых языков. Теорема Успенского-Райса

2014-12-14T09:06:19Z

217.118.78.38: /* Теорема Успенского-Райса */

== Свойства языков ==

Рассмотрим множество всех [[Перечислимые_языки|перечислимых]] языков <tex> \mathrm {RE} </tex>.
{{Определение
|definition='''Свойством языков''' (англ. ''property of languages'') называется множество <tex> A \subset \mathrm {RE} </tex>.
}}
'''Примеры свойств''':
* Язык должен содержать слово ''hello''.
* Язык должен содержать хотя бы одно простое число.

{{Определение
|definition=Свойство называется '''тривиальным''' (англ. ''trivial''), если <tex> A = \varnothing </tex> или <tex> A = \mathrm {RE} </tex>.
}}
Псевдокод для <tex> A = \varnothing </tex>
p_A(p_X)
'''return L(p_X) \in A

Псевдокод для <tex> A = \mathrm {RE} </tex>.
p(A)
'''return''' ''true''
{{Определение
|definition='''Язык свойства''' (англ. ''language of property'') <tex> A </tex> {{---}} множество программ, языки которых обладают этим свойством: <tex>L(A) \overset{\underset{\mathrm{def}}{}}{=} \lbrace p \mid L(p) \in A \rbrace </tex>.
}}
Пример.
Пусть <tex>p_X</tex> {{---}} разрешитель некоторого языка
p(<tex>p_X</tex>)
'''return''' <tex>p_X</tex>('hello')
{{Определение
|definition=Свойство <tex> A </tex> называется '''разрешимым''' (англ. ''recursive''), если <tex>L(A) </tex> является [[Разрешимые_(рекурсивные)_языки|разрешимым]].
}}

== Теорема Успенского-Райса ==
{{Теорема
|statement=
Язык никакого нетривиального свойства не является разрешимым.
|proof=
Приведём доказательство от противного.

Предположим, что <tex>A</tex> разрешимо и нетривиально, <tex>p_A</tex> {{---}} программа, разрешающая <tex>A</tex>.

Не умаляя общности, можно считать, что <tex>\varnothing \notin A</tex> (в противном случае перейдём к <tex> \mathrm {RE} \setminus A</tex>, которое также будет разрешимым и нетривиальным, так как <tex> \mathrm {RE} \setminus A \neq \varnothing </tex> и <tex> \mathrm {RE} \setminus A \neq \mathrm {RE} ) </tex>.

Поскольку <tex>A</tex> непусто, то найдётся перечислимый язык <tex>X \in A</tex>. Пусть <tex>p_X</tex> {{---}} полуразрешитель <tex>X</tex>.

Рассмотрим вспомогательную программу:
<tex> U(i, x) </tex> {{---}} универсальная функция
<tex>g_{i,x}(y):</tex>
'''if''' U(i, x) == 1 //если i (где i - это программа), на входе x выдает 1
'''return''' <tex>p_X(y)</tex>
'''else'''
'''while''' ''true''
Нетрудно понять, что в разумной модели вычислений номер этой программы можно вычислить по данным <tex>i</tex> и <tex>x</tex>. Значит, можно рассмотреть такую программу:
<tex>US(\langle i, x \rangle )</tex>
'''return''' <tex>p_A ( g_{i,x} ) </tex>

Заметим, что
<tex>
L(g_{i,x}) = \begin{cases}
X, & U(i, x) = 1; \\
\varnothing, & U(i, x) \neq 1; \\
\end{cases}
</tex>

Исключение пустого множества нам нужно чтобы различать <tex> X</tex> и пустое.
Следовательно, <br/> <tex>
US(\langle i, x \rangle ) = p_A(g_{i,x}) = \begin{cases}
p_A(p_X), & U(i, x) = 1; \\
p_A(p_\varnothing ), & U(i, x) \neq 1; \\
\end{cases} = \begin{cases}
1, & U(i, x) = 1; \\
0, & U(i, x) \neq 1; \\
\end{cases}
</tex> {{---}} программа, разрешающая [[Множества | универсальное множество]]. Получили противоречие.
}}

== См. также ==
* [[Теорема о рекурсии]]
* [[Теорема Райса-Шапиро]]

== Источники информации ==
* [https://en.wikipedia.org/wiki/Rice%27s_theorem Wikipedia — Rice's theorem]
* Rice, H. G. "Classes of Recursively Enumerable Sets and Their Decision Problems." Trans. Amer. Math. Soc. 74, 358-366, 1953.
* Хопкрофт Д., Мотванн Р., Ульманн Д. Введение в теорию автоматов, языков и вычислений страница 397.
[[Категория: Теория вычислимости]]
[[Категория: Теория формальных языков]]

Свойства перечислимых языков. Теорема Успенского-Райса

2014-12-14T09:03:55Z

217.118.78.38: /* Теорема Успенского-Райса */

== Свойства языков ==

Рассмотрим множество всех [[Перечислимые_языки|перечислимых]] языков <tex> \mathrm {RE} </tex>.
{{Определение
|definition='''Свойством языков''' (англ. ''property of languages'') называется множество <tex> A \subset \mathrm {RE} </tex>.
}}
'''Примеры свойств''':
* Язык должен содержать слово ''hello''.
* Язык должен содержать хотя бы одно простое число.

{{Определение
|definition=Свойство называется '''тривиальным''' (англ. ''trivial''), если <tex> A = \varnothing </tex> или <tex> A = \mathrm {RE} </tex>.
}}
Псевдокод для <tex> A = \varnothing </tex>
p_A(p_X)
'''return L(p_X) \in A

Псевдокод для <tex> A = \mathrm {RE} </tex>.
p(A)
'''return''' ''true''
{{Определение
|definition='''Язык свойства''' (англ. ''language of property'') <tex> A </tex> {{---}} множество программ, языки которых обладают этим свойством: <tex>L(A) \overset{\underset{\mathrm{def}}{}}{=} \lbrace p \mid L(p) \in A \rbrace </tex>.
}}
Пример.
Пусть <tex>p_X</tex> {{---}} разрешитель некоторого языка
p(<tex>p_X</tex>)
'''return''' <tex>p_X</tex>('hello')
{{Определение
|definition=Свойство <tex> A </tex> называется '''разрешимым''' (англ. ''recursive''), если <tex>L(A) </tex> является [[Разрешимые_(рекурсивные)_языки|разрешимым]].
}}

== Теорема Успенского-Райса ==
{{Теорема
|statement=
Язык никакого нетривиального свойства не является разрешимым.
|proof=
Приведём доказательство от противного.

Предположим, что <tex>A</tex> разрешимо и нетривиально, <tex>p_A</tex> {{---}} программа, разрешающая <tex>A</tex>.

Не умаляя общности, можно считать, что <tex>\varnothing \notin A</tex> (в противном случае перейдём к <tex> \mathrm {RE} \setminus A</tex>, которое также будет разрешимым и нетривиальным, так как <tex> \mathrm {RE} \setminus A</tex> != <tex>\varnothing </tex> и <tex> \mathrm {RE} \setminus A</tex> != <tex>\mathrm {RE} ) </tex>.

Поскольку <tex>A</tex> непусто, то найдётся перечислимый язык <tex>X \in A</tex>. Пусть <tex>p_X</tex> {{---}} полуразрешитель <tex>X</tex>.

Рассмотрим вспомогательную программу:
<tex> U(i, x) </tex> {{---}} универсальная функция
<tex>g_{i,x}(y):</tex>
'''if''' U(i, x) == 1 //если i (где i - это программа), на входе x выдает 1
'''return''' <tex>p_X(y)</tex>
'''else'''
'''while''' ''true''
Нетрудно понять, что в разумной модели вычислений номер этой программы можно вычислить по данным <tex>i</tex> и <tex>x</tex>. Значит, можно рассмотреть такую программу:
<tex>US(\langle i, x \rangle )</tex>
'''return''' <tex>p_A ( g_{i,x} ) </tex>

Заметим, что
<tex>
L(g_{i,x}) = \begin{cases}
X, & U(i, x) = 1; \\
\varnothing, & U(i, x) \neq 1; \\
\end{cases}
</tex>

Исключение пустого множества нам нужно чтобы различать <tex> X</tex> и пустое.
Следовательно, <br/> <tex>
US(\langle i, x \rangle ) = p_A(g_{i,x}) = \begin{cases}
p_A(p_X), & U(i, x) = 1; \\
p_A(p_\varnothing ), & U(i, x) \neq 1; \\
\end{cases} = \begin{cases}
1, & U(i, x) = 1; \\
0, & U(i, x) \neq 1; \\
\end{cases}
</tex> {{---}} программа, разрешающая [[Множества | универсальное множество]]. Получили противоречие.
}}

== См. также ==
* [[Теорема о рекурсии]]
* [[Теорема Райса-Шапиро]]

== Источники информации ==
* [https://en.wikipedia.org/wiki/Rice%27s_theorem Wikipedia — Rice's theorem]
* Rice, H. G. "Classes of Recursively Enumerable Sets and Their Decision Problems." Trans. Amer. Math. Soc. 74, 358-366, 1953.
* Хопкрофт Д., Мотванн Р., Ульманн Д. Введение в теорию автоматов, языков и вычислений страница 397.
[[Категория: Теория вычислимости]]
[[Категория: Теория формальных языков]]

Свойства перечислимых языков. Теорема Успенского-Райса

2014-12-14T09:03:07Z

217.118.78.38: /* Теорема Успенского-Райса */

== Свойства языков ==

Рассмотрим множество всех [[Перечислимые_языки|перечислимых]] языков <tex> \mathrm {RE} </tex>.
{{Определение
|definition='''Свойством языков''' (англ. ''property of languages'') называется множество <tex> A \subset \mathrm {RE} </tex>.
}}
'''Примеры свойств''':
* Язык должен содержать слово ''hello''.
* Язык должен содержать хотя бы одно простое число.

{{Определение
|definition=Свойство называется '''тривиальным''' (англ. ''trivial''), если <tex> A = \varnothing </tex> или <tex> A = \mathrm {RE} </tex>.
}}
Псевдокод для <tex> A = \varnothing </tex>
p_A(p_X)
'''return L(p_X) \in A

Псевдокод для <tex> A = \mathrm {RE} </tex>.
p(A)
'''return''' ''true''
{{Определение
|definition='''Язык свойства''' (англ. ''language of property'') <tex> A </tex> {{---}} множество программ, языки которых обладают этим свойством: <tex>L(A) \overset{\underset{\mathrm{def}}{}}{=} \lbrace p \mid L(p) \in A \rbrace </tex>.
}}
Пример.
Пусть <tex>p_X</tex> {{---}} разрешитель некоторого языка
p(<tex>p_X</tex>)
'''return''' <tex>p_X</tex>('hello')
{{Определение
|definition=Свойство <tex> A </tex> называется '''разрешимым''' (англ. ''recursive''), если <tex>L(A) </tex> является [[Разрешимые_(рекурсивные)_языки|разрешимым]].
}}

== Теорема Успенского-Райса ==
{{Теорема
|statement=
Язык никакого нетривиального свойства не является разрешимым.
|proof=
Приведём доказательство от противного.

Предположим, что <tex>A</tex> разрешимо и нетривиально, <tex>p_A</tex> {{---}} программа, разрешающая <tex>A</tex>.

Не умаляя общности, можно считать, что <tex>\varnothing \notin A</tex> (в противном случае перейдём к <tex> \mathrm {RE} \setminus A</tex>, которое также будет разрешимым и нетривиальным, так как <tex> \mathrm {RE} \setminus A</tex> != <tex>\varnothing </tex> и <tex> \mathrm {RE} \setminus A</tex> != <tex>\mathrm {RE} ) </tex>.

Поскольку <tex>A</tex> непусто, то найдётся перечислимый язык <tex>X \in A</tex>. Пусть <tex>p_X</tex> {{---}} полуразрешитель <tex>X</tex>.

Рассмотрим вспомогательную программу:
<tex> U(i, x) </tex> {{---}} универсальная функция
<tex>g_{i,x}(y):</tex>
'''if''' U(i, x) == 1 //если i (где i - это программа), на входе x выдает 1
'''return''' <tex>p_X(y)</tex>
'''else'''
'''while''' ''true''
Нетрудно понять, что в разумной модели вычислений номер этой программы можно вычислить по данным <tex>i</tex> и <tex>x</tex>. Значит, можно рассмотреть такую программу:
<tex>US(\langle i, x \rangle )</tex>
'''return''' <tex>p_A ( g_{i,x} ) </tex>

Заметим, что
<tex>
L(g_{i,x}) = \begin{cases}
X, & U(i, x) = 1; \\
\varnothing, & U(i, x) \neq 1; \\
\end{cases}
</tex>
Исключение пустого множества нам нужно чтобы различать <tex> X</tex> и пустое (при построении функции <tex>L(g_{i,x}))</tex>.
Следовательно, <br/> <tex>
US(\langle i, x \rangle ) = p_A(g_{i,x}) = \begin{cases}
p_A(p_X), & U(i, x) = 1; \\
p_A(p_\varnothing ), & U(i, x) \neq 1; \\
\end{cases} = \begin{cases}
1, & U(i, x) = 1; \\
0, & U(i, x) \neq 1; \\
\end{cases}
</tex> {{---}} программа, разрешающая [[Множества | универсальное множество]]. Получили противоречие.
}}

== См. также ==
* [[Теорема о рекурсии]]
* [[Теорема Райса-Шапиро]]

== Источники информации ==
* [https://en.wikipedia.org/wiki/Rice%27s_theorem Wikipedia — Rice's theorem]
* Rice, H. G. "Classes of Recursively Enumerable Sets and Their Decision Problems." Trans. Amer. Math. Soc. 74, 358-366, 1953.
* Хопкрофт Д., Мотванн Р., Ульманн Д. Введение в теорию автоматов, языков и вычислений страница 397.
[[Категория: Теория вычислимости]]
[[Категория: Теория формальных языков]]

Свойства перечислимых языков. Теорема Успенского-Райса

2014-12-14T08:58:36Z

217.118.78.38: /* Теорема Успенского-Райса */

== Свойства языков ==

Рассмотрим множество всех [[Перечислимые_языки|перечислимых]] языков <tex> \mathrm {RE} </tex>.
{{Определение
|definition='''Свойством языков''' (англ. ''property of languages'') называется множество <tex> A \subset \mathrm {RE} </tex>.
}}
'''Примеры свойств''':
* Язык должен содержать слово ''hello''.
* Язык должен содержать хотя бы одно простое число.

{{Определение
|definition=Свойство называется '''тривиальным''' (англ. ''trivial''), если <tex> A = \varnothing </tex> или <tex> A = \mathrm {RE} </tex>.
}}
Псевдокод для <tex> A = \varnothing </tex>
p_A(p_X)
'''return L(p_X) \in A

Псевдокод для <tex> A = \mathrm {RE} </tex>.
p(A)
'''return''' ''true''
{{Определение
|definition='''Язык свойства''' (англ. ''language of property'') <tex> A </tex> {{---}} множество программ, языки которых обладают этим свойством: <tex>L(A) \overset{\underset{\mathrm{def}}{}}{=} \lbrace p \mid L(p) \in A \rbrace </tex>.
}}
Пример.
Пусть <tex>p_X</tex> {{---}} разрешитель некоторого языка
p(<tex>p_X</tex>)
'''return''' <tex>p_X</tex>('hello')
{{Определение
|definition=Свойство <tex> A </tex> называется '''разрешимым''' (англ. ''recursive''), если <tex>L(A) </tex> является [[Разрешимые_(рекурсивные)_языки|разрешимым]].
}}

== Теорема Успенского-Райса ==
{{Теорема
|statement=
Язык никакого нетривиального свойства не является разрешимым.
|proof=
Приведём доказательство от противного.

Предположим, что <tex>A</tex> разрешимо и нетривиально, <tex>p_A</tex> {{---}} программа, разрешающая <tex>A</tex>.

Не умаляя общности, можно считать, что <tex>\varnothing \notin A</tex> (в противном случае перейдём к <tex> \mathrm {RE} \setminus A</tex>, которое также будет разрешимым и нетривиальным, так как <tex> \mathrm {RE} \setminus A</tex> != <tex>\varnothing </tex> и <tex> \mathrm {RE} \setminus A</tex> != <tex>\mathrm {RE} ) </tex>.

Поскольку <tex>A</tex> непусто, то найдётся перечислимый язык <tex>X \in A</tex>. Пусть <tex>p_X</tex> {{---}} полуразрешитель <tex>X</tex>.

Рассмотрим вспомогательную программу:
<tex> U(i, x) </tex> {{---}} универсальная функция
<tex>g_{i,x}(y):</tex>
'''if''' U(i, x) == 1 //если i (где i - это программа), на входе x выдает 1
'''return''' <tex>p_X(y)</tex>
'''else'''
'''while''' ''true''
Исключение пустого множества нам нужно чтобы различать <tex> X</tex> и пустое (при построении функции <tex>L(g_{i,x}))</tex>.
Нетрудно понять, что в разумной модели вычислений номер этой программы можно вычислить по данным <tex>i</tex> и <tex>x</tex>. Значит, можно рассмотреть такую программу:
<tex>US(\langle i, x \rangle )</tex>
'''return''' <tex>p_A ( g_{i,x} ) </tex>

Заметим, что
<tex>
L(g_{i,x}) = \begin{cases}
X, & U(i, x) = 1; \\
\varnothing, & U(i, x) \neq 1; \\
\end{cases}
</tex>

Следовательно, <br/> <tex>
US(\langle i, x \rangle ) = p_A(g_{i,x}) = \begin{cases}
p_A(p_X), & U(i, x) = 1; \\
p_A(p_\varnothing ), & U(i, x) \neq 1; \\
\end{cases} = \begin{cases}
1, & U(i, x) = 1; \\
0, & U(i, x) \neq 1; \\
\end{cases}
</tex> {{---}} программа, разрешающая [[Множества | универсальное множество]]. Получили противоречие.
}}

== См. также ==
* [[Теорема о рекурсии]]
* [[Теорема Райса-Шапиро]]

== Источники информации ==
* [https://en.wikipedia.org/wiki/Rice%27s_theorem Wikipedia — Rice's theorem]
* Rice, H. G. "Classes of Recursively Enumerable Sets and Their Decision Problems." Trans. Amer. Math. Soc. 74, 358-366, 1953.
* Хопкрофт Д., Мотванн Р., Ульманн Д. Введение в теорию автоматов, языков и вычислений страница 397.
[[Категория: Теория вычислимости]]
[[Категория: Теория формальных языков]]

Детерминированные конечные автоматы

2014-11-29T09:51:23Z

217.118.78.38: /* Алгоритм */

{{Определение
|definition=
'''Детерминированный конечный автомат (ДКА)''' (англ. ''deterministic finite automaton (DFA)'') — набор из пяти элементов <tex>\langle \Sigma , Q, s \in Q, T \subset Q, \delta : Q \times \Sigma \to Q \rangle</tex>, где <tex>\Sigma</tex> — алфавит (англ. ''alphabet''), <tex>Q</tex> — множество состояний (англ. ''finite set of states''), <tex>s</tex> — начальное (стартовое) состояние (англ. ''start state''), <tex>T</tex> — множество допускающих состояний (англ. ''set of accept states''), <tex>\delta</tex> — функция переходов (англ. ''transition function'').
}}

== Процесс допуска ==
Изначально автомат находится в стартовом состоянии <tex>s</tex>. Автомат считывает символы по очереди. При считывании очередного символа <tex>p_i</tex> автомат переходит в состояние <tex>\delta(q, p_i)</tex>, где <tex>q</tex> — текущее состояние автомата. Процесс продолжается до тех пор, пока не будет достигнут конец входного слова.
{{Определение
|id=допускает
|definition=
Будем говорить, что автомат '''допускает''' слово, если после окончания описанного выше процесса автомат окажется в допускающем состоянии.
}}
'''Замечание.''' Если в какой-то момент из текущего состояния нет перехода по считанному символу, то будем считать, что автомат не допускает данное слово. При реализации вместо отдельного рассмотрения данного случая иногда удобно вводить фиктивную нетерминальную '''''«дьявольскую вершину»''''' (также '''''тупиковое состояние''''', '''''сток'''''), из которой любой переход ведет в неё же саму, и заменить все несуществующие переходы на переходы в «дьявольскую вершину».

== Способы представления ==
* Диаграмма переходов — граф, вершины которого соответствуют состояниям автомата, а рёбра — переходам между состояниями.
* Таблица переходов <tex>T (|Q| \times |\Sigma|)</tex>, дающая табличное представление функции <tex>\delta</tex>.

== Примеры ==
{| border="1" cellpadding="5" cellspacing="0" style="text-align:center" width=60%
|style="background:#ffffff"|Автомат, принимающий непустые строки из чередующихся символов ''a'' и ''b'',<br/>
<small>а) без «дьявольской вершины», <br/>б) с «дьявольской вершиной» (отмечена серым цветом).

<tex>\bigcirc</tex> — нетерминальное состояние,
<br/><tex>\circledcirc</tex> — терминальное состояние.
<br/>Стрелка <tex>\downarrow</tex> указывает на начальное состояние.</small>
|style="background:#ffffff"|а)[[Файл:Finite state machine 1.png|150 px]]
б)[[Файл:Finite state machine 2.png|200 px]]
|-
|style="background:#ffffff"|[[Автомат для поиска образца в тексте]] для строки ''abbab''.
|style="background:#ffffff"|[[Файл:Automata_Search.png|340px]]
|}

== Автоматные языки ==
{{Определение
|definition=
'''Мгновенное описание''' ('''конфигурация''') (англ. ''instant configuration'') {{---}} пара <tex>\langle q, \alpha \rangle</tex>, где <tex>q</tex> {{---}} текущее состояние, <tex>\alpha</tex> {{---}} оставшиеся символы.
}}
Будем говорить, что конфигурация <tex>\langle p, \beta \rangle</tex> выводима из <tex>\langle q, \alpha \rangle</tex> за один шаг <tex>(\langle q, \alpha \rangle \vdash \langle p, \beta \rangle)</tex>, если:
* <tex>\alpha = c\beta</tex>,
* <tex>\delta (q, c)=p </tex>.
Будем говорить, что конфигурация <tex>\langle p, \beta \rangle</tex> выводима из <tex>\langle q, \alpha \rangle</tex> за конечное число шагов <tex>(\langle q, \alpha \rangle \vdash^* \langle p, \beta \rangle)</tex>, если <tex>\exists n:</tex>
* <tex>\alpha = c_1 c_2 ... c_n\beta</tex>,
* <tex>\langle q, c_1 c_2 c_3 ... c_n\beta \rangle \vdash \langle u_1, c_2 c_3 ... c_n\beta \rangle \vdash \langle u_2, c_3 ... c_n\beta \rangle \vdash ... \vdash \langle u_{n-1}, c_n\beta \rangle \vdash \langle p, \beta \rangle</tex>.

{{Лемма
|statement=
<tex>\langle q, \alpha \rangle \vdash^* \langle p, \varepsilon \rangle, \langle p, \beta \rangle \vdash^* \langle r, \varepsilon \rangle \Rightarrow \langle q, \alpha\beta \rangle \vdash^* \langle r, \varepsilon \rangle</tex>.
|proof=
<tex>\langle q, \alpha\beta \rangle \vdash^* \langle p, \beta \rangle \vdash^* \langle r, \varepsilon \rangle.</tex>
}}

{{Определение
|definition=
Множество <tex>L(\mathcal{A})=\{\alpha \mid \exists t \in T : \langle s, \alpha \rangle \vdash^* \langle t, \varepsilon \rangle\}</tex> называется '''языком автомата''' (англ. ''automata's language'') <tex>\mathcal{A}</tex>.
}}
Иначе говоря, языком автомата является множество всех допускаемых им слов. Произвольный язык является автоматным, если существует ДКА, допускающий те и только те слова, которые принадлежат языку.

{{Определение
|definition=
Множество языков всех ДКА образует множество '''автоматных языков''' <tex>\mathrm{AUT}</tex>.
}}

== Изоморфизм двух автоматов ==
{{Определение
|definition=
Автоматы называются изоморфными, если существует [[wikipedia:Биекция | биекция]] между их вершинами такая, что сохраняются все переходы, терминальные состояния соответствуют терминальным, начальные {{---}} начальным
}}
{{Задача
|definition=
Задано два детерминированных конечных автомата. Определить, изоморфны ли они друг другу.
Гарантируется, что все состояния автоматов достижимы.
}}

=== Алгоритм ===
Будем проверять множества переходов для двух вершин. Запустим [[Обход в глубину, цвета вершин | обход в глубину]] из стартовых вершин, если множество переходов по ребрам для двух вершин совпадают и также это выполнено для вершин соответствующим концам ребер (если у нас соответствующие вершины дьявольские, то множество переходов считаем равными) то два автомата изоморфны. Заметим, что если мы рассмотрим два автомата состоящих из пройденных вершин, то эти два автомата будут изоморфны (из этого следует, что на когда мы обойдем все вершины, это тоже будет выполнено). Этот алгоритм пройдет по всем вершинам и ребрам ровно один раз, из этого следует время работы <tex>O(N + M) </tex>, где <tex> N</tex> {{---}} суммарное число вершин в автоматах, <tex> M</tex> {{---}} суммарное число ребер.

=== Псевдокод ===
<tex>Transitions</tex> {{---}} множество пар (<tex>a</tex>, <tex>Vertex</tex>), где <tex> a \in \Sigma</tex>, <tex>Vertex \in Q</tex>
'''boolean''' dfs(Vertex u, Vertex v)
'''for''' (Transition e : u.transitions)
'''if''' ('''not''' v.transitions.contains(e))
'''return''' ''false''

'''if''' (v.transitions.size '''!=''' u.transitions.size)
'''return''' ''false''

'''boolean''' result = ''true''
'''for''' (Transition t : u.transitions)
'''char''' symbol = t.getSymbol()
Vertex t1 = u.transitions.getVertex(symbol)
Vertex t2 = v.transitions.getVertex(symbol)
result = result '''and''' dfs(t1, t2)

'''return''' result

== См. также ==
* [[Недетерминированные конечные автоматы]]
* [[Автомат для поиска образца в тексте]]
* [[Алгоритм Ахо-Корасик]]
* [[Теорема Клини (совпадение классов автоматных и регулярных языков)]]

== Источники информации==
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — М.:Издательский дом «Вильямс», 2002. — С. 61.— ISBN 5-8459-0261-4
* ''Lawson, Mark V. (2004). Finite automata''. Chapman and Hall/CRC. ISBN 1-58488-255-7.
* [[wikipedia:Deterministic finite automaton | Wikipedia {{---}} Deterministic finite automaton]]

[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]

Детерминированные конечные автоматы

2014-11-29T09:43:31Z

217.118.78.38: /* Псевдокод */

{{Определение
|definition=
'''Детерминированный конечный автомат (ДКА)''' (англ. ''deterministic finite automaton (DFA)'') — набор из пяти элементов <tex>\langle \Sigma , Q, s \in Q, T \subset Q, \delta : Q \times \Sigma \to Q \rangle</tex>, где <tex>\Sigma</tex> — алфавит (англ. ''alphabet''), <tex>Q</tex> — множество состояний (англ. ''finite set of states''), <tex>s</tex> — начальное (стартовое) состояние (англ. ''start state''), <tex>T</tex> — множество допускающих состояний (англ. ''set of accept states''), <tex>\delta</tex> — функция переходов (англ. ''transition function'').
}}

== Процесс допуска ==
Изначально автомат находится в стартовом состоянии <tex>s</tex>. Автомат считывает символы по очереди. При считывании очередного символа <tex>p_i</tex> автомат переходит в состояние <tex>\delta(q, p_i)</tex>, где <tex>q</tex> — текущее состояние автомата. Процесс продолжается до тех пор, пока не будет достигнут конец входного слова.
{{Определение
|id=допускает
|definition=
Будем говорить, что автомат '''допускает''' слово, если после окончания описанного выше процесса автомат окажется в допускающем состоянии.
}}
'''Замечание.''' Если в какой-то момент из текущего состояния нет перехода по считанному символу, то будем считать, что автомат не допускает данное слово. При реализации вместо отдельного рассмотрения данного случая иногда удобно вводить фиктивную нетерминальную '''''«дьявольскую вершину»''''' (также '''''тупиковое состояние''''', '''''сток'''''), из которой любой переход ведет в неё же саму, и заменить все несуществующие переходы на переходы в «дьявольскую вершину».

== Способы представления ==
* Диаграмма переходов — граф, вершины которого соответствуют состояниям автомата, а рёбра — переходам между состояниями.
* Таблица переходов <tex>T (|Q| \times |\Sigma|)</tex>, дающая табличное представление функции <tex>\delta</tex>.

== Примеры ==
{| border="1" cellpadding="5" cellspacing="0" style="text-align:center" width=60%
|style="background:#ffffff"|Автомат, принимающий непустые строки из чередующихся символов ''a'' и ''b'',<br/>
<small>а) без «дьявольской вершины», <br/>б) с «дьявольской вершиной» (отмечена серым цветом).

<tex>\bigcirc</tex> — нетерминальное состояние,
<br/><tex>\circledcirc</tex> — терминальное состояние.
<br/>Стрелка <tex>\downarrow</tex> указывает на начальное состояние.</small>
|style="background:#ffffff"|а)[[Файл:Finite state machine 1.png|150 px]]
б)[[Файл:Finite state machine 2.png|200 px]]
|-
|style="background:#ffffff"|[[Автомат для поиска образца в тексте]] для строки ''abbab''.
|style="background:#ffffff"|[[Файл:Automata_Search.png|340px]]
|}

== Автоматные языки ==
{{Определение
|definition=
'''Мгновенное описание''' ('''конфигурация''') (англ. ''instant configuration'') {{---}} пара <tex>\langle q, \alpha \rangle</tex>, где <tex>q</tex> {{---}} текущее состояние, <tex>\alpha</tex> {{---}} оставшиеся символы.
}}
Будем говорить, что конфигурация <tex>\langle p, \beta \rangle</tex> выводима из <tex>\langle q, \alpha \rangle</tex> за один шаг <tex>(\langle q, \alpha \rangle \vdash \langle p, \beta \rangle)</tex>, если:
* <tex>\alpha = c\beta</tex>,
* <tex>\delta (q, c)=p </tex>.
Будем говорить, что конфигурация <tex>\langle p, \beta \rangle</tex> выводима из <tex>\langle q, \alpha \rangle</tex> за конечное число шагов <tex>(\langle q, \alpha \rangle \vdash^* \langle p, \beta \rangle)</tex>, если <tex>\exists n:</tex>
* <tex>\alpha = c_1 c_2 ... c_n\beta</tex>,
* <tex>\langle q, c_1 c_2 c_3 ... c_n\beta \rangle \vdash \langle u_1, c_2 c_3 ... c_n\beta \rangle \vdash \langle u_2, c_3 ... c_n\beta \rangle \vdash ... \vdash \langle u_{n-1}, c_n\beta \rangle \vdash \langle p, \beta \rangle</tex>.

{{Лемма
|statement=
<tex>\langle q, \alpha \rangle \vdash^* \langle p, \varepsilon \rangle, \langle p, \beta \rangle \vdash^* \langle r, \varepsilon \rangle \Rightarrow \langle q, \alpha\beta \rangle \vdash^* \langle r, \varepsilon \rangle</tex>.
|proof=
<tex>\langle q, \alpha\beta \rangle \vdash^* \langle p, \beta \rangle \vdash^* \langle r, \varepsilon \rangle.</tex>
}}

{{Определение
|definition=
Множество <tex>L(\mathcal{A})=\{\alpha \mid \exists t \in T : \langle s, \alpha \rangle \vdash^* \langle t, \varepsilon \rangle\}</tex> называется '''языком автомата''' (англ. ''automata's language'') <tex>\mathcal{A}</tex>.
}}
Иначе говоря, языком автомата является множество всех допускаемых им слов. Произвольный язык является автоматным, если существует ДКА, допускающий те и только те слова, которые принадлежат языку.

{{Определение
|definition=
Множество языков всех ДКА образует множество '''автоматных языков''' <tex>\mathrm{AUT}</tex>.
}}

== Изоморфизм двух автоматов ==
{{Определение
|definition=
Автоматы называются изоморфными, если существует [[wikipedia:Биекция | биекция]] между их вершинами такая, что сохраняются все переходы, терминальные состояния соответствуют терминальным, начальные {{---}} начальным
}}
{{Задача
|definition=
Задано два детерминированных конечных автомата. Определить, изоморфны ли они друг другу.
Гарантируется, что все состояния автоматов достижимы.
}}

=== Алгоритм ===
Будем проверять множества переходов для двух вершин. Запустим [[Обход в глубину, цвета вершин | обход в глубину]] из стартовых вершин, если множество переходов по ребрам для двух вершин совпадают и также это выполнено для вершин соответствующим концам ребер (если у нас соответствующие вершины дьявольские, то множество переходов считаем равными) то два автомата изоморфны. Этот алгоритм пройдет по всем вершинам и ребрам ровно один раз, из этого следует время работы <tex>O(N + M) </tex>, где <tex> N</tex> {{---}} суммарное число вершин в автоматах, <tex> M</tex> {{---}} суммарное число ребер.

=== Псевдокод ===
<tex>Transitions</tex> {{---}} множество пар (<tex>a</tex>, <tex>Vertex</tex>), где <tex> a \in \Sigma</tex>, <tex>Vertex \in Q</tex>
'''boolean''' dfs(Vertex u, Vertex v)
'''for''' (Transition e : u.transitions)
'''if''' ('''not''' v.transitions.contains(e))
'''return''' ''false''

'''if''' (v.transitions.size '''!=''' u.transitions.size)
'''return''' ''false''

'''boolean''' result = ''true''
'''for''' (Transition t : u.transitions)
'''char''' symbol = t.getSymbol()
Vertex t1 = u.transitions.getVertex(symbol)
Vertex t2 = v.transitions.getVertex(symbol)
result = result '''and''' dfs(t1, t2)

'''return''' result

== См. также ==
* [[Недетерминированные конечные автоматы]]
* [[Автомат для поиска образца в тексте]]
* [[Алгоритм Ахо-Корасик]]
* [[Теорема Клини (совпадение классов автоматных и регулярных языков)]]

== Источники информации==
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — М.:Издательский дом «Вильямс», 2002. — С. 61.— ISBN 5-8459-0261-4
* ''Lawson, Mark V. (2004). Finite automata''. Chapman and Hall/CRC. ISBN 1-58488-255-7.
* [[wikipedia:Deterministic finite automaton | Wikipedia {{---}} Deterministic finite automaton]]

[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]

Детерминированные конечные автоматы

2014-11-29T09:43:09Z

217.118.78.38: /* Псевдокод */

{{Определение
|definition=
'''Детерминированный конечный автомат (ДКА)''' (англ. ''deterministic finite automaton (DFA)'') — набор из пяти элементов <tex>\langle \Sigma , Q, s \in Q, T \subset Q, \delta : Q \times \Sigma \to Q \rangle</tex>, где <tex>\Sigma</tex> — алфавит (англ. ''alphabet''), <tex>Q</tex> — множество состояний (англ. ''finite set of states''), <tex>s</tex> — начальное (стартовое) состояние (англ. ''start state''), <tex>T</tex> — множество допускающих состояний (англ. ''set of accept states''), <tex>\delta</tex> — функция переходов (англ. ''transition function'').
}}

== Процесс допуска ==
Изначально автомат находится в стартовом состоянии <tex>s</tex>. Автомат считывает символы по очереди. При считывании очередного символа <tex>p_i</tex> автомат переходит в состояние <tex>\delta(q, p_i)</tex>, где <tex>q</tex> — текущее состояние автомата. Процесс продолжается до тех пор, пока не будет достигнут конец входного слова.
{{Определение
|id=допускает
|definition=
Будем говорить, что автомат '''допускает''' слово, если после окончания описанного выше процесса автомат окажется в допускающем состоянии.
}}
'''Замечание.''' Если в какой-то момент из текущего состояния нет перехода по считанному символу, то будем считать, что автомат не допускает данное слово. При реализации вместо отдельного рассмотрения данного случая иногда удобно вводить фиктивную нетерминальную '''''«дьявольскую вершину»''''' (также '''''тупиковое состояние''''', '''''сток'''''), из которой любой переход ведет в неё же саму, и заменить все несуществующие переходы на переходы в «дьявольскую вершину».

== Способы представления ==
* Диаграмма переходов — граф, вершины которого соответствуют состояниям автомата, а рёбра — переходам между состояниями.
* Таблица переходов <tex>T (|Q| \times |\Sigma|)</tex>, дающая табличное представление функции <tex>\delta</tex>.

== Примеры ==
{| border="1" cellpadding="5" cellspacing="0" style="text-align:center" width=60%
|style="background:#ffffff"|Автомат, принимающий непустые строки из чередующихся символов ''a'' и ''b'',<br/>
<small>а) без «дьявольской вершины», <br/>б) с «дьявольской вершиной» (отмечена серым цветом).

<tex>\bigcirc</tex> — нетерминальное состояние,
<br/><tex>\circledcirc</tex> — терминальное состояние.
<br/>Стрелка <tex>\downarrow</tex> указывает на начальное состояние.</small>
|style="background:#ffffff"|а)[[Файл:Finite state machine 1.png|150 px]]
б)[[Файл:Finite state machine 2.png|200 px]]
|-
|style="background:#ffffff"|[[Автомат для поиска образца в тексте]] для строки ''abbab''.
|style="background:#ffffff"|[[Файл:Automata_Search.png|340px]]
|}

== Автоматные языки ==
{{Определение
|definition=
'''Мгновенное описание''' ('''конфигурация''') (англ. ''instant configuration'') {{---}} пара <tex>\langle q, \alpha \rangle</tex>, где <tex>q</tex> {{---}} текущее состояние, <tex>\alpha</tex> {{---}} оставшиеся символы.
}}
Будем говорить, что конфигурация <tex>\langle p, \beta \rangle</tex> выводима из <tex>\langle q, \alpha \rangle</tex> за один шаг <tex>(\langle q, \alpha \rangle \vdash \langle p, \beta \rangle)</tex>, если:
* <tex>\alpha = c\beta</tex>,
* <tex>\delta (q, c)=p </tex>.
Будем говорить, что конфигурация <tex>\langle p, \beta \rangle</tex> выводима из <tex>\langle q, \alpha \rangle</tex> за конечное число шагов <tex>(\langle q, \alpha \rangle \vdash^* \langle p, \beta \rangle)</tex>, если <tex>\exists n:</tex>
* <tex>\alpha = c_1 c_2 ... c_n\beta</tex>,
* <tex>\langle q, c_1 c_2 c_3 ... c_n\beta \rangle \vdash \langle u_1, c_2 c_3 ... c_n\beta \rangle \vdash \langle u_2, c_3 ... c_n\beta \rangle \vdash ... \vdash \langle u_{n-1}, c_n\beta \rangle \vdash \langle p, \beta \rangle</tex>.

{{Лемма
|statement=
<tex>\langle q, \alpha \rangle \vdash^* \langle p, \varepsilon \rangle, \langle p, \beta \rangle \vdash^* \langle r, \varepsilon \rangle \Rightarrow \langle q, \alpha\beta \rangle \vdash^* \langle r, \varepsilon \rangle</tex>.
|proof=
<tex>\langle q, \alpha\beta \rangle \vdash^* \langle p, \beta \rangle \vdash^* \langle r, \varepsilon \rangle.</tex>
}}

{{Определение
|definition=
Множество <tex>L(\mathcal{A})=\{\alpha \mid \exists t \in T : \langle s, \alpha \rangle \vdash^* \langle t, \varepsilon \rangle\}</tex> называется '''языком автомата''' (англ. ''automata's language'') <tex>\mathcal{A}</tex>.
}}
Иначе говоря, языком автомата является множество всех допускаемых им слов. Произвольный язык является автоматным, если существует ДКА, допускающий те и только те слова, которые принадлежат языку.

{{Определение
|definition=
Множество языков всех ДКА образует множество '''автоматных языков''' <tex>\mathrm{AUT}</tex>.
}}

== Изоморфизм двух автоматов ==
{{Определение
|definition=
Автоматы называются изоморфными, если существует [[wikipedia:Биекция | биекция]] между их вершинами такая, что сохраняются все переходы, терминальные состояния соответствуют терминальным, начальные {{---}} начальным
}}
{{Задача
|definition=
Задано два детерминированных конечных автомата. Определить, изоморфны ли они друг другу.
Гарантируется, что все состояния автоматов достижимы.
}}

=== Алгоритм ===
Будем проверять множества переходов для двух вершин. Запустим [[Обход в глубину, цвета вершин | обход в глубину]] из стартовых вершин, если множество переходов по ребрам для двух вершин совпадают и также это выполнено для вершин соответствующим концам ребер (если у нас соответствующие вершины дьявольские, то множество переходов считаем равными) то два автомата изоморфны. Этот алгоритм пройдет по всем вершинам и ребрам ровно один раз, из этого следует время работы <tex>O(N + M) </tex>, где <tex> N</tex> {{---}} суммарное число вершин в автоматах, <tex> M</tex> {{---}} суммарное число ребер.

=== Псевдокод ===
<tex>Transitions</tex> {{---}} множество пар (<tex>a</tex>, <tex>Vertex</tex>), где <tex> a \in \Sigma</tex>, <tex>C \in Q</tex>
'''boolean''' dfs(Vertex u, Vertex v)
'''for''' (Transition e : u.transitions)
'''if''' ('''not''' v.transitions.contains(e))
'''return''' ''false''

'''if''' (v.transitions.size '''!=''' u.transitions.size)
'''return''' ''false''

'''boolean''' result = ''true''
'''for''' (Transition t : u.transitions)
'''char''' symbol = t.getSymbol()
Vertex t1 = u.transitions.getVertex(symbol)
Vertex t2 = v.transitions.getVertex(symbol)
result = result '''and''' dfs(t1, t2)

'''return''' result

== См. также ==
* [[Недетерминированные конечные автоматы]]
* [[Автомат для поиска образца в тексте]]
* [[Алгоритм Ахо-Корасик]]
* [[Теорема Клини (совпадение классов автоматных и регулярных языков)]]

== Источники информации==
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — М.:Издательский дом «Вильямс», 2002. — С. 61.— ISBN 5-8459-0261-4
* ''Lawson, Mark V. (2004). Finite automata''. Chapman and Hall/CRC. ISBN 1-58488-255-7.
* [[wikipedia:Deterministic finite automaton | Wikipedia {{---}} Deterministic finite automaton]]

[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]

QpmtnCmax

2012-06-11T19:05:32Z

217.118.78.38: /* Доказательство корректности алгоритма */

<div style="background-color: #ABCDEF; font-size: 16px; font-weight: bold; color: #000000; text-align: center; padding: 4px; border-style: solid; border-width: 1px;">Эта статья находится в разработке!</div>
<includeonly>[[Категория: В разработке]]</includeonly>

==Постановка задачи==
Есть несколько станков с разной скоростью выполнения работ. Работу на каждом из станков можно прервать и продолжить позже.

Цель - выполнить все как можно быстрее.

1. Найдем нижнюю границу времени выполнения.

2. Составим оптимальное расписание.

==Алгоритм построения расписания==

<tex> P_i = p_1 + ... + p_i</tex>

<tex> S_j = s_1 + ... + s_j</tex>

Где <tex>i = 1 ... n</tex>; <tex>j = 1 ... m</tex>; <tex> p_i</tex> - вес i-ой работы ;<tex> s_j</tex> - скорость работы j-oй машины ; <tex> n \ge m</tex>;

Необходимое условие для выполнения всех работ в интервале <tex>[0;T]</tex>:

<tex> P_n = p_1 + ... + p_n \le s_1T + ... + s_mT = S_mT</tex> или <tex>P_n/S_m \le T</tex>

Нижняя граница <tex>C_{max}</tex> :

<tex>w = \max\{\max\limits_{j=1}^{m-1} {P_i \over S_j}, {P_n \over S_m}\}</tex>

Будем назвать Level-ом работы <tex> lvl(p_i(t)) </tex> - невыполненную часть работы <tex> p_i </tex> в момент времени <tex> t </tex>

Далее построим расписание, которое достигает нашей оценки <tex>w</tex>, с помощью Level-алгоритма.

Level - алгоритм:

<tex>t \leftarrow 0 </tex>
'''WHILE''' существуют работы с положительным level
Assign(t)
<tex>t1 \leftarrow min(s>t |</tex>работа выполненная в момент времени <tex> s)</tex>
<tex>t2 \leftarrow min(s>t | p_i(t)>p_j(t)</tex> && <tex> p_i(s) == p_j(s))</tex>
<tex> t \leftarrow min(t1,t2) </tex>
Построение расписания

Функция <tex>Assign(t)</tex>:

<tex>J = </tex>{<tex>i|p_i(t)>0</tex>}
<tex>M = </tex>{<tex>M_1,...,M_m</tex>}
'''WHILE''' (<tex>J</tex> != 0 && <tex>M</tex> != 0)
Найти множество работ <tex>I</tex> подмножество <tex>J</tex> ,level которых максимальный
<tex>r \leftarrow min</tex>(|<tex>M</tex>|,|<tex>I</tex>|)
Назначаем работы из мн-ва <tex>I</tex> на <tex>r</tex> самых быстрых машин из мн-ва <tex>M</tex>
<tex>J \leftarrow J</tex>\<tex>I</tex>
удаляем из мн-ва <tex>M</tex> <tex>r</tex> самых быстрых машин

==Доказательство корректности алгоритма==
Так как нижняя граница <tex>C_{max}</tex>:

<tex>w = \max\{\max\limits_{j=1}^{m-1} {P_i \over S_j}, {P_n \over S_m}\}</tex>

то достаточно показать, что составленное расписание достигает этой оценки.

Будем считать, что в начале алгоритма мы имеем <tex> p_1(0) \ge p_2(0) \ge ... \ge p_n(0) </tex>. Это утверждение не меняется на протяжении всего выполнения алгоритма, для любого момента времени. Получаем: <tex> p_1(t) \ge p_2(t) \ge ... \ge p_n(t) </tex>. Докажем что алгоритм составляет расписание в соответствии с этим свойством. Чтобы доказать этот факт, будем считать что в любой момент времени T нет простоев машин, когда есть хотя бы одна невыполненная работа. Получаем:

<tex> T(s_1 + ... + s_m) = p_1 + p_2 + ... + p_n </tex> или <tex> T = {P_n \over S_n} </tex>

Таким образом необходимая оценка достигается нашим алгоритмом.

==Пример==
[[Файл:qptmncmax.png|400px|thumb|right|Картинка к примеру]]

Пусть у нас есть 5 работ и 4 станка. Покажем работу алгоритма для данного случая.

В начальный момент времени начинаем обрабатывать работы с наибольшим временем выполнения <tex>J_1-J_4</tex> на станках <tex>M_1-M_4</tex> соответственно. В момент времени <tex>t_1</tex> <tex>lvl</tex> 4-ой работы опускается до времени выполнения 5-ой работы. С этого момента начинаем обрабатывать работы <tex> J_4,J_5</tex> на одном станке: <tex>M_4</tex>. В момент времени <tex>t_2</tex> происходит похожая ситуация. С этого момента времени работы <tex> J_1,J_2</tex> выполняются синхронно на двух станках <tex> M_1,M_2</tex>. Далее работы не пересекаются друг с другом и каждая заканчивается на ранее выделенных им станках.

==Время работы==
Level-алгоритм вызывает функцию Assign(t) в самом худшем случае <tex>O(n)</tex> раз. Функция Assign(t) выполняется за <tex>O(nm)</tex>. Итоговое время работы <tex>O(n^2m)</tex>.

==Литература==
* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 379 стр. {{---}} ISBN 978-3-540-69515-8

QpmtnCmax

2012-06-11T18:04:09Z

217.118.78.38: /* Алгоритм построения расписания */

<div style="background-color: #ABCDEF; font-size: 16px; font-weight: bold; color: #000000; text-align: center; padding: 4px; border-style: solid; border-width: 1px;">Эта статья находится в разработке!</div>
<includeonly>[[Категория: В разработке]]</includeonly>

==Постановка задачи==
Есть несколько станков с разной скоростью выполнения работ. Работу на каждом из станков можно прервать и продолжить позже.

Цель - выполнить все как можно быстрее.

1. Найдем нижнюю границу времени выполнения.

2. Составим оптимальное расписание.

==Алгоритм построения расписания==

<tex> P_i = p_1 + ... + p_i</tex>

<tex> S_j = s_1 + ... + s_j</tex>

Где <tex>i = 1 ... n</tex>; <tex>j = 1 ... m</tex>; <tex> p_i</tex> - вес i-ой работы ;<tex> s_j</tex> - скорость работы j-oй машины ; <tex> n \ge m</tex>;

Необходимое условие для выполнения всех работ в интервале <tex>[0;T]</tex>:

<tex> P_n = p_1 + ... + p_n \le s_1T + ... + s_mT = S_mT</tex> или <tex>P_n/S_m \le T</tex>

Нижняя граница <tex>C_{max}</tex> :

<tex>w = \max\{\max\limits_{j=1}^{m-1} {P_i \over S_j}, {P_n \over S_m}\}</tex>

Будем назвать Level-ом работы <tex> lvl(p_i(t)) </tex> - невыполненную часть работы <tex> p_i </tex> в момент времени <tex> t </tex>

Далее построим расписание, которое достигает нашей оценки <tex>w</tex>, с помощью Level-алгоритма.

Level - алгоритм:

<tex>t \leftarrow 0 </tex>
'''WHILE''' существуют работы с положительным level
Assign(t)
<tex>t1 \leftarrow min(s>t |</tex>работа выполненная в момент времени <tex> s)</tex>
<tex>t2 \leftarrow min(s>t | p_i(t)>p_j(t)</tex> && <tex> p_i(s) == p_j(s))</tex>
<tex> t \leftarrow min(t1,t2) </tex>
Построение расписания

Функция <tex>Assign(t)</tex>:

<tex>J = </tex>{<tex>i|p_i(t)>0</tex>}
<tex>M = </tex>{<tex>M_1,...,M_m</tex>}
'''WHILE''' (<tex>J</tex> != 0 && <tex>M</tex> != 0)
Найти множество работ <tex>I</tex> подмножество <tex>J</tex> ,level которых максимальный
<tex>r \leftarrow min</tex>(|<tex>M</tex>|,|<tex>I</tex>|)
Назначаем работы из мн-ва <tex>I</tex> на <tex>r</tex> самых быстрых машин из мн-ва <tex>M</tex>
<tex>J \leftarrow J</tex>\<tex>I</tex>
удаляем из мн-ва <tex>M</tex> <tex>r</tex> самых быстрых машин

==Доказательство корректности алгоритма==
Так как нижняя граница <tex>C_{max}</tex>:

<tex>w = \max\{\max\limits_{j=1}^{m-1} {P_i \over S_j}, {P_n \over S_m}\}</tex>

то достаточно показать, что составленное расписание достигает этой оценки.

==Пример==
[[Файл:qptmncmax.png|400px|thumb|right|Картинка к примеру]]

Пусть у нас есть 5 работ и 4 станка. Покажем работу алгоритма для данного случая.

В начальный момент времени начинаем обрабатывать работы с наибольшим временем выполнения <tex>J_1-J_4</tex> на станках <tex>M_1-M_4</tex> соответственно. В момент времени <tex>t_1</tex> <tex>lvl</tex> 4-ой работы опускается до времени выполнения 5-ой работы. С этого момента начинаем обрабатывать работы <tex> J_4,J_5</tex> на одном станке: <tex>M_4</tex>. В момент времени <tex>t_2</tex> происходит похожая ситуация. С этого момента времени работы <tex> J_1,J_2</tex> выполняются синхронно на двух станках <tex> M_1,M_2</tex>. Далее работы не пересекаются друг с другом и каждая заканчивается на ранее выделенных им станках.

==Время работы==
Level-алгоритм вызывает функцию Assign(t) в самом худшем случае <tex>O(n)</tex> раз. Функция Assign(t) выполняется за <tex>O(nm)</tex>. Итоговое время работы <tex>O(n^2m)</tex>.

==Литература==
* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 379 стр. {{---}} ISBN 978-3-540-69515-8

QpmtnCmax

2012-06-11T18:03:50Z

217.118.78.38: /* Доказательство корректности алгоритма */

<div style="background-color: #ABCDEF; font-size: 16px; font-weight: bold; color: #000000; text-align: center; padding: 4px; border-style: solid; border-width: 1px;">Эта статья находится в разработке!</div>
<includeonly>[[Категория: В разработке]]</includeonly>

==Постановка задачи==
Есть несколько станков с разной скоростью выполнения работ. Работу на каждом из станков можно прервать и продолжить позже.

Цель - выполнить все как можно быстрее.

1. Найдем нижнюю границу времени выполнения.

2. Составим оптимальное расписание.

==Алгоритм построения расписания==

<tex> P_i = p_1 + ... + p_i</tex>

<tex> S_j = s_1 + ... + s_j</tex>

Где <tex>i = 1 ... n</tex>; <tex>j = 1 ... m</tex>; <tex> p_i</tex> - вес i-ой работы ;<tex> s_j</tex> - скорость работы j-oй машины ; <tex> n \ge m</tex>;

Необходимое условие для выполнения всех работ в интервале <tex>[0;T]</tex>:

<tex> P_n = p_1 + ... + p_n \le s_1T + ... + s_mT = S_mT</tex> или <tex>P_n/S_m \le T</tex>

Нижняя граница <tex>C_{max}</tex> :

<tex>w = \max\{\max\limits_{j=1}^{m-1} {P_i \over S_j}, {P_n \over S_m}\}</tex>

Будем назвать Level-ом работы <tex> lvl(p_i(t)) </tex> - невыполненную часть работы <tex> p_i </tex> в момент времени <tex> t </tex>

Далее построим расписание, которое достигает нашей оценки <tex>w</tex>, с помощью Level-алгоритма.

Level - алгоритм:

<tex>t \leftarrow 0 </tex>
'''WHILE''' существуют работы с положительным level
Assign(t)
<tex>t1 \leftarrow min(s>t |</tex>работа выполненная в момент времени <tex> s)</tex>
<tex>t2 \leftarrow min(s>t | p_i(t)>p_j(t)</tex> && <tex> p_i(s) == p_j(s))</tex>
<tex> t \leftarrow min(t1,t2) </tex>
Построение расписания

Функция <tex>Assign(t)</tex>:

<tex>J = </tex>{<tex>i|p_i(t)>0</tex>}
<tex>M = </tex>{<tex>M_1,...,M_m</tex>}
'''WHILE''' (<tex>J</tex> != 0 && <tex>M</tex> != 0)
Найти множество работ <tex>I</tex> подмножество <tex>J</tex> ,level которых максимальный
<tex>r \leftarrow min</tex>(|<tex>M</tex>|,|<tex>I</tex>|)
Назначаем работы из мн-ва <tex>I</tex> на <tex>r</tex> самых быстрых машин из мн-ва <tex>M</tex>
<tex>J \leftarrow J</tex>\<tex>I</tex>
удаляем из мн-ва <tex>M</tex> <tex>r</tex> самых быстрых машин

==Доказательство корректности алгоритма==
Так как нижняя граница <tex>C_{max}</tex>:

<tex>w = \max\{\max\limits_{j=1}^{m-1} {P_i \over S_j}, {P_n \over S_m}\}</tex>

то достаточно показать, что составленное расписание достигает этой оценки.

==Пример==
[[Файл:qptmncmax.png|400px|thumb|right|Картинка к примеру]]

Пусть у нас есть 5 работ и 4 станка. Покажем работу алгоритма для данного случая.

В начальный момент времени начинаем обрабатывать работы с наибольшим временем выполнения <tex>J_1-J_4</tex> на станках <tex>M_1-M_4</tex> соответственно. В момент времени <tex>t_1</tex> <tex>lvl</tex> 4-ой работы опускается до времени выполнения 5-ой работы. С этого момента начинаем обрабатывать работы <tex> J_4,J_5</tex> на одном станке: <tex>M_4</tex>. В момент времени <tex>t_2</tex> происходит похожая ситуация. С этого момента времени работы <tex> J_1,J_2</tex> выполняются синхронно на двух станках <tex> M_1,M_2</tex>. Далее работы не пересекаются друг с другом и каждая заканчивается на ранее выделенных им станках.

==Время работы==
Level-алгоритм вызывает функцию Assign(t) в самом худшем случае <tex>O(n)</tex> раз. Функция Assign(t) выполняется за <tex>O(nm)</tex>. Итоговое время работы <tex>O(n^2m)</tex>.

==Литература==
* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 379 стр. {{---}} ISBN 978-3-540-69515-8

QpmtnCmax

2012-06-11T18:03:22Z

217.118.78.38: /* Алгоритм построения расписания */

<div style="background-color: #ABCDEF; font-size: 16px; font-weight: bold; color: #000000; text-align: center; padding: 4px; border-style: solid; border-width: 1px;">Эта статья находится в разработке!</div>
<includeonly>[[Категория: В разработке]]</includeonly>

==Постановка задачи==
Есть несколько станков с разной скоростью выполнения работ. Работу на каждом из станков можно прервать и продолжить позже.

Цель - выполнить все как можно быстрее.

1. Найдем нижнюю границу времени выполнения.

2. Составим оптимальное расписание.

==Алгоритм построения расписания==

<tex> P_i = p_1 + ... + p_i</tex>

<tex> S_j = s_1 + ... + s_j</tex>

Где <tex>i = 1 ... n</tex>; <tex>j = 1 ... m</tex>; <tex> p_i</tex> - вес i-ой работы ;<tex> s_j</tex> - скорость работы j-oй машины ; <tex> n \ge m</tex>;

Необходимое условие для выполнения всех работ в интервале <tex>[0;T]</tex>:

<tex> P_n = p_1 + ... + p_n \le s_1T + ... + s_mT = S_mT</tex> или <tex>P_n/S_m \le T</tex>

Нижняя граница <tex>C_{max}</tex> :

<tex>w = \max\{\max\limits_{j=1}^{m-1} {P_i \over S_j}, {P_n \over S_m}\}</tex>

Будем назвать Level-ом работы <tex> lvl(p_i(t)) </tex> - невыполненную часть работы <tex> p_i </tex> в момент времени <tex> t </tex>

Далее построим расписание, которое достигает нашей оценки <tex>w</tex>, с помощью Level-алгоритма.

Level - алгоритм:

<tex>t \leftarrow 0 </tex>
'''WHILE''' существуют работы с положительным level
Assign(t)
<tex>t1 \leftarrow min(s>t |</tex>работа выполненная в момент времени <tex> s)</tex>
<tex>t2 \leftarrow min(s>t | p_i(t)>p_j(t)</tex> && <tex> p_i(s) == p_j(s))</tex>
<tex> t \leftarrow min(t1,t2) </tex>
Построение расписания

Функция <tex>Assign(t)</tex>:

<tex>J = </tex>{<tex>i|p_i(t)>0</tex>}
<tex>M = </tex>{<tex>M_1,...,M_m</tex>}
'''WHILE''' (<tex>J</tex> != 0 && <tex>M</tex> != 0)
Найти множество работ <tex>I</tex> подмножество <tex>J</tex> ,level которых максимальный
<tex>r \leftarrow min</tex>(|<tex>M</tex>|,|<tex>I</tex>|)
Назначаем работы из мн-ва <tex>I</tex> на <tex>r</tex> самых быстрых машин из мн-ва <tex>M</tex>
<tex>J \leftarrow J</tex>\<tex>I</tex>
удаляем из мн-ва <tex>M</tex> <tex>r</tex> самых быстрых машин

==Доказательство корректности алгоритма==
Так как нижняя граница <tex>C_{max}</tex>:

<tex>w = \max\{\max\limits_{j=1}^{m-1} {P_i \over S_j}, {P_n \over S_m}\}</tex>

то достаточно показать, что составленное расписание достигает этой оценки.

==Пример==
[[Файл:qptmncmax.png|400px|thumb|right|Картинка к примеру]]

Пусть у нас есть 5 работ и 4 станка. Покажем работу алгоритма для данного случая.

В начальный момент времени начинаем обрабатывать работы с наибольшим временем выполнения <tex>J_1-J_4</tex> на станках <tex>M_1-M_4</tex> соответственно. В момент времени <tex>t_1</tex> <tex>lvl</tex> 4-ой работы опускается до времени выполнения 5-ой работы. С этого момента начинаем обрабатывать работы <tex> J_4,J_5</tex> на одном станке: <tex>M_4</tex>. В момент времени <tex>t_2</tex> происходит похожая ситуация. С этого момента времени работы <tex> J_1,J_2</tex> выполняются синхронно на двух станках <tex> M_1,M_2</tex>. Далее работы не пересекаются друг с другом и каждая заканчивается на ранее выделенных им станках.

==Время работы==
Level-алгоритм вызывает функцию Assign(t) в самом худшем случае <tex>O(n)</tex> раз. Функция Assign(t) выполняется за <tex>O(nm)</tex>. Итоговое время работы <tex>O(n^2m)</tex>.

==Литература==
* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 379 стр. {{---}} ISBN 978-3-540-69515-8

QpmtnCmax

2012-06-11T18:02:49Z

217.118.78.38: /* Доказательство корректности алгоритма */

<div style="background-color: #ABCDEF; font-size: 16px; font-weight: bold; color: #000000; text-align: center; padding: 4px; border-style: solid; border-width: 1px;">Эта статья находится в разработке!</div>
<includeonly>[[Категория: В разработке]]</includeonly>

==Постановка задачи==
Есть несколько станков с разной скоростью выполнения работ. Работу на каждом из станков можно прервать и продолжить позже.

Цель - выполнить все как можно быстрее.

1. Найдем нижнюю границу времени выполнения.

2. Составим оптимальное расписание.

==Алгоритм построения расписания==

<tex> P_i = p_1 + ... + p_i</tex>

<tex> S_j = s_1 + ... + s_j</tex>

Где <tex>i = 1 ... n</tex>; <tex>j = 1 ... m</tex>; <tex> p_i</tex> - вес i-ой работы ;<tex> s_j</tex> - скорость работы j-oй машины ; <tex> n \ge m</tex>;

Необходимое условие для выполнения всех работ в интервале <tex>[0;T]</tex>:

<tex> P_n = p_1 + ... + p_n \le s_1T + ... + s_mT = S_mT</tex> или <tex>P_n/S_m \le T</tex>

Нижняя граница <tex>C_{max}</tex> :

<tex>w = \max</tex>{<tex>\max\limits_{j=1}^{m-1} P_i/S_j, P_n/S_m</tex>}

Будем назвать Level-ом работы <tex> lvl(p_i(t)) </tex> - невыполненную часть работы <tex> p_i </tex> в момент времени <tex> t </tex>

Далее построим расписание, которое достигает нашей оценки <tex>w</tex>, с помощью Level-алгоритма.

Level - алгоритм:

<tex>t \leftarrow 0 </tex>
'''WHILE''' существуют работы с положительным level
Assign(t)
<tex>t1 \leftarrow min(s>t |</tex>работа выполненная в момент времени <tex> s)</tex>
<tex>t2 \leftarrow min(s>t | p_i(t)>p_j(t)</tex> && <tex> p_i(s) == p_j(s))</tex>
<tex> t \leftarrow min(t1,t2) </tex>
Построение расписания

Функция <tex>Assign(t)</tex>:

<tex>J = </tex>{<tex>i|p_i(t)>0</tex>}
<tex>M = </tex>{<tex>M_1,...,M_m</tex>}
'''WHILE''' (<tex>J</tex> != 0 && <tex>M</tex> != 0)
Найти множество работ <tex>I</tex> подмножество <tex>J</tex> ,level которых максимальный
<tex>r \leftarrow min</tex>(|<tex>M</tex>|,|<tex>I</tex>|)
Назначаем работы из мн-ва <tex>I</tex> на <tex>r</tex> самых быстрых машин из мн-ва <tex>M</tex>
<tex>J \leftarrow J</tex>\<tex>I</tex>
удаляем из мн-ва <tex>M</tex> <tex>r</tex> самых быстрых машин

==Доказательство корректности алгоритма==
Так как нижняя граница <tex>C_{max}</tex>:

<tex>w = \max\{\max\limits_{j=1}^{m-1} {P_i \over S_j}, {P_n \over S_m}\}</tex>

то достаточно показать, что составленное расписание достигает этой оценки.

==Пример==
[[Файл:qptmncmax.png|400px|thumb|right|Картинка к примеру]]

Пусть у нас есть 5 работ и 4 станка. Покажем работу алгоритма для данного случая.

В начальный момент времени начинаем обрабатывать работы с наибольшим временем выполнения <tex>J_1-J_4</tex> на станках <tex>M_1-M_4</tex> соответственно. В момент времени <tex>t_1</tex> <tex>lvl</tex> 4-ой работы опускается до времени выполнения 5-ой работы. С этого момента начинаем обрабатывать работы <tex> J_4,J_5</tex> на одном станке: <tex>M_4</tex>. В момент времени <tex>t_2</tex> происходит похожая ситуация. С этого момента времени работы <tex> J_1,J_2</tex> выполняются синхронно на двух станках <tex> M_1,M_2</tex>. Далее работы не пересекаются друг с другом и каждая заканчивается на ранее выделенных им станках.

==Время работы==
Level-алгоритм вызывает функцию Assign(t) в самом худшем случае <tex>O(n)</tex> раз. Функция Assign(t) выполняется за <tex>O(nm)</tex>. Итоговое время работы <tex>O(n^2m)</tex>.

==Литература==
* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 379 стр. {{---}} ISBN 978-3-540-69515-8

QpmtnCmax

2012-06-11T11:31:07Z

217.118.78.38:

<div style="background-color: #ABCDEF; font-size: 16px; font-weight: bold; color: #000000; text-align: center; padding: 4px; border-style: solid; border-width: 1px;">Эта статья находится в разработке!</div>
<includeonly>[[Категория: В разработке]]</includeonly>

==Постановка задачи==
Есть несколько станков с разной скоростью выполнения работ. Работу на каждом из станков можно прервать и продолжить позже.

Цель - выполнить все как можно быстрее.

1. Найдем нижнюю границу времени выполнения.

2. Составим оптимальное расписание.

==Алгоритм построения расписания==

<tex> P_i = p_1 + ... + p_i</tex>

<tex> S_j = s_1 + ... + s_j</tex>

Где <tex>i = 1 ... n</tex>; <tex>j = 1 ... m</tex>; <tex> p_i</tex> - вес i-ой работы ;<tex> s_j</tex> - скорость работы j-oй машины ; <tex> n \ge m</tex>;

Необходимое условие для выполнения всех работ в интервале <tex>[0;T]</tex>:

<tex> P_n = p_1 + ... + p_n \le s_1T + ... + s_mT = S_mT</tex> или <tex>P_n/S_m \le T</tex>

Нижняя граница <tex>C_{max}</tex> :

<tex>w = \max</tex>{<tex>\max\limits_{j=1}^{m-1} P_i/S_j, P_n/S_m</tex>}

Будем назвать Level-ом работы <tex> lvl(p_i(t)) </tex> - невыполненную часть работы <tex> p_i </tex> в момент времени <tex> t </tex>

Далее построим расписание, которое достигает нашей оценки <tex>w</tex>, с помощью Level-алгоритма.

Level - алгоритм:

<tex>t \leftarrow 0 </tex>
'''WHILE''' существуют работы с положительным level
Assign(t)
<tex>t1 \leftarrow min(s>t |</tex>работа выполненная в момент времени <tex> s)</tex>
<tex>t2 \leftarrow min(s>t | p_i(t)>p_j(t)</tex> && <tex> p_i(s) == p_j(s))</tex>
<tex> t \leftarrow min(t1,t2) </tex>
Построение расписания

Функция <tex>Assign(t)</tex>:

<tex>J = </tex>{<tex>i|p_i(t)>0</tex>}
<tex>M = </tex>{<tex>M_1,...,M_m</tex>}
'''WHILE''' (<tex>J</tex> != 0 && <tex>M</tex> != 0)
Найти множество работ <tex>I</tex> подмножество <tex>J</tex> ,level которых максимальный
<tex>r \leftarrow min</tex>(|<tex>M</tex>|,|<tex>I</tex>|)
Назначаем работы из мн-ва <tex>I</tex> на <tex>r</tex> самых быстрых машин из мн-ва <tex>M</tex>
<tex>J \leftarrow J</tex>\<tex>I</tex>
удаляем из мн-ва <tex>M</tex> <tex>r</tex> самых быстрых машин

==Доказательство корректности алгоритма==

==Пример==
[[Файл:qptmncmax.png|400px|thumb|right|Картинка к примеру]]

Пусть у нас есть 5 работ и 4 станка. Покажем работу алгоритма для данного случая.

В начальный момент времени начинаем обрабатывать работы с наибольшим временем выполнения <tex>J_1-J_4</tex> на станках <tex>M_1-M_4</tex> соответственно. В момент времени <tex>t_1</tex> <tex>lvl</tex> 4-ой работы опускается до времени выполнения 5-ой работы. С этого момента начинаем обрабатывать работы <tex> J_4,J_5</tex> на одном станке: <tex>M_4</tex>. В момент времени <tex>t_2</tex> происходит похожая ситуация. С этого момента времени работы <tex> J_1,J_2</tex> выполняются синхронно на двух станках <tex> M_1,M_2</tex>. Далее работы не пересекаются друг с другом и каждая заканчивается на ранее выделенных им станках.

==Время работы==
Level-алгоритм вызывает функцию Assign(t) в самом худшем случае <tex>O(n)</tex> раз. Функция Assign(t) выполняется за <tex>O(nm)</tex>. Итоговое время работы <tex>O(n^2m)</tex>.

==Литература==
* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 379 стр. {{---}} ISBN 978-3-540-69515-8

2-3 дерево

2012-06-06T21:28:03Z

217.118.78.38:

[[Файл:23дерево_new.jpg‎ |right|300px|thumb|Пример 2-3 дерева]]‎
''' 2-3 дерево ''' — структура данных, представляющая собой сбалансированное дерево поиска, такое что из каждого узла может выходить две или три ветви и глубина всех листьев одинакова. 2-3 дерево можно обобщить до [[B-дерево#B.2B-.D0.B4.D0.B5.D1.80.D0.B5.D0.B2.D0.BE|B+-дерева]].

== Структура ==
:*Все данные хранятся в листьях, в вершинах хранится вспомогательная информация,необходимая для организации поиска по поддеревьям.
:*Сыновья упорядочены по значению максимума поддерева сына.
:*Нелистовые вершины содержат 1 или 2 ключа, указывающие на диапазон значений в их поддеревьях.
:*Если нелистовая вершина имеет двух сыновей, то вершина хранит минимум правого поддерева; если трех, то первый ключ равен минимуму среднего поддерева, а второй ключ равен минимуму правого поддерева.
:*2-3 деревья сбалансированы, то есть каждое левое, правое, и центральное поддерево одинаковой высоты, и таким образом содержат равное (или почти равное) число данных.
:*Высота 2-3 дерева <tex>O(\log{n})</tex>, где <tex> n </tex> - количество элементов в дереве, поэтому операции поиска, добавления, удаления, слияния выполняются за время <tex>O(\log{n})</tex>.

== Операции ==
=== Поиск ===
Для поиска в 2-3 дереве необходимо последовательно просматривать ключи,
хранящиеся во внутренних ячейках, спускаясь от корня к листьям. Вначале ключ искомого
элемента сравнивается с первым ключом ячейки и, если искомый ключ меньше,
то осуществляется переход в левое поддерево. Иначе, сравниваем искомый ключ со вторым
ключом в ячейке (если второго ключа нет — поддерева всего два, то сразу переходим во
второе поддерево) и если наш ключ не превосходит второй ключ, то осуществляется переход
в среднее поддерево, а если превосходит, то идем в правое поддерево.

=== Вставка элемента ===
Есть два варианта вставки в 2-3 дерево.

1) Чтобы поместить новый ключ в узел, в котором содержится ровно один ключ, необходимо просто добавить его как второй ключ к узлу.

[[Файл:23treeadd3.png|440px|border]] [[Файл:23treeadd4.png|400px|border]]

2) Если же в узле уже содержатся два ключа, делим его на два "одноключевых" узла и вставляем средний ключ в родительский узел.Это может привести к тому, что придется делить родительский узел. Тогда таким же образом проходим до корня дерева.

[[Файл:23treeadd1.png|490px|border]] [[Файл:23treeadd2.png|400px|border]]

=== Удаление элемента ===
При удалении ключа из узла возникают три варианта.

1) Если после удаления ключа в узле содержится два ключа, то после удаления ничего не меняется.

2) Если же у ключа после удаления остался один элемент, то проверяем количество потомков второго ребенка того узла, ребенком которого является узел с удаляемым ключом. Если у него два ребенка, то присваиваем ему оставшийся один элемент. Вершину, оставшуюся без детей, удаляем рекурсивно.

[[Файл:23treedel1.png|330px|border]] [[Файл:23treedel2.png|300px|border]] [[Файл:23treedel5.png|300px|border]]

3) Иначе у него три ребенка. Тогда присваиваем узлу с одним ключом один из этих ключей, таким образом получая два узла с двумя ключами.

[[Файл:23treedel3.png|300px|border]] [[Файл:23treedel4.png|320px|border]] [[Файл:23treedel6.png|300px|border]]

=== Слияние двух деревьев ===
Возможно два варианта слияния двух деревьев.

1) Если два дерева одной высоты, то слияние представляет собой добавление общей вершины.

[[Файл:23treemerge1.png|400px|border]] [[Файл:23treemerge2.png|400px|border]]

2) Если два дерева разной высоты, то при слиянии меньшее добавляем как поддерево к одной из вершин большего.Если возникает ситуация,когда у необходимого узла уже есть три ребенка, то делим его на два узла с двумя поддеревьями, переходим в родителя.Таким образом будем проходим по дереву вверх пока дерево не станет корректным.

[[Файл:23treemerge3.png|400px|border]] [[Файл:23treemerge4.png|400px|border]]

== Cсылки ==
* [http://is.ifmo.ru/vis/tree23/tree23_ru.html is.ifmo.ru - Визуализатор 2-3 дерева — 1]
* [http://rain.ifmo.ru/cat/view.php/vis/trees/2-3-2002 rain.ifmo.ru - Визуализатор 2-3 дерева — 2]
* [http://ru.wikipedia.org/wiki/2-3-дерево Википедия — 2-3 дерево]
* Д. Кнут «Искусство программирования. Сортировка и поиск», часть 6.2.4
== См. также ==
* [[B-дерево]]
* [[Splay-дерево]]
* [[АВЛ-дерево]]
* [[Декартово дерево]]
* [[Красно-черное дерево]]

[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Деревья поиска]]