Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Выполнили студенты 321 группы:

Аграновский Михаил

Брызгалов Антон

Мирошник Владислав

Смирнов Александр

Задача

Доказать, что задача «Составные числа» .

Постановка

Задано натуральное число . Составное ли оно, т.е. имеет ли ононатуральный неединичный и не равный делитель?

Решение

1. Генерация подсказки

В качестве подсказки для машины Тьюринга будем использовать всевозможные натуральные числа. Тогда генерация подсказки для каждой следующей машины Тьюринга будет заключаться в прибавлении единицы к предыдущей подсказке, то есть иметь сложность , где — длина подсказки. В случае поставленной задачи только на числах (где m – длина входа) может останавливаться ДМТ с положительным ответом.
Таким образом сложность генерации подсказки:

1. Деление уголком

В дальнейшем нам понадобится следующая Лемма:

Лемма (сложность деления уголком)

Временная сложность нахождения остатка (деления уголком): .

Доказательство леммы

Зададим делимое и делитель в двоичной системе.

• Делимое:

• Делитель:

Если , то остаток равен , частное — .

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

Тогда число битовых операций не превосходит , и для них выполнена оценка .

Доказательство завершено.

Если подсказка является делителем числа, то ДМТ, обрабатывающая данную подсказку, дает положительный ответ, в противном случае ДМТ не останавливается.

Для оценки итоговой временной сложности нам необходимо будет выбрать максимальное время работы на ДМТ, давших положительных ответ. (Здесь под работой ДМТ понимается время на генерацию подсказки + время работы самого алгоритма).

Воспользуемся результатом рассуждений, приведенных выше. Генерация подсказки имеет сложность , алгоритм нахождения остатка имеет временную сложность , где — длина входных данных (числа ). Итоговая сложность ( ) ограничена полиномом от входных данных. Поэтому задача проверки, является ли число составным, принадлежит классу NP.

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

Список файлов курсовой работы