Партнерка на США и Канаду по недвижимости, выплаты в крипто
- 30% recurring commission
- Выплаты в USDT
- Вывод каждую неделю
- Комиссия до 5 лет за каждого referral
Теория алгоритмов
Во всех сферах своей деятельности, и частности в сфере обработки информации, человек сталкивается с различными способами или методиками решения задач. Они определяют порядок выполнения действий для получения желаемого результата. Это можно трактовать как первоначальное или интуитивное определение алгоритма. Некоторые дополнительные требования приводят к неформальному определению алгоритма.
Алгоритм _____________________________________________________________________
_____________________________________________________________________________________
_____________________________________________________________________________________
Несмотря на усилия исследователей, отсутствует одно исчерпывающе строгое определение понятия алгоритм, в теории алгоритмов были введены различные формальные определения алгоритма и удивительным научным результатом является доказательство эквивалентности этих формальных определений в смысле их равномощности. Варианты словесного определения алгоритма принадлежат российским ученым и
Колмогоров: Алгоритм ____________________________________________________________
_____________________________________________________________________________________
_____________________________________________________________________________________
Марков: Алгоритм _________________________________________________________________
_____________________________________________________________________________________
_____________________________________________________________________________________
Отметим несколько основных общих свойств алгоритмов:
¾ дискретность ___________________________________________________________________
________________________________________________________________________________
¾ детерминированность ____________________________________________________________
________________________________________________________________________________
¾ массовость __________________________________________________________
________________________________________________________________________________
¾ направленность __________________________________________________________________
________________________________________________________________________________
________________________________________________________________________________
Другие формальные определения понятия алгоритма связаны с введением специальных математических конструкций (машина Поста, машина Тьюринга, рекурсивно-вычислимые функции Черча) и постулированием тезиса об эквивалентности такого формализма и понятия алгоритм.
Тезис Чёрча:____________________________________________________________________
_____________________________________________________________________________________
_____________________________________________________________________________________
Тезис Чёрча нельзя доказать, поскольку интуитивное понятие алгоритма строго не определяется и его нельзя использовать в доказательных математических рассуждениях.
Машина Тьюринга
Машина Тьюринга задается системой пяти объектов 
:
– _______________________________________________________________
– _______________________________________________________________
– _______________________________________________________________
– _______________________________________________________________
– _______________________________________________________________
Машина Тьюринга является абстрактной математической моделью, функционирующей в целочисленном неотрицательном времени: 
Машина Тьюринга состоит из следующих частей:
1. Лента – _____________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
2. Управляющая головка –___________________________________________________
______________________________________________________________________
______________________________________________________________________
ß | |||||||
… |
|
| … |
| … |
| … |
3. Программа – ___________________________________________________________
Программу машины Тьюринга можно задавать таблицей переходов (функциональной схемой): строки соответствуют символам алфавита, столбцы – состояниям машины.
Схема функционирования машины Тьюринга:
_____________________________________________________________________________________
_____________________________________________________________________________________
_____________________________________________________________________________________
_____________________________________________________________________________________
_____________________________________________________________________________________
_____________________________________________________________________________________
_____________________________________________________________________________________
_____________________________________________________________________________________
_____________________________________________________________________________________
_____________________________________________________________________________________
_____________________________________________________________________________________
_____________________________________________________________________________________
_____________________________________________________________________________________
_____________________________________________________________________________________
_____________________________________________________________________________________
_____________________________________________________________________________________
Рассмотрим пример. Алфавит 
, где с – вспомогательный символ. Задана функциональная схема машины Тьюринга:
q1 | q2 | q3 | q4 | q5 | |
0 | q5 R | q3 1 L | q0 | R | q3 L |
1 | R | L | q0 L | q4 L | |
a | R | L | 0 L | q2 c R | |
b | R | L | 0 L | R | |
c | q5 R | 0 L |
Рассмотрим работу этой машины Тьюринга на входном слове 
.
ß | |||||||||||
0 | a | b | a | a | b | 0 | 0 | 0 | 0 | 0 | 0 |
ß | |||||||||||
0 | a | b | a | a | b | 0 | 0 | 0 | 0 | 0 | 0 |
ß | |||||||||||
0 | c | b | a | a | b | 0 | 0 | 0 | 0 | 0 | 0 |
Составим диаграмму Тьюринга для этой задачи:
Рассмотрим еще пример. Составим функциональную схему машины Тьюринга для вычисления функции 
. Будем представлять натуральное число последовательностью единиц. Например, 1 – 1, 2 – 11, …, 6 – …
q1 | q2 | ||||
0 | |||||
1 | |||||
+ |
Рассмотрим работу этой машины Тьюринга на входном слове 
.
ß | |||||||||||
0 | 1 | 1 | 1 | 1 | 1 | 1 | + | 0 | 0 | 0 | 0 |
ß | |||||||||||
0 | 1 | 1 | 1 | 1 | 1 | 1 | + | 0 | 0 | 0 | 0 |
…
ß | |||||||||||
0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
Составим диаграмму Тьюринга:
