Теория алгоритмов, Крупский В.Н., Плиско В.Е., 2009
Теория алгоритмов, Крупский В.Н., Плиско В.Е., 2009.
В учебном пособии изложены основы качественной и количественной теории алгоритмов; рассмотрены основные модели вычислений (машины Тьюринга, машины с неограниченными регистрами, рекурсивные функции) и связанные с ними подходы к формализации понятия алгоритма; даны начала алгоритмической теории множеств; представлены наиболее известные результаты об алгоритмической неразрешимости, а также элементы теории сложности вычислений.
Для студентов высших учебных заведений. Может быть полезно широкому кругу читателей, интересующихся основами теории вычислимости.
Неформальное понятие алгоритма.
Алгоритм — это точное предписание, которое задает вычислительный процесс (называемый в этом случае алгоритмическим), начинающийся с произвольного исходного данного (из некоторой совокупности возможных для данного алгоритма исходных данных) и направленный на получение полностью определяемого этим исходным данным результата. Алгоритм описывает порядок действий исполнителя для решения некоторой задачи. В настоящее время в качестве исполнителя алгоритма чаще всего выступает компьютер. В этом случае алгоритм называют также компьютерной программой. Однако исполнителем может быть и человек. Так, именно для человека формулируются известные из начальной школы правила (алгоритмы) сложения, вычитания, умножения и деления чисел столбиком. В этих алгоритмах возможными исходными данными служат упорядоченные пары натуральных чисел, записанных в десятичной системе, а возможными результатами — натуральные числа.
Именно с правилами арифметических действий связано само появление термина «алгоритм». Его происхождение связывают с именем среднеазиатского ученого аль-Хорезми (полное имя Абу Абдалла Мухаммед бен Муса аль-Маджуси аль-Хорезми), жившего в IX в., описавшего изобретенную в Индии позиционную десятичную систему счисления и сформулировавшего правила вычислений в этой системе. Именно благодаря латинскому переводу трактата аль-Хорезми (XII в.) позиционная система счисления стала известной в Европе, а правила счета в этой системе получили название алгоритмов по латинской транскрипции имени автора трактата. В широком смысле к алгоритмам можно отнести всякое точное предписание (например, подробный рецепт приготовления некоторого блюда или инструкцию по сборке предмета мебели из деталей).
ОГЛАВЛЕНИЕ
Предисловие
Глава 1. Начальные понятия теории алгоритмов
1.1. Неформальное понятие алгоритма
1.2. Конструктивные объекты
1.3. Алгоритмический процесс
1.4. Вычислимые функции
1.5. Сигнализирующее множество
Глава 2. Алгоритмическая теория множеств
2.1. Разрешимые множества
2.2. Полуразрешимые множества
2.3. Перечислимые множества
2.4. Равнообъемность понятий полуразрешимости и перечислимости
2.5. Теорема о графике
2.6. Основные факты о разрешимых и перечислимых множествах
Глава 3. Машины Тьюринга
3.1. Определение одноленточной машины Тьюринга
3.2. Вычисление функций на машинах Тьюринга
3.3. Синтез машин Тьюринга
3.4. Тезис Тьюринга
3.5. Универсальная машина Тьюринга
3.6. Теорема о компиляции
3.7. Многоленточные машины Тьюринга
Глава 4. Рекурсивные функции
4.1. Введение
4.2. Примитивно рекурсивные функции
4.3. Частично-рекурсивные функции
4.4. Нормальная форма Клини
Глава 5. Машины с неограниченными регистрами
5.1. Определение и примеры программ
5.2. МНР-вычислимость частично-рекурсивных функций
Глава 6. Нумерации вычислимых функций
6.1. Нумерации вычислимых функций натурального аргумента
6.2. Нумерации, порожденные машинами Тьюринга
6.3. Нумерации, порожденные МНР
Глава 7. Неразрешимые алгоритмические проблемы
7.1. Примеры невычислимых функций
7.2. Проблема остановки
7.3. Теорема Райса
Глава 8. Алгоритмические проблемы в математике и логике
8.1. Диофантово представление множеств и десятая проблема Гильберта
8.2. Проблема равенства слов в полугруппах
8.3. Арифметические множества и функции
Глава 9. Элементы теории сложности вычислений
9.1. Некоторые предварительные сведения
9.2. Меры сложности вычислений
9.3. Оценка эффективности вычислительных алгоритмов
Глава 10. Легко- и трудноразрешимые задачи
10.1. Класс Р
10.2. Булевы схемы полиномиального размера
10.3. Класс ??
10.4. Примеры заведомо трудных задач
Список литературы
Предметный указатель.
| Рейтинг: | 4.8 баллов / 2537 оценок |
| Формат: | Книга |
| Уже скачали: | 12896 раз |
Похожие Книги
Нам показалось, что Книги ниже Вас заинтересуют не меньше. Эти издания Вы так же можете скачивать и читать совершенно бесплатно на сайте!
-
Лесная съемка
Название: Лесная съемка Автор: Дубов С.Д, Поляков А.Н.Издательство: Лесная промышленностьГод: 1982Страниц: 204Формат: PDF Размер: 21.2 МбЯзык: русскийВ соответствии с программой изложены теория и прак . . .
-
Шаолиньское кунг-фу. Классика восточных единоборств
Название: Шаолиньское кунг-фу. Классика восточных единоборствАвтор: Максим Петров Год издания: 2009Издательство: Современная школаISBN: 978-985-513-477-1Страниц: 464 . . .
-
Knitting №2332 2007.
Название: Knitting №2332 2007 Автор: коллектив Издательство: Hamaka Год издания: 2007 Страниц: 85 Язык: Японский Формат: JPEG Размер: 21 МбОписание: Популярный японский журнал по вязанию спицами и к . . .
-
Орхидные северо-запада европейской России
Автор: П.Г.ЕфимовНазвание: Орхидные северо-запада европейской РоссииИздательство: Товарищество научных изданий КМКГод: 2011Формат: DjVuРазмер: 20 Mb Страниц: 211Язык: RUSФормат архива: RAR, 3% на восс . . .
-
Организмы, виды и эволюция
Автор: Н.Н.ИорданскийНазвание: Организмы, виды и эволюцияИздательство: Книжный дом «ЛИБРОКОМ»Год: 2011Формат: DjVuРазмер: 2 Mb Страниц: 176Язык: RUSФормат архива: RAR, 3% на восстановлениеРазмер архив . . .
-
Knitting №351 1990.
Название: Knitting №351 1990 Автор: коллектив Издательство: Hamaka Год издания: 1990 Страниц: 85 Язык: Японский Формат: JPEG Размер: 19 МбОписание: Популярный японский журнал по вязанию спицами и кр . . .
-
Anna №5 2008
Название: Anna №5 2008Издательство: BurdaГод издания: 2008Номер: № 5Язык: НемецкийCтраниц: 70Формат: JPEGРазмер: 39 МБОписание: Anna - популярный и известный журнал по рукоделию. В каждом номере предс . . .
-
Knitting №351 1990
Название: Knitting №351 1990Издательство: HamakaГод издания: 1990Номер: 351Язык: ЯпонскийCтраниц: 85Формат: JPEGРазмер: 19 МБОписание: Популярный японский журнал по вязанию спицами и крючком, с очень . . .
-
Knitting №2332 2007
Название: Knitting №2332 2007Издательство: HamakaГод издания: 2007Номер: № 2332Язык: ЯпонскийCтраниц: 85Формат: JPEGРазмер: 21 МБОписание: Популярный японский журнал по вязанию спицами и крючком, с оч . . .
-
Российский исторический журнал "Родина" №7
Название: Российский исторический журнал "Родина" №7Автор: Коллектив авторовИздательство: Родина-ПрессГод: 2009Страниц: 113Формат: PDFЯзык: РусскийРазмер: 29,57 МбРоссийский исторический журнал. Входи . . .
Вы не зарегистрированы!
Если вы хотите скачивать книги, журналы и аудиокниги бесплатно, без рекламы и без смс, оставлять комментарии и отзывы, учавствовать в различных интересных мероприятиях, получать скидки в книжных магазинах и многое другое, то Вам необходимо зарегистрироваться в нашей Электронной Библиотеке.
Отзывы читателей
Ой!
К сожалению, в нашей Бесплатной Библиотеке пока нет отзывов о Книге Теория алгоритмов, Крупский В.Н., Плиско В.Е., 2009. Помогите нам и другим читателям окунуться в сюжет Книги и узнать Ваше мнение. Оставьте свой отзыв или обзор сейчас, это займет у Вас всего-лишь несколько минут.