Верхние и нижние оценки сложности алгоритмов. Разрешимые и неразрешимые задачи. Классы сложности алгоритмов P, EXP, NP.

 

Для реальной задачи набор данных разбивается на классы, таким образом, чтобы для каждого из этих классов количество действий, выполняемых алгоритмом было одинаково. Разбиение на классы идет каким-либо разумным способом с точки зрения решения задачи.

· Верхняя оценка (худший случай)

· Нижняя оценка (лучший случай)

· Средняя оценка (что «усредненное», комбинаторные методы или методы теорий вероятностей).

Задача – это некоторый вопрос, на который необходимо получить или вычислить ответ. Задача может быть решена (т.е. является разрешимой), если построен алгоритм, приводящий к результату решения задачи.

Неразрешимые задачи:

· Проблема останова (на нескольких исходных данных машина Тьюринга может не останавливаться, не давать результата). Проблема состоит в построении машины Тьюринга, которая, получая на входе код, производит машину Тьюринга и входные данные этой машины, определяет, останавливается ли машина. Доказано, что такую машину построить нельзя.

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

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

2 вид: задачи частные (задачи индивидуальные) получаются из общей задачи, если список параметров получает конкретные значения.

Сложностью задачи называется сложность самого простого алгоритма, который решает эту задачу. Поиск самого простого алгоритма – оптимизация алгоритма.

· Легкие задачи (если есть величина n, то сложность будет o(n),o(n^2),o(n^3) – полиномиальная сложность, задачи класса P (Polinom)).

· Задачи класса NP («нарушители границы» задачи могут быть решены за полиномиальное время, только машина должна быть многопроцессорной и должен использоваться недетерминированные вычислитель).

· Трудные задачи (o(2^n),o(3^n)…, задачи класса EXP (Exponenta)).

Типы данных

Концепция типа данных

 

1. Любая переменная, константа, выражение или функция относятся к некоторому типу;

2. Тип данных определяет множество значений, к которым относится константа, и, которые могут принимать переменные, выражение или функция;

3. Каждая операция и функция требует для своего выполнения аргументов строго определенного типа и вырабатывает результат так же строго определенного типа.

Следствия:

1. Все новые типы данных определяются только на основе уже существующих;

2. Значения новых типов данных всегда состоят из комбинации значений предыдущих типов данных, поэтому значения новых типов называются составными;

3. Если при построении нового типа данных используется только один составляющий тип, то он называется базовым;

4. Число различных значений, входящих в тип данных, называется мощностью типа;

5. Каждый язык высокого уровня дает свои изобразительные средства для указания принадлежности какой-либо переменной к определенному типу;

6. Любой язык для любого типа данных вводит всегда 2 операции: это присваивание и сравнение на равенство;

7. Если для значения какого-либо типа данных определяется операция отношения, то такой тип данных называется скалярным.

Понятие типа данных. Классификации типов данных в языках Pascal и С.

 

Тип данных – определяет множество значений, к которым относится константа и которые может принимать переменная, выражение или функция.

Новые типы данных могут быть определены только на основе предыдущих.

Pascal:

Стандартные:

· Integer;

· Real;

· Boolean;

· Char;

· String;

· Text.

Сложные:

· Перечисление (type имя=(имя знач1, имя знач2,…));

· Отрезок (type имя=min_знач … max_знач);

· Множество (type имя=set of базовый тип);

· Массив (type имя=array[тип индекса] of базовый тип);

· Запись (type имя=record имя_поля1:тип; имя_поля2:тип; end;);

· Файл (type имя=file of базовый тип);

· Ссылка.

С++:

Скалярные:

Указатели (Тип * имя);

Арифметические (основные):

Целые:

· Char;

· Int;

· Short;

· Long;

· Unsigned char;

· Unsigned int;

· Unsigned short;

· Unsigned long;

Плавающие:

· Float

· Double;

· Long double;

Составные:

Перечисление (enum имя_типа {список значений});

Массив (тип имя_переменной [кол-во]);

Структура (struct имя {список полей});

Смесь – это структура, у которой все поля имеют 0 смещение.

Определение типа:

1. внешний вид значения типа;

2. диапазон значений (+ константы);

3. операции над типом;

4. процедуры и функции можно применять к значениям;

5. особенности (допустимость) ввода-вывода;

6. представление значений в памяти ЭВМ;

Диаграмма Вирта

1. Терминальный символ – «круг»

2. Детерминальный символ – «квадрат»

3. Стрелки

Бэкус-Наур форма

1. Терминальный символ – a

2. Детерминальный символ - <a>

3. [a] – 0/1

4. {a} – 0/1/2/3…

5. a|b – a/b

6. конструкция – S::=L

Переопределение типа: typedef «старый тип» «новый тип»

Характеристика типа данных integer языка Pascal.

Целочисленный тип

Тип	Диапазон	Формат
Integer	-32768..32767	16 бит со знаком
Longint	-2147483648..2147483647	32 бита со знаком

Операции:

· Div, mod;

· Арифметические (+, -, *, /);

· Сравнения (<, >, <=, >=, <>, =);

Процедуры и функции:

· Математические (sqr(x), sqrt(x));

· Тригонометрич. (sin(x), cos(x)), x – угол в радианах;

· Прочие:

o pred(x) – пред. знач.;

o succ(x) – след. знач.;

o odd(x) – true, если нечетное;

o inc(x) – увеличение x на 1;

o dec(x) – уменьшение x на 1;