Бесплатная библиотека - 1 338 003 изданий в библиотеке

Введение в сложность вычислений, Крупский В.Н., 2006

Книга Введение в сложность вычислений, Крупский В.Н., 2006

Введение в сложность вычислений, Крупский В.Н., 2006.
   Учебное пособие написано по материалам полугодового спецкурса, читавшегося автором на механико-математическом факультете
МГУ им. М. В. Ломоносова для студентов и аспирантов кафедры математической логики и теории алгоритмов, а также специальности
«Защита информации». Излагаются основные идеи и методы теории сложности вычислений.
Для студентов, аспирантов и специалистов, занимающихся анализом эффективности алгоритмов.

Модели Тьюринга.
Это семейство моделей вычислений наиболее честно отражает время вычислений. Возможных вариантов определения много. Машина Тьюринга состоит из управляющего устройства (УУ) и потенциально бесконечной внешней памяти, структура которой не меняется со временем. Она снабжена программой, задающей правила ее функционирования.
Память разбита на одинаковые ячейки, предназначенные для хранения букв фиксированного конечного алфавита (одна буква в ячейке). Имеется одна или несколько (конечное число) читающе-пишущих головок. В каждый момент времени головка обозревает одну ячейку памяти. За один такт работы головка может изменить содержимое этой ячейки и переместиться к одной из соседних (или остаться на месте). Функционированием головок управляет УУ. В каждый момент времени УУ находится в одном из фиксированного конечного множества внутренних состояний. Один такт работы состоит в следующем: машина читает содержимое обозреваемых ячеек и внутреннее состояние, выбирает из программы инструкцию, однозначно определяемую этими данными, и исполняет ее. В инструкции сказано, каким должно стать новое внутреннее состояние, какие буквы должны быть записаны в обозреваемые ячейки и куда должны переместиться головки.

Рейтинг: 4.8 баллов / 2537 оценок
Формат: Книга
Уже скачали: 12777 раз

Похожие Книги

Нам показалось, что Книги ниже Вас заинтересуют не меньше. Эти издания Вы так же можете скачивать и читать совершенно бесплатно на сайте!

  • Аудиокнига Хроники Тральфамадора (аудиокнига)

    Хроники Тральфамадора (аудиокнига)

    Название: Хроники Тральфамадора (аудиокнига)Автор: Курт ВоннегутИздательство: Нигде не купишьИсполнитель: Герасимов ВячеславГод выпуска: 2008Аудио: MP3, 128 Кбит/с, 44 кГц, стереоВремя звучания: 46:22 . . .

  • Аудиокнига Кто подслушал слоненка Госпела (аудиокнига)

    Кто подслушал слоненка Госпела (аудиокнига)

    Название: Кто подслушал слоненка Госпела (аудиокнига)Автор: Найо МаршИздательство: Логос ВОСИсполнитель: Илья ПрудовскийГод выпуска: 2001Аудио: MP3, 128 Кбит/с, 44.1 кГц, стереоВремя звучания: 11:19:0 . . .

  • Журнал Odkrywca 2013-06

    Odkrywca 2013-06

    Название: Odkrywca 2013-06 (173)Издательство: Instytut Badan Historycznych i KrajoznawczychГод: 2013Формат: pdfРазмер: 64 MbКол-во страниц: 76Язык: PolishПольский военно-исторический журналuploaded.ne . . .

  • Аудиокнига Калина красная (Аудиокнига)

    Калина красная (Аудиокнига)

    Название: Калина краснаяАвтор: Василий ШукшинИздательство: Аудиокнига своими рукамиЭту книгу озвучил: Александр СиницаГод выпуска: 2013Жанр: ПовестьАудио кодек: mp3Битрейт аудио: 192 kbpsПродолжительн . . .

  • Аудиокнига Пещера Рыжего Монаха (аудиокнига)

    Пещера Рыжего Монаха (аудиокнига)

    Название: Пещера Рыжего Монаха (аудиокнига)Автор: Коробейников Г.Издательство: Нигде Не КупишьИсполнитель: Заборовский Ю.Год выпуска: 2008Аудио: MP3, 128KbpsВремя звучания: 13 часов 11 минутРазмер: 74 . . .

  • Журнал Военно-исторический журнал "Воин" №14

    Военно-исторический журнал "Воин" №14

    Название: Военно-исторический журнал "Воин" №14 Издательство: ООО "Братина"Год: 2011Формат: PDF (HQ)Размер: 56 MbСтраниц 92Язык: RussianScan: devoid of fear Военно-исторический журнал “Воин” охватывае . . .

  • Журнал Цветочный клуб №8 2013

    Цветочный клуб №8 2013

    Название: Цветочный клубИздательство: ПлантарияГод выхода: 2013Номер: 8Страниц: 68Формат: PDFКачество: ХорошееЯзык: РусскийРазмер: 35.4 Мб«Цветочный клуб» - ежемесячный иллюстрированный журнал о цвета . . .

  • Журнал Quatro. Wloski lekki krazownik [Modelik 2012/19]

    Quatro. Wloski lekki krazownik [Modelik 2012/19]

    Название:Quatro. Wloski lekki krazownikГод / месяц:2012/№19Масштаб:1:200 Формат:jpg Формат листов:А4 Язык:ПольскийРазмер:18mb Листов:18Модель из бумаги итальянского лёгкого крейсера времен 1 Мировой . . .

  • Журнал Odkrywca 2013-03

    Odkrywca 2013-03

    Название: Odkrywca 2013-03 (170)Издательство: Instytut Badan Historycznych i KrajoznawczychГод: 2013Формат: pdfРазмер: 64 MbКол-во страниц: 76Язык: PolishПольский военно-исторический журналuploaded.ne . . .

  • Книга Мультимедийная энциклопедия секса

    Мультимедийная энциклопедия секса

    Язык: русский Формат: ISO, NRG, MDF Размер: 691.34 Мб Мультимедийная энциклопедия секса дает возможность сохранить в секрете все Ваши интимные проблемы и при этом окажет конкретную помощь в их . . .

Вы не зарегистрированы!

Если вы хотите скачивать книги, журналы и аудиокниги бесплатно, без рекламы и без смс, оставлять комментарии и отзывы, учавствовать в различных интересных мероприятиях, получать скидки в книжных магазинах и многое другое, то Вам необходимо зарегистрироваться в нашей Электронной Библиотеке.

Войти Регистрация

Отзывы читателей

Ой!

К сожалению, в нашей Бесплатной Библиотеке пока нет отзывов о Книге Введение в сложность вычислений, Крупский В.Н., 2006. Помогите нам и другим читателям окунуться в сюжет Книги и узнать Ваше мнение. Оставьте свой отзыв или обзор сейчас, это займет у Вас всего-лишь несколько минут.