Xreferat.com » Рефераты по информатике и программированию » Формализация понятия алгоритма

Формализация понятия алгоритма

4 5 6 7 8 9 0

Нач. состояние

Сти

раем палочку

(крайнеправый сим

вол |)

qo LqerH LqeH 1qerH 2qerH 3qerH 4qerH 5qerH 6qerH 7qerH 8qerH 9qerH 0qerH ql 1qrП |qlЛ 1qerH 2qerH 3qerH 4qerH 5qerH 6qerH 7qerH 8qerH 9qerH 0qerH

Про

дви-жение вправо до пер

вой | , либо если нет | , то пе

реход в q2l

qr Lq2lЛ |q2rH 1qrП 2qrП 3qrП 4qrП 5qrП 6qrП 7qrП 8qrП 9qrП 0qrП

Движе-ние влево до на

чала слова из цифр и стоп

q2l L!H |qerH 1q2lЛ 2q2lЛ 3q2lЛ 4q2lЛ 5q2lЛ 6q2lЛ 7q2lЛ 8q2lЛ 9q2lЛ 0q2lЛ

Движение вправо на | до пер

вой пусто-ты

q2r Lq3lЛ |q2rП 1qerH 2qerH 3qerH 4qerH 5qerH 6qerH 7qerH 8qerH 9qerH 0qerH

Сти

раем палочку.

Дви

жемся до пер

вой

циф

ры и увели

чива

ем ее на единицу

q3l LqerH LqdЛ 1qerH 2qerH 3qerH 4qerH 5qerH 6qerH 7qerH 8qrH 9q3lЛ 0q2lЛ qd 1qrH |qdЛ 2qrH 3qrH 4qrH 5qrH 6qrH 7qrH 8qrH 9qrH 0qrЛ 1qrЛ

Рис.4. Машина Тьюринга для U((n)1)=(n)10

Оценим сложность этого алгоритма. В начале работы каретка пройдет (n-1) символ при движении влево и (n-1) символ при движении обратно, т.е. 2(n-1). На втором проходе - 2(n-2) и т.д. Отсюда число пройденных палочек, а следовательно и выполненных команд будет равно n(n-1). Машина n раз выполнит команду, увеличения текущей цифры на 1. Количество просмотров цифр будет равно Формализация понятия алгоритма([log10n]+1)([log10n]).Таким образом, получаем

n(n-1)+n+[log10n]× ([log10n]+1) @ n2+[log10n(log10n+1)]

Пример 4. Построить машину Тьюринга, для сравнения двух чисел a и b, заданных в унарной форме.

Формализация понятия алгоритма  если  Формализация понятия алгоритма

Пусть на ленте числа a и b заданы в унарной форме. Каретка располагается над лентой так, как показано на рисунке 5,

Формализация понятия алгоритма  Формализация понятия алгоритма

Рис.5.

т.е. над крайне правым символом | числа a . Cравнивать числа a и b будем, стирая попарно одну палочку в записи a и одну палочку в записи b. Если останутся палочки только в записи a, то значит a>b, если только в записи b, то a TD width=106 style='width:79.85pt;border-left:none;border-top:none;border-right:solid windowtext .75pt;border-bottom:solid windowtext .75pt' P style='margin-top:6.0pt'FONT style='font-size:10.0PT'FONT style='color:black;font-size:12.0pt'|qSUBa>bH

xqCHLЛ qCHR Lq’a=bЛ |qab Lq’a>bЛ |qa>bП xqa>bП q’a>b 1!H |qa>bЛ Lq’a>bЛ

qa

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: