Вычислимость и сложность задач на примере машин Тьюринга
Понятие вычислимости, сложности и алгоритма решения задач. Неразрешимая проблема остановки и универсальность машин Тьюринга, их вычислимые функции и перечислимость. Определение примитивных рекурсивных функций, классы сложности вычислительных задач.
| Рубрика | Программирование, компьютеры и кибернетика |
| Предмет | Теория алгоритмов |
| Вид | реферат |
| Язык | русский |
| Прислал(а) | ivan.ponurenko |
| Дата добавления | 02.05.2014 |
| Размер файла | 49,0 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Подобные документы
Временная и ёмкостная сложность программы. Размер входных данных. Связь сложности в худшем случае и в среднем. Понятие оптимальной программы. Классы вычислительной сложности программ. Эквивалентность по сложности. Примеры классов вычислительной сложности.
презентация [77,3 K], добавлен 19.10.2014Временная, пространственная и асимптотическая сложности. Основные классы сложности в теории алгоритмов. Сведение как преобразование одной задачи к другой. Проблема равенства классов P и NP. Характеристика основных иерархических отношений между классами.
реферат [16,9 K], добавлен 09.04.2012Описание формальной модели алгоритма на основе рекурсивных функций. Разработка аналитической и программной модели алгоритма для распознающей машины Тьюринга. Разработка аналитической модели алгоритма с использованием нормальных алгоритмов Маркова.
курсовая работа [1,5 M], добавлен 07.07.2013Общее понятие алгоритма и меры его сложности. Временная и емкостная сложность алгоритмов. Основные методы и приемы анализа сложности. Оптимизация, связанная с выбором метода построения алгоритма и с выбором методов представления данных в программе.
реферат [90,6 K], добавлен 27.11.2012Принципы работы и основы программирования машины Тьюринга, а также перечень правил написания алгоритмов на ее эмуляторе. Особенности решения задачи по сложению нескольких чисел в двоичной системе путем реализации ее алгоритма на эмуляторе машины Тьюринга.
контрольная работа [82,4 K], добавлен 05.12.2010Средства формализации процесса определения спецификаций. Назначение языка (PSL) и анализатора определения задач (PSA). Разработка алгоритма решения задачи, критерии оценки его сложности. Локальный и глобальный уровни повышения эффективности алгоритмов.
контрольная работа [144,9 K], добавлен 26.10.2010Разложение функций по переменным. Совершенная дизъюнктивная нормальная форма. Разрешимoсть задач в классической теории алгоритмов и их трудоемкость. Память и время как количественная характеристика алгоритма (применительно к машине Тьюринга и ЭВМ).
дипломная работа [59,9 K], добавлен 17.04.2009Назначение и применение электронно-вычислительных машин. Этапы решения задач на ЭВМ. Общая характеристика алгоритмического языка QuickBASIC: символы, простейшие конструкции, арифметические выражения. Определение нестандартных функций оператором DEF FN.
методичка [322,1 K], добавлен 18.12.2014Простое вычислительное устройство машина Тьюринга и ее алгоритмические свойства. Тезис Черча–Тьюринга и моделирование машины Тьюринга (операции перезаписи ячеек, сравнения и перехода к другой соседней ячейке с учетом изменения состояния машины).
контрольная работа [23,3 K], добавлен 24.04.2009Классы сложности задач в теории алгоритмов. Общие сведения о симметричной и ассиметрично-ключевой криптографии. "Лазейка" в односторонней функции. Криптографическая система RSA. Криптографическая система Эль-Гамаля. Алгоритм обмена ключами Диффи-Хеллмана.
курсовая работа [706,6 K], добавлен 06.06.2010Развитие навыков работы с табличным процессором Microsoft Excel и программным продуктом MathCAD и применение их для решения задач с помощью электронно-вычислительных машин. Схема алгоритма. Назначение функции Линейн и метода наименьших квадратов.
курсовая работа [340,4 K], добавлен 17.12.2014Более строгое описание алгоритма, чем общее или формализация понятия алгоритма. Три подхода к формализации: теория конечных и бесконечных автоматов, теория вычислимых (рекурсивных) функций и л-исчисление Черча. Воображаемые машины Поста и Тьюринга.
реферат [370,0 K], добавлен 09.02.2009Цель ТРИЗ - области знаний о механизмах развития технических систем и методах решения изобретательских задач. Значение точной формулировки мини-задачи. Три вида противоречий в порядке возрастания сложности разрешения. Законы развития технических систем.
презентация [248,5 K], добавлен 18.03.2017Характеристика этапов решения задач на электронных вычислительных системах. Разработка алгоритма и основы программирования. Язык Ассемблера, предназначенный для представления в удобочитаемой символической форме программ, записанных на машинном языке.
контрольная работа [60,5 K], добавлен 06.02.2011Понятие алгоритма и анализ теоретических оценок временной сложности алгоритмов умножения матриц. Сравнительный анализ оценки временной сложности некоторых классов алгоритмов обычным программированием и программированием с помощью технологии Open MP.
дипломная работа [1,6 M], добавлен 12.08.2017Классы задач P и NP, их сводимость. Примеры NP-полных и NP-трудных задач. Сущность метода поиска с возвратом. Алгоритмы решения классических задач комбинаторного поиска. Решение задачи о восьми ферзях. Поиск оптимального решения методом ветвей и границ.
презентация [441,5 K], добавлен 19.10.2014Назначение и возможности пакета MATLAB, его основные составляющие. Набор вычислительных функций. Роль интерполяции функций в вычислительной математике. Пример интерполяции с четырьмя узлами. Интерполирование и сглаживание, схемы решения задач в MATLAB.
курсовая работа [594,5 K], добавлен 28.12.2012Компиляторы - инструменты для решения вычислительных задач с использованием бинарного кода. Проблема выбора "правильного" компилятора. Применение компиляторов языка С++. Оценка MinGW, Borland Builder, Intel C++ Professional Edition, Watcom и Visual Studi.
контрольная работа [4,5 M], добавлен 05.10.2012История создания и развития профессиональных электронных вычислительных машин (ЭВМ), предназначеных для решения узкого круга специальных задач, и все программные и технические средства которых ориентированы на конкретную профессию или выполняемую задачу.
презентация [7,0 M], добавлен 11.07.2011Характеристика параметрических методов решения задач линейного программирования: методы внутренней и внешней точки, комбинированные методы. Алгоритм метода барьерных поверхностей и штрафных функций, применяемых для решения задач большой размерности.
контрольная работа [59,8 K], добавлен 30.10.2014
