- •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. Поиск остова и минимального остова.
Опред. Маршрутом (путем) в графе G между вершинами x и y называется упорядоченное множество ребер следующего вида:M={ ei | v1,..,vn V [P(x,e1,v1)/\P(v1,e2,v2)/\.../\P(vn-1,en,vn)/\P(vn+1,e,y)]}.
Пример.
Опред. Вершины x и y называются взаимнодостижимыми, если существует маршрут из х в у и из у в х.
Опред. Остовом или каркасом неориентированного графа G называется суграф G’={V’, E’, P’}, построенный следующим образом.
A) Сначала V’:=V, E’:=0;
B) Перебираем ребра ei из E и включаем их в E’ в том случае, если на данный момент вершины - x,y, где P(x,ei,y) (т.е. вершины, которые соединяет данное ребро)- взаимно недостижимые.
Это определение фактически дает алгоритм построения остова.
Пример
2 4
1
3 5 6
Теорема. Количество элементов в остове <=n-1.
Док-во опускается.
Запишем алгоритм в формальном виде:
ВХОД - граф, заданный масcивом ребер G[i,1] и G[i,2] соответственно вершины, инцидентные i-му ребру. Считаем, что граф неориинтированный, и поэтому если в массиве есть запись (x,y) считаем, что нет записи (y,x); m- число ребер в G, n - число вершин в G.
ВЫХОД - остов G’, заданный массивом ребер G1. число ребер в остове - i1
Главная проблема при построении алгоритма - определение факта взаимодостижимости вершин. Эта проблема решена путем введения вcпомогательного массива A[1..n], который поддерживается таким образом, что все взаимно-достижимые на данный момент вершины имеют одинаковое значение.
Алгоритм выглядит так:
procedure ostov;
for i:=1 to n do A[i]:=i; //обозн., что любая вершина достижима сама с собой.
i1:=0; // i1 - число ребер в остове
for i:=1 to m do if A[G[i,1]]<>A[G[i,2]] then begin //если G[i,1] и G[i,2] - недостижимые - включаем i-е ребро в остов.
inc(i1); //включаем ребро
G1[i1,1]:=G[i,1]; G1[i1,2]:=G[i,2]; // в остов
//перестроение массива A.
if A[G[i,1]]<>G[i,1] then begin
A[G[i,2]]:=A[G[i,1]];
for j:=1 to n do if A[j]=G[i,2] then A[j]:=A[G[i,1]]
end else if A[G[i,2]]<>G[i,2] then begin
A[G[i,1]]:=A[G[i,2]];
for j:=1 to n do if A[j]=G[i,1] then A[j]:=A[G[i,2]]
end else A[G[i,2]]:=A[G[i,1]];
if i1=n -1 then break;
end;
end;
Оценим трудоемкость T(n)~m+(n-1)n~m+n2. первое слагаемое - мах придется просмотреть все m ребер, 2-е - max n-1 включений ребер в остов, каждое приводящее мах к n шагов по перестройке массива A.
Поиск минимального остова графа.
Пусть дан взвешенный граф G. Его остов, который имеет минимальную сумму весов ребер среди всех остовов графа G называется минимальным остовом графа G.
Алгоритм решения задачи тривиален:
ВХОД - граф G, заданный расширенным списком ребер G
ВЫХОД - минимальный остов, заданный расширенным списком ребер G1.
sort(E); //сортируем множество ребер по возрастанию весов.
ostov; .//вызов процедуры поиска остова (см. 2.4.)
Этот алгоритм впервые предложен был Краскалом, он же доказал его корректноcть.
Заметим, что для алгоритма Краскала. T~mlog m+n2. С учетом того, что для простых графов m<=n2 имеем, что T~o(n2logn), т.е. даже наихудшие характеристики незначительно хуже. чем у алгоритма поиска простого остова. Кроме того, следует учитывать, что в реальных задачах часто m<<n2.