АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Формальное определение

Читайте также:
  1. A. Определение элементов операций в пользу мира
  2. I. Определение потенциального валового дохода.
  3. II. Определение геометрических размеров двигателя
  4. II.ОПРЕДЕЛЕНИЕ ПРОИЗВОДИТЕЛЬНОСТИ ЛА
  5. P.2.3.2.1(с) Определение удельной теплоемкости твердых тел
  6. Б) Определение жёсткости
  7. В) Определение объема движений
  8. В) Определение щёлочности.
  9. Введение в психологию человек. Определение психологии человека как науки. Задачи и место психологии в системе наук.
  10. Виды психологической помощи: определение, структура. Подготовка психолога. Личностные качества психолога
  11. Виды факторов производства и определение прав собственности экономических субъектов
  12. Вопрос Определение и классификация ЧС.

Алгоритм отождествляется с детерминированной машиной Тьюринга, которая вычисляет ответ по данному на входную ленту слову из входного алфавита . Временем работы алгоритма при фиксированном входном слове x называется количество рабочих тактов машины Тьюринга от начала до остановки машины. Сложностью функции , вычисляемой некоторой машиной Тьюринга, называется функция , зависящая от длины входного слова и равная максимуму времени работы машины по всем входным словам фиксированной длины:

6)Что записывается в стек при рекурсивном вызове

 

Стек можно использовать для того, чтобы избавится от рекурсии, так идея вызова рекурсивных функций сама использует стек. Адрес возврата и локальные переменные рекурсивной функции записываются в стек, благодаря чему каждый следующий рекурсивный вызов этой функции пользуется своим набором локальных переменных и за счёт этого работает корректно. Единственный минус такого использования в том, что очень хорошо отъедает память:D, поэтому надо избегать программ, которая допускает большой глубины рекурсии.

 

1) текущий уровень рекурсии

Число рекурсивных вызовов в каждый момент времени, называется текущим уровнем рекурсии.

2) зачем нужно делать перебор (пример)

3) алгоритм для нахождения к разрядных двоичных чисел

4) Размер задачи

длины или количества входных данных, называемых размером задачи.

5) Классы сложности

Классы сложности - множества вычислительных задач, примерно одинаковых по сложности вычисления. Более узко, классы сложности — это множества предикатов (функций, получающих на вход слово и возвращающих ответ 0 или 1), использующих для вычисления примерно одинаковые количества ресурсов. Каждый класс сложности (в узком смысле) определяется как множество предикатов, обладающих некоторыми свойствами.

Классом сложности X называется множество предикатов P(x), вычислимых на машинах Тьюринга и использующих для вычисления O(f(n)) ресурса, где n — длина слова x.

В качестве ресурсов обычно берутся время вычисления (количество рабочих тактов машины Тьюринга) или рабочая зона (количество использованных ячеек на ленте во время работы).

Класс P – задачи, которые могут быть решены за время, полиномиально зависящее от объёма исходных данных, с помощью детерминированной вычислительной машины (например, машины Тьюринга),

Класс NP — задачи, которые могут быть решены за полиномиально выраженное время с помощью недетерминированной вычислительной машины, то есть машины, следующее состояние которой не всегда однозначно определяется предыдущими. К классу NP относятся задачи, решение которых с помощью дополнительной информации полиномиальной длины, данной нам свыше, мы можем проверить за полиномиальное время. В частности, к классу NP относятся все задачи, решение которых можно проверить за полиномиальное время. Класс P содержится в классе NP. Классическим примером NP-задачи является задача о коммивояжёре.

 

6)И чем отличаются NP от Np полных

NP-задачи - это класс задач, которые можно решить за полиномиальное время (Р), но на машине, более мощной, чем обычная однопроцессорная машина — на недетерминированном (N) вычислителе.

Если некоторая NP – полная задача разрешима за полиномиальное время, то Р = NP. Иначе говоря, если в классе NP есть задача, не разрешимая за полиномиальное время, то все NP – полные задачи таковы.

1) Что такое глубина рекурсии

Максимальное число рекурсивных вызовов подпрограммы без возвратов, которое происходит во время выполнения программы, называется глубиной рекурсии.

 

2)

3) Какой основной прием у динамического программирования

Динамическое программирование в теории управления и теории вычислительных систем — способ решения сложных задач путём разбиения их на более простые подзадачи.

Ключевая идея в динамическом программировании достаточно проста. Как правило, чтобы решить поставленную задачу, требуется решить отдельные части задачи (подзадачи), после чего объединить решения подзадач в одно общее решение. Часто многие из этих подзадач одинаковы. Подход динамического программирования состоит в том, чтобы решить каждую подзадачу только один раз, сократив тем самым количество вычислений. Это особенно полезно в случаях, когда число повторяющихся подзадач экспоненциально велико.

4) Что такое класс сложности

Множество вычислительных проблем, для которых существуют алгоритмы, схожие по сложности, называется классом сложности.

5)


1 | 2 | 3 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.004 сек.)