39. Определения теории графов. Задачи оптимизации на графах.

Графом G называют пару множеств (V,E) , где V={1,2,..,n} – множество пронумерованных вершин, т. е. V={V₁,V₂,…,V_n }, а E={e} – набор упорядоченных или неупорядоченных пар вершин e={v_i,v_j}. Неупорядоченная пара вершин, называется ребром, а упорядоченная - дугой .

Граф содержащий только рёбра(дуги), называется неориентированным (ори­ен­ти­ро­ванным). Граф, содержащий кратные ребра, называется мультиграфом.

Вершины V₁, V₂ называются смежными, ели они образуют ребро или дугу e={V₁,V₂}. Говорят, что V₁, V₂ инциденты ребру (дуге) e.

Каждому n-вершинному графу соответствует матрица смежности n x n C=||C_ij||, C_ij= количество ребер, соединяющих вершины i и j. (С_ii = 0; симметрична относительно диагонали; )

Граф G=(V,E) называется частью графа G=(V,E), если VV, EE.

Часть G графа G называется суграфом, если V= V, EE. G называется подграфом, если VV, а E’ содержит все ребра инцидентные v_i,v_jV.

|V|, |E| - величины показывающие количество вершин и ребер графа соответственно.

По количеству ребер можно выделить следующие виды:

1. E_n |V| = n, |E| = 0 – пустой граф (груда);

2. Противоположный Е_n , K_n полный граф (клика), у которого все вершины попарно смежны. Число ребер в n-мерной клике n(n-1)/2;

3. Имеющие вид многоугольников – циклы.

Связный граф не содержащий циклов называется деревом.

Остовным деревом графа называется связный суграф этого графа не содержащий циклов.

Задачи оптимизации на графах:

1. Задача о минимальном остовном дереве;

Дан n вершинный граф, каждому ребру которого ставится в соответствие c_ij. Множеством допустимых решений явл. Мн-во остовных деревьев данного графа. Необходимо найти такое ОД:

Алгоритм Краскала

Исходные данные: связный взвешенный граф с n>0 вершинами.

1. построить пустой граф с n вершинами;

2. k=0;

3. если k=n-1, то конец;

4. k=k+1;

5. найти k-ое по возрастанию весов ребро графа;

6. если добавление ребра в граф не приводит к появлению цикла, то добавить его;

7. перейти к шагу 3.

КОНЕЦ

2. Задача раскраски графа;

Постановка задачи: правильно раскрасить граф, т.е. такое приписывание вершинам графа номеров цветов, что любые две смежные вершины имеют разную окраску.

3. Задача о кратчайшем пути между парой вершин;

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

40. Основні команди користувача в операційній системі Windows. Консольний режим. Поняття про діалогові оболонки. Приклади.

1. Просмотр каталога - команда: dir

Формат: dir дисковод:\ имя каталога

Параметр \Р задаёт поэкранный режим вывода, \W выводит только информацию об именах файлов в каталоге.

Примеры:

dir - вывести оглавление текущего каталога;

dir*.exe - вывести сведения о всех файлах с расширением .exe из

текущего каталога;

dir a: - вывести оглавление корневого каталога диска а:

2. Изменение текущего каталога - команда: cd (Change Directory)

Формат: cd дисковод:\путь

Примеры:

cd games - переход в каталог GAMES текущего диска;

cd.. - переход в предыдущий каталог;

cd \ - переход в корневой каталог текущего диска

3. Создание каталога - команда md (Make Directory)

Формат: md дисковод:\путь

Примеры:

md games создание подкаталога GAMES в текущем каталоге;

md d:\games\doom2 - создание подкаталога DOOM2 в каталоге GAMES

диска D:

4. Уничтожение каталога - команда: rd (Remove Directory).

Формат: rd дисковод:\путь

Примеры: rd games удаление подкаталога GAMES в текущем каталоге; rd d:\games\doom2 - удаление подкаталога DOOM2 в каталоге GAMES диска D:

ВНИМАНИЕ! УДАЛИТЬ МОЖНО ТОЛЬКО ПУСТОЙ КАТАЛОГ!

