x-uni.com
регистрация / вход
сейчас на линии 59 чел.
x-uni.com
x-uni.com
 
Математика
Биология
Литература
Русский язык
ВИДЕО
Физика
Химия
История
Английский
 
ВИДЕО
 
 
регистрация / вход
сейчас на линии 59 чел.
Теория алгоритмов, Крупский В.Н., Плиско В.Е., 2009

Теория алгоритмов, Крупский В.Н., Плиско В.Е., 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. Примеры заведомо трудных задач
Список литературы
Предметный указатель.

Скачать бесплатно на сайте fileskachat.com

Предложения интернет-магазинов

Занковские педагогические чтения. 2009-2010. Опыт. Достижения. Перспективы

  Издательство: Дом Федорова, 2010 г.

Цена: 152 руб.   Купить

В сборнике "Занковские педагогические чтения. 2009-2010. Опыт. Достижения. Перспективы" представлены работы как ученых, разработчиков системы развивающего обучения Л.В. Занкова, авторов УМК, специалистов вузов и ИПК, так и учителей-практиков. Основой содержания сборника стали материалы Занковских педагогических чтений, состоявшихся в 2009-2010 годах, а также работы участников региональных и межрегиональных семинаров. В материалах освещается широкий круг вопросов, связанных прежде всего с введением Федерального государственного образовательного стандарта начального общего образования, осмыслением потенциала системы Л.В. Занкова для реализации его требований. Кроме того, издание включает разработки уроков, выполненные учителями. Сборник может быть полезен тем, кого интересуют теория и практика современного начального образования, развивающего обучения.


Общая химия: Учебник

Автор(ы): Хомченко Иван Гавриилович   Издательство: Новая волна, 2014 г.

Цена: 302 руб.   Купить

В книге изложены основные понятия и законы химии, теория строения атома, учение о химической связи, теория растворов и электрохимических процессов. Описаны свойства неорганических соединений. В разделе, посвященном органической химии, рассмотрены теория химического строения органических соединений А. М. Бутлерова и свойства органических соединений отдельных классов. Учебник предназначен для учащихся техникумов, колледжей и средних учебных заведений с расширенной программой по химии. Может быть полезен преподавателям химии и студентам нехимических вузов, изучающим общую или органическую химию. 2-е издание, исправленное и дополненное.


Биология. Большой справочник для подготовки к ЕГЭ

Автор(ы): Колесников Сергей Ильич   Издательство: Легион, 2015 г.  Серия: Готовимся к ЕГЭ

Цена: 250 руб.   Купить

Издание содержит развёрнутый теоретический материал, предусмотренный ФГОС и необходимый для систематизации знаний и подготовки к ЕГЭ по биологии, а также к другим формам контроля и аттестации в 9-11 классах. В справочнике представлены основные теоретические сведения, термины, понятия, законы биологии. Материал снабжён таблицами, схемами, иллюстрациями. Книга адресована прежде всего старшеклассникам, а также может быть полезна учителям для организации повторения. Издание является частью учебно-методического комплекса "Биология. Подготовка к ЕГЭ", включающего пособия "Биология. Подготовка к ЕГЭ-2016", "Биология. ЕГЭ. Раздел: "Генетика. Теория, тренировочные задания", "Биология. ЕГЭ. Раздел: "Эволюция органического мира. Теория, тренировочные задания" и др. Учебные пособия издательства "Легион" Допущены к использованию в образовательном процессе приказом Минобрнауки России № 729 от 14.12.2009. 2-е издание.


Информатика. Теоретические основы. Учебное пособие для подготовки к ЕГЭ (+CD)

Автор(ы): Нурмухамедов Геннадий Михайлович, Соловьева Людмила Федоровна   Издательство: BHV, 2012 г.  Серия: Информатика и ИКТ

Цена: 229 руб.   Купить

Книга предназначена для углубленной подготовки учащихся 11 классов и выпускников общеобразовательных школ по теоретической информатике и включает следующие разделы: информатика и информация, устройство ЭВМ, двоичная арифметика, бинарная логика, информационные системы, информационные модели, основы теории алгоритмов, программный способ записи алгоритмов. Представленные материалы также могут быть полезны студентам средних специальных учебных заведений и младших курсов профильных вузов. Книга сопровождается авторским компакт-диском, содержащим электронную версию книги с элементами интерактивного обучения.

ПЕДСОВЕТ / ФОРУМ

Новости образования

Новости науки

флаг италииX-UNI рекомендует репетитора итальянского языка: yuliyavenezia (Скайп).

Репетитор по Скайпу без посредников

Неограниченная аудитория, свободный график. Начните свой бизнес здесь!