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

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

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

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

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

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

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

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

  • Книга Историография и источниковедение истории стран Азии и Африки. Золотоордынские ханы 60–70-х годов XIV в.

    Историография и источниковедение истории стран Азии и Африки. Золотоордынские ханы 60–70-х годов XIV в.

    Автор: Григорьев А.П.Название: Историография и источниковедение истории стран Азии и Африки. Золотоордынские ханы 60–70-х годов XIV в.Издательство: ЛенинградГод: 1983Страницы: 9-54Формат: pdfРазмер: 2 . . .

  • Книга Цивилизации. Выпуски 1,3,5,6,7

    Цивилизации. Выпуски 1,3,5,6,7

    Автор: Барг М.А., Чубарьян А.О. (ред.)Название: Цивилизации. Выпуски 1,3,5,6,7Издательство: НаукаГод издания: 1992-2006Формат: DjVuЯзык: русскийCтраниц: 233+239+242+251+282Размер: 10 МБСборник статей, . . .

  • Книга Ядерно-физические константы. Справочник

    Ядерно-физические константы. Справочник

    Название: Ядерно-физические константы. Справочник Автор: Гордеев И. В., Кардашев Д. А., Малышев А. В. Издательство: Госатомиздат Страниц: 511 Формат: DJVU Размер: 20.23 Мб Качество: Нормальное Язык: Р . . .

  • Книга Конструкция, ремонт и регулировка приспособлений для металлорежущих станков

    Конструкция, ремонт и регулировка приспособлений для металлорежущих станков

    Название: Конструкция, ремонт и регулировка приспособлений для металлорежущих станков Автор: Большаков И.С. Издательство: Фабрика экранных учебно-наглядных пособий ВТПП ГК СМ СССР по профтехобразовани . . .

  • Книга Тяжёлый танк «ПАНТЕРА». Первая полная энциклопедия pdf 13,84Мб

    Тяжёлый танк «ПАНТЕРА». Первая полная энциклопедия pdf 13,84Мб

    Название: Тяжёлый танк «ПАНТЕРА». Первая полная энциклопедияГод выпуска: 2012Издательство: М.: Стретегия КМ : Яуза : ЭксмоАвтор: М.Коломиец Язык: РусскийСтраниц: 338Качество: ХорошееФормат: PDFРазмер: . . .

  • Книга Vom Wort zum Text 1

    Vom Wort zum Text 1

    Название: Vom Wort zum Text 1 Автор: Коллектив авторов Издательство: Март Страниц: 252 Формат: PDF Размер: 210МВ Качество: Отличное Язык: Немецкий Жанр: Языки Год издания: 2002 "От слова к тексту" - к . . .

  • Книга Анабиоз в 5 томах fb2, rtf 20,98Мб

    Анабиоз в 5 томах fb2, rtf 20,98Мб

    Название: Анабиоз в 5 томахГод выпуска: 2011-2012Издательство: Олма Медиа ГруппСерия: АнабиозАвтор: РазныеЯзык: РусскийСтраниц: 1500Качество: ХорошееФормат: FB2, RTFРазмер: 20,98 MbСерия книг Анабиоз . . .

  • Книга Советские атомные ледоколы

    Советские атомные ледоколы

    Название: Советские атомные ледоколы Автор: Соколов Б.М., Кучиев Ю.С., Синяев А.К. и др Издательство: Мортехинформреклама Страниц: 81 Формат: DJVU Размер: 31.10Мб Качество: Отличное Язык: Русский Год . . .

  • Книга Специальные виды литья pdf 5Мб

    Специальные виды литья pdf 5Мб

    Название: Специальные виды литьяАвтор: Боровский Ю.Ф.Издательство: Фабрика экранных учебно-наглядных пособий ВТПП ГК СМ СССР по профтехобразованиюГод: 1966Страниц: 141Язык: русскийФормат: pdfРазмер: 5 . . .

  • Книга Япония: мифы и реальность

    Япония: мифы и реальность

    Название: Япония: мифы и реальность Автор: Кравцевич А. И. (ред.) Издательство: "Восточная литература" РАН Страниц: 335 Формат: PDF Размер: 37.04 Мб Качество: Отличное Язык: Русский Год издания: 1999 . . .

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

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

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

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

Ой!

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