5. Создание текстовых файлов - команда: copy con

Формат: copy con имя файла

После нажатия ENTER нужно ввести текст файла, затем последовательно нажать F6 ENTER

Пример:

Copy con games.txt - создание текстового файла Games.txt в текущем

каталоге.

6. Копирование файлов - Команда: copy

Формат: copy (имя копируемого файла) \(имя каталога, в который нужно поместить файл)

Пример:

Copy games.txt \games копировать файл games.txt в подкаталог GAMES

текущего диска.

7. Удаление файлов - Команда: del

Формат: del имя файла

Пример:

Del games.txt - удаление файла games.txt из текущего каталога.

8. Переименование файлов - Команда: ren (Rename)

Формат: ren (имя. файла) (новое имя. файла)

Пример: Ren games.txt games.doc - изменить имя файла games.txt

на games.doc в текущем каталоге".

9. Изменение вида приглашения DOS - Команда: prompt

Формат: prompt (текст)

В качестве текста можно использовать символы:

$p - текущий дисковод и каталог; $n - текущий дисковод; $d - текущая дата; $t - текущее ремя; $v - версия DOS; $_ - переход на новую строку; $s - пробел; $h - удаление редыдущего символа; $e - символ с кодом 27 (ESC); $g - символ > ; $b - символ | ; $$ - символ $;

10. Другие команды.

Date - вывод информации о дате с возможностью настройки.

Time - вывод информации о времени с возможностью настройки.

Verify on - включить режим проверки записи на диск.

Verify of - выключить режим проверки записи на диск.

Verify - вывести информацию о том, включен ли режим проверки записи

на диск.

Path - определяет порядок поиска наиболее часто запускаемых

программ.

Ver - показывает версию операционной системы.

Cls - производит очистку экрана.

Label - выводит информацию о метке диска с возможностью её

изменения.

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

Диалоговая оболочка – вид интерфейса при котором все необходимые свойства для выполнения команды указываются пользователем из набора, предоставленного ему в явном виде. Является интуитивно понятным и не требует от пользователя знания синтаксиса и всех свойств выполняемой команды (в отличии от командной строки MS-DOS).

Пример: С диалоговой оболочкой мы работаем при установке программного обеспечения.

41. Основні концепції об'єктно-орієнтованої методології програмування. Програмна модель об'єкту. Наведете приклад програмної моделі об'єкта в мові програмування C++.

Объе́ктно-ориенти́рованное программи́рование (ООП) — парадигма программирования, в которой основными концепциями являются понятия объектов и классов.

Класс — это тип, описывающий устройство объектов. Понятие «класс» подразумевает некоторое поведение и способ представления. Понятие «объект» подразумевает нечто, что обладает определённым поведением и способом представления. Говорят, что объект — это экземпляр класса. Класс можно сравнить с чертежом, согласно которому создаются объекты. Обычно классы разрабатывают таким образом, чтобы их объекты соответствовали объектам предметной области.

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

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

Концепции ООП (по Алану Кею):

• все является объектом;

• вычисления осуществляются путем взаимодействия (обмена данными) между объектами, при котором один объект требует, чтобы другой объект выполнил некоторое действие; объекты взаимодействуют, посылая и получая сообщения; сообщение -- это запрос на выполнение действия, дополненный набором аргументов, которые могут понадобиться при выполнении действия;

• каждый объект имеет независимую память, которая состоит из других объектов;

• каждый объект является представителем класса, который выражает общие свойства объектов данного типа;

• в классе задается функциональность (поведение объекта); тем самым все объекты, которые являются экземплярами одного класса, могут выполнять одни и те же действия;

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

Пример (Java, но выдавайте за С++)

// Создание экземпляра класса ArrayList с именем list

ArrayList list = new ArrayList();

// добавления экземпляра класса Integer в объект list

list.add(new Integer(1));

list.add(new Integer(2));

list.add(new Integer(3));

Подразумевается, что класс ArrayList уже описан в программном коде, и описание содержит определение для конструктора класса и метода add.