- •1. Структурная схема микропроцессора (на примере i8086). Назначение регистров.
- •3. Организация основной памяти.
- •3. Структура и характеристики оперативной памяти
- •4. Модель osi
- •5. Стек протоколов tcp/ip
- •6. Классификация компьютерных сетей
- •7. Данные и модели данных
- •8. Модель данных «сущность-связь»
- •Ограничения целостности
- •9. Реляционная модель данных
- •10. Основные направления исследования в области ии
- •11. Метод резолюции в лппп.
- •12. Продукционная модель
- •13. Основные парадигмы языков программирования.
- •14. Основные понятия ооп: инкапсуляция, наследование, полиморфизм
- •1. Инкапсуляция
- •2. Полиморфизм
- •3. Наследование
- •15. Понятие алгоритма.
- •16. Понятие о временной и емкостной сложности алгоритма
- •17. Машина Тьюринга: детерминированная и недетерминированная
- •18. Понятие формального языка и формальной грамматики
- •19. Основные понятия теории графов.
- •20. Понятие количества информации и энтропии. Теорема Шеннона.
- •21. Деревья в теории графов.
- •22. Модели линейного программирования (постановка задачи, математическая модель, решение графическим методом).
- •23. Двойственность в задачах линейного программирования.
- •25. Элементы теории игр.
- •2. Подпрограммы. Процедуры и функции
- •3. Массивы
- •4. Записи
- •5. Работа с Динамическими данными
- •6. Динамические структуры данных. Линейные списки.
- •7. Динамические структуры данных: двоичные деревья
- •8. Работа с файлами
- •9.Операции целочисленной арифметики
- •10. Системы счисления. Перевод чисел из одной системы счисления в другую
- •11. Язык sql. Назначение и основные команды.
- •Манипулирование данными
- •Простые запросы
- •12. Алгоритмы внутренней сортировки.
- •13. Алгоритмы внешней сортировки
- •14. Нахождение кратчайших путей в графе
- •15. Поиск в ширину
- •16. Поиск остова и минимального остова.
- •17. Линейная модель работы информационно-поисковой системы.
- •18. Хеширование
- •Основные достоинства в-дерева
- •20. Логические вопросно-ответные системы:выполнение запросов различных типов.
- •21. Поиск в семантической сети.
- •22. Принципы динамического программирования. Иллюстрация на примере.
- •23. Адресация в Интернете
- •Доменные имена
- •Общий вид формата url-адреса
- •Как работает dns-сервер
- •24. Основные сервисы в сети Интернет.
- •Word Wide Web (www) - "Всемирная паутина"
- •Поиск информации в сети
- •VoIp сервис
- •Мессенджеры
- •25. Использование html. Структура Web(html) страницы.
16. Понятие о временной и емкостной сложности алгоритма
Элементарным шагом алгоритма называется некоторое действие алгоритма, время выполнения которого не зависит от длины входа (входных данных).
Алгоритм – набор точных предписаний, однозначно задающих содержание и последовательность выполняемых операций для решения определенного класса задач.
Св-ва:
Дискретность – подразумевает, что алгоритм состоит из отдельных шагов.
Сходимость – алгоритм на корректных данных заканчивает работу.
Детерминированность – каждый шаг алгоритма, последовательность шагов однозначно определены.
Массовость – алгоритм пригоден для решения всех задач одного класса.
Вход – совокупность данных, содержащих условия необходимые для решения задач.
Выход алгоритма – совокупность данных, содержащих результат.
Временной сложностью или временной трудоемкостью алгоритма называется кол-во элементарных шагов, выполненных для данного входа.
Трудоемкость зависит от длины входа.
Если Т – трудоемкость, n – количественная характеристика входа (длина входа), то имеем T(n) – функция трудоемкости алгоритма.
Замечание: Время выполнения некоторого элементарного шага нефиксированно, то математический смысл имеет не сама ф-ция трудоемкости, а ее асимптотический порядок lim T(n) с точностью до const.
n→∞
Функции T1(n) и T2(n) называются функциями одного асимптотического порядка, выполняется следующее соотношение:
lim T1(n) T1(n)
n →∞ =lim = const T1(n)=0(T2(n)) T1(n)~T2(n)
n→∞ T2(n)
lim T2(n)
n→∞
Замечание: Трудоемкость зависит как от количественных характеристик (длины входа), так и от качественных характеристик.
T(n) – в наихудшем; Tср(n) – в среднем.
Трудоемкость в наихудшем – максимум трудоемкости при входе данной длины n.
Усредненная трудоемкость в среднем – среднее значение трудоемкости при входе длины n.
Пр.: вычисление объединения двух множеств. Сравнение алгоритма по временной сложности (т.е. как ведут себя асимптотические порядки)
ВХОД: А,В – упорядоченные по возрастанию |A|=n; |B|=m (| |- мощность).
ВЫХОД: надо получить C=AUB; AUB={x| xєA либо xєB}.
1 способ: Приписываем массив B в конец массива A=> отслеживаем одинаковые элементы: A={3,4,5,7} B={1,4,5,8,11}=> C={3,4,5,7,1,4,5,8,11}(удаление дубликатов) => C={3,4,5,7,1,8,11}
T~n+m+(n+m)2~(n+m)2 шагов.
В Паскале 1 способ:
For i:=n+1 to n+m do A[i]=B[i-n] // приписываем В в конец А.
L:=n+m // удаление дубликатов
For i:=1 to l do begin
For j:=i+1 to l do
If A[i]=A[j] then begin
For j1:=j+1 to l do A[j1-1]:=A[j1];
Dec (l); break; end; end.
2 способ: Переписываем элементы из А и В по возрастанию; если какой-то элемент уже попал в С, то отбрасываем =>T~(n+m)=> этот алгоритм эффективнее на порядок => по временной сложности (трудоемкости) второй алгоритм удачнее.
В Паскале 2 способ:
A[n+1]:= ∞ B[m+1]:= - ∞; i:=1; j:=1; l:=0; l – кол-во элементов в массиве С
While (i<=n) or (j<=m) do begin
While (A[i]<=B[j]) and (i<=n) do begin
If A[i]<>C[l] then begin inc(l);
C[l]:=A[i] end;
Inc(i) end;
While (A[i]>B[j]) and (j<=m) do begin
If B[j]<> C[l] then begin inc(l);
C[l]:=B[j] end;
Inc(j) end; end.
Емкостной трудоемкостью алгоритма называется объем памяти, требуемый для работы алгоритма.
Сложность задачи как временная, так и емкостная определяется как соответствующая трудоемкость самого эффективного алгоритма решения данной задачи.
Трудоемкостью задачи называется трудоемкость самого эффективного алгоритма решения данной задачи. T~n log n.
Сущ-ет лемма: T(n) ~f(n)=> cущ. C, по для каждых n>n0, т.ч. T(n)≤c*f(n).
Оценка трудоемкости: Чем > длина входов, тем выше разность между эффективными и неэффективными алгоритмами. Кроме тех случаев, когда трудоемкость оценивается тривиально, этот процесс может вызвать затруднения, например, в случае анализа рекуррентных конструкций.
Теорема 1: Пусть T(n)={b, n=1
A*T(n-1) +bnp, n>p, тогда a=1, T(n) ~np+1 k=const
a>1, T(n) ~2kn
Док-во:
aT(n-1)+bnp=a(aT(n-2)+b(n-1)p)+bnp=
n=n-1 шаг
=a(a(aT(n-3)+b(n-2)p)+b(n-2)p+b(n-1)p)+bnp=… =>
n=n-2 шаг
=>aT(n-1)+bnp=a2T(n-2)+ab(n-1)p+bnp=a3T(n-3)+a2b(n-2)p+ab(n-1)p+bnp= … =(n=2)=
=an-1T(n-n+1)+an-2b(2)p+ … + ab(n-1)p+a0bnp => (n-1) шаг an-1 T(1) + an-2b(2)p + … +
=b
+a1b(n-1)p+a0bnp=b(an-11p+an-22p+an-33p + …+ a1(n-1)p)+a0np.
Если a=1 => T(n)=b(1p+2p+ … +np) ~ 1p+ … +np~ np+1;
Если a>1 => T(n)=an-1= an/a=an=(2log2 a)n
Если K=log2a => T(n) ~2kn
Т.о. при a=1, когда T(n) ~ np+1 алгоритм имеет полиномиальную трудоемкость. При a>1, когда T(n) ~ 2kn~lk1n – экспоненциальную трудоемкость. Все алгоритмы делятся на экспонециал. (нереально выполнимые) и полиномиал. (реально выполнимые).
Теорема 2: T(n)={b, n=1
aT(n/c)+bnp, n>1, тогда 1. a<cp => T(n) ~ np
2. a=cp => T(n) ~ nplog n
3. a>cp => T(n) ~ n logca (полиномиал.)
Понятие временной и емкостной сложности задач по Тьюрингу.
Временой трудоёмкостью по Тьюрингу наз. кол-во переходов, выполняемых МТ, соответствующих данному алгоритму.
Под алгоритмом здесь понимается любая последовательность действий для МТ.
В связи с этим основные свойства алгоритма:
дискретность( выполняется автоматически)
детерминированость (выполняется автом. Только для ДМТ)
массовость (в общем случае не выпол.)
сходимость (выпол. В случае если МТ останавливается на коректных вход. даных)
для выполнения св-ва массовости необходимо, чтобы в момент останова на ленте гарантировалось наличие выходных данных. Формально, алгоритм обладающий этим свойством наз. корректным. Если же алгоритм гарантирует остановку МТ и на корректных данных, то он наз. хорошим.
Фун-ия трудоемкости Т(п) п-длина выхода
Длиной выхода яв-ся объем выходных данных, т.е. кол-во символов на ленте перед началом работы МТ.
Различают точную и фактическую длину входа.
Точной длиной входа н-ется кол-во символов на ленте МТ перед началом ее работы T(n) и Tср(n). Под последней понимается кол-во некоторых блоков данных.
Пр. сортировка: 7 13 14 5 1 п(фактическ.)=5 п(точн.)=40 пт=к*пф
Вместо Т(п) используем ассимптотический порядок п Т(пт)=Т(пф)
S(п) емкостная трудоемкость и определяется как макс. количество занятых ячеек на ленте МТ. К сожалению, по ряду причин, нет линейной связи между трудоемкостью в классическом смысле и трудоемкостью по Тьюрингу, но есть связь полиномиальная, т.е. Ткл.(п)~пр1< = >Тмт(п)~пр2
Временной сложностью задачи по Тьюрингу называется число переходов, выполняемых машиной Тьюринга (МТ) для данного входа.
Емкостная сложность по Тьюрингу – максимальная длина рабочей части ленты МТ во время выполнения программы (алгоритма).
Замечание: Ассимптонический порядок трудоемкости в классическом смысле и трудоемкости по Тьюрингу не всегда совпадают. Но в тоже время доказано, что эти трудоемкости связаны полиномиально:
TMT(n)=np1 => Tkn(n) ~np2 , p1,p2 – const
Tkn(n) ~np1 => TMT(n) ~ np2
T~2kn – экспоненциальная трудоемкость
T~np – полиномиальная трудоемкость
T~n – линейная трудоемкость