Верхние и нижние оценки сложности алгоритмов. разрешимые и неразрешимые задачи.
с целью анализа программы удобно представлять управляющий граф.
Верхняя оценка (худший случай)
нижняя оценка (лучший случай)
средняя оценка (что "усреднённое", комбинаторные методы или методы теорий вероятностей).
задача может быть решена, если построен алгоритм, приводящий к рез-ту-решению задачи.
неразрешимые задачи:
1) проблема остановки (на несколоьких исходных данных машина тьюринга может не останавливаться, не давать рез-та).эта проблема состоит в построении маш.Тьюринга, которая, получая на входе код произв. маш.Тьюринга и входные данные этой маш. Тьюринга, определяет, останавливается ли машина. Доказано, что ткую машину построить нельзя.
2) проблема эквивалентности. (для любых исходных данных две машины Тьюринга будут вычислять одинаковый рез-т одной и той же ф-ии). проблема состоит в построении такой маш.Тьюригна, получающей на входе описания (коды) двух машин Тьюринга и орпеделяющий эквивалентны ли эти маш.Тьюринга. Но не существует общего метода.
29. Классы сложности алгоритмов P, EXP, NP
30. Концепция типа данных.
1. Любая переменная, константа, выражение или функция относятся к некоторому типу;
2.Тип данных определяет множество значений, к которым отностится константа и которые могут принимать переменные, выражение и ли функция;
3.Каждая операция м функция требует для своего выполнения аргументов строго определенного типа и вырабатывает результат так же строго определенного типа.
Следствия:
1 Все новые типы данных определяются только на основе уже существующих;
2 Значения новых типов данных всегда состоят из комбинации значений предыдущих типов данных, поэтому значения новых типов называются составными.
3 Если при постороении нового типа данных используется только один состовляющий тип, то он называется базовым
4 Число различных значений входящих в тип данных называется мощностью типа.
5 Каждый язык высокого уровня дает свои изобразительные средства для указания принадлежности какой-либо переменнойк определенному типу
6 Любой язык для любого типа данных вводит всегда 2 операции, это присваивание и сравнение на равенство.
7 Если для значения какого-либо типа данных определяется операция отношения, то такой тип данных называется скалярным.
31. Понятие типа данных. Классификации типов данных в языках 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 базовый тип)
- Ссылка
C++
1. Скалярные
1.1. Указатели
1.1.1. Тип * имя;
1.2. Арифметические (основные)
1.2.1. Целые
1.2.1.1. Char
1.2.1.2. Int
1.2.1.3. Short
1.2.1.4. Long
1.2.1.5. Unsigned char
1.2.1.6. Unsigned int
1.2.1.7. Unsigned short
1.2.1.8. Unsigned long
1.2.2. Плавающие
1.2.2.1. Float (вещественный тип 4 байта)
1.2.2.2. Double (2-ая точность 8 байт)
1.2.2.3. Long double
2. Составные
2.1. Перечисление (enum имя_типа {список значений})
2.2. Массив (тип имя_переменной [кол-во])
2.3. Структура (struct имя {список полей})
2.4. Смесь – это структура у которой все поля имеют 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 «старый тип» «новый тип»
32. Integer
Целочисленные типы
---------------------------------------------------------------
Предопределенные целочисленные типы Таблица 4.1
---------------------T--------------------T---------------------
¦ Тип ¦ Диапазон ¦ Формат ¦
+--------------------+--------------------+---------------------+
¦ целое ¦ -32768 .. 32767 ¦ 16 бит со знаком ¦
¦ (Integer) ¦ ¦ ¦
+--------------------+--------------------+---------------------+
¦ длинное целое ¦ -2147483648 .. ¦ 32 бита со знаком ¦
¦ (Longint) ¦ ..2147483647 ¦ ¦
L--------------------+--------------------+----------------------
_____ _____
--->¦знак ¦--->¦число¦--->
¦_________¦ ¦_________¦
Операции:
· DIV, MOD
· Арифметич. (+,-,*,/)
· Сравнения (<,>,=,>=,<=,<>)
Процедуры и функции:
· математические (sqr, sqrt)
· тригонометрич. (sin, cos)
· прочие (
o pred – пред знач.
o succ – след.знач
o odd – true if nech
o inc - ++
o dec - --
33. Real
Вещественные типы
-----------------------------------------------------------------
Диапазон представления
и десятичные цифры для вещественных типов Таблица 4.2
------------------------T---------------------------T-----------
¦ Тип ¦ Диапазон ¦ Цифры ¦
+-----------------------+---------------------------+-----------+
¦ вещественное ¦2.9x10^-39 .. 1.7x10^38 ¦от 11 до 12¦
¦ (Real) ¦ ¦ ¦
L-----------------------+---------------------------+------------
[±]Z.[C]
±mE±p
Вещ.число _____ _________ ________ _____ _________
--------->¦знак ¦--->¦цел.часть¦-->.-->¦др.часть¦--->E-->¦знак ¦-->¦цел.часть¦--->
¦_________¦ ¦________________¦¦__________________________¦
Операции:
· Сравнения (<,>,=,>=,<=,<>)
· Арифметические(+,-,*,/)
Процедуры и функции:
· Все математич.
· Все тригонометрич.
· Прочие()
o Trunc – отсек. Др.часть
o Round – округл.до ближ.целого
34. Char Boolean
Логический тип
-----------------------------------------------------------------
True, False
Операции:
· логические (or, and, not)
· Сравнения (<,>,=,>=,<=,<>)
Процедуры и функции:
- False < True
- Ord(False) = 0
- Ord(True) = 1
- Succ(False) = True
- Pred(True) = False
Символьный тип (char)
-----------------------------------------------------------------
Кодировка: расположение символов по кодам их представляемых.
Условия:
· Кажд. Символ имеет свой числовой эквивалент
· Коды символов, изображ.арабские цифры идут строго последовательно, и упорядочены по возрастанию
· Любая кодировка должна содерж.символ пробела
ACSII – 256 символов
Операции:
· Сравнения (<,>,=,>=,<=,<>)
Процедуры и функции:
· Ord(A)=152
· Chr(152)=A
35. Перечисление, отрезок, множество
Отрезки типа
-----------------------------------------------------------------
ЗАПРЕЩЕНО! Использовать для Real
Type имя = min..max
pul=10..50;
color=red..black;
type matrix = array[1..m,1..n] of real;
Перечислимые типы
-----------------------------------------------------------------
имя знач.1
имя знач.2
Type имя = . . . . .
имя знач.N-1
имя знач.N
var x:имя;
Операции:
· Сравнения (<,>,=,>=,<=,<>)
Процедуры и функции:
· Pred
· Succ
· Ord
I/O – НЕТ!
Множественные типы
-----------------------------------------------------------------
Type имя = set of базовый тип
M1 = set of color;
Var x:M1;
Присваивания: x:=[red,black,green]
x:=[white]
x:=[]
Операции:
· Сложение
· Умножение
· Вычитание
· In
Проц. и Функц.: НЕТ!
I/O: НЕТ!
36. Массив Запись
Типы массив
-----------------------------------------------------------------
Type имя = array [T1] of T2
T1 – тип индекса (кроме вещ.)
T2 – тип элементов (кроме file)