19. Представление графа списком списков, алгоритм обхода графа в ширину.

Список списков снимает ограничение на множество вершин в графе

Обход в ширину (3амена стека на очередь)

При поиске в глубину , чем по3днее будет просмотрена вершина, тем раньше она исполь3уется ,- принцип стека.

При обходе в ширину, чем раньше просматривается , добавляется в очередь, тем раньше исполь3уется - удалится, т.е просматриваются все смежные с ней вершины сра3у.

Алгоритм :

function BFS (v)

begin Queue=0; v-> Queue;

Nov[v] = false;

while(queue <>0) do begin

Queue -> p; просмотреть p;

for ( u э spisok[p]) do

if ( Nov[u]) then begin;

Nov[u] = false ; u-> queue ; end;end;end;

Оба алгоритма можно исполь3овать для нахождения пути между вершинами u и v.

20. Технологии программирования, концепции, заложенные в ооп.

ООП - один и3 подходов к ра3работке программ. Исторически первый и3 реали3уемых подход - процедурное программирование, при котором со3давались библиотеки стандартных программ, они исполь3овались в ра3личных областях применения ЭВМ-программирование "сни3у-вверх", основано на со3дании модулей.-одно и3 основных требований к машинноне3ависимым я3ыкам.

Структурное программирование - структурирование наборов действий,а ООП - структурирование наборами объектов => ООП - ре3ультат 30 летнего опыта программистов : Simula67 -> Smalltalk -> Lisp-Clu-Actor -> Eiffel -> Objective C -> Objective Pascal , Java, C++, C#

Концепции 3аложеные в ООП:

-моделирование объектов и действий реального мира

-наличие типов данных , определённых поль3ователем

-сокрытие деталей ркали3ации

-во3можность многократного исполь3ования программного кода

-интерпретация вы3овов функций на этапе выполнения программы

Универсальные среды ра3работки Windows - приложений объединяют:

1) программирование по событиям - пр-ие ответных действий на реально во3никшие события во время сеанса работы.

2) ви3уальное программирование даёт во3можность и3ображать объекты на экране до выполнения самой программы. т.е программист видит, как будет выглядеть готовая программа => события управляют работой программы.

Реакция на событие - выполнение некоторой программы - метода объекта- обработчик события.

21. Основные понятия ооп: абстракция, инкапсуляция, полиморфизм.

Основная идея ООП- объединение(инкапсуляция) данных и методов их обработки в единое целое – объект, который может использоваться как самостоятельная программная единица, или как часть другого объекта, или является базой для создания новых объектов.

Абстрагирование (abstraction) - метод решения задачи, при котором объекты разного рода объединяются общим понятием (концепцией), а затем сгруппированные сущности рассматриваются как элементы единой категории.

Инкапсуляция (encapsulation) - объединение данных с функциями, предназначенными для манипулирования этими данными (т.е. поведением) в новом типе - КЛАССЕ . Пример. Представьте, что Вам надо написать программу, которая выполняла бы дует духового и струнного инструментов. Для этого определите классы Духовой инструмент и Струнный инструмент. Для класса Духовой инструмент определите, что имеется мундштук и что в него надо дуть, чтоб получить звук. Для класса Струнный инструмент определите, что по струнам надо ударять, чтоб получить звук. Оба класса уже способны "играть музыку", и что это свойство было унаследовано от предка. Они унаследовали метод PlayMusic, который был объявлен и реализован как метод класса Музыкальный инструмент. Таким образом, этот метод уже не нужно создавать, и Вам не надо знать код реализации метода, чтобы использовать его в двух новых классах. Способ, которым реализована возможность играть музыку, не важен. Этот принцип сокрытия информации (information hiding) характерен для инкапсуляции и существенно облегчает написание больших и стабильно работающих приложений. Если класс был грамотно сконструирован и тщательно проверен, он может многократно использоваться в различных приложениях. В примере с музыкальными инструментами это означает, что каждый класс обладает свойствами класса Музыкальный инструмент, а способы создания звука заключены внутри него. Эти способы невидимы и недоступны за пределами класса. Также подразумевается, что классы ничего не знают друг о друге. Они полностью разделены, и им не известны спецификации и свойства друг друга. Духовой инструмент закрыт для любых попыток других классов использовать его мундштук. Также и струны Струнного инструмента, и способ их использования заключены внутри него самого. Объект закрыт, т.е. окружение не может случайно изменить это объект. Смысл этой закрытости в том, что Вы не обязательно должны знать, как, например, Труба издает звук.

Полиморфизм - многоформенность в Си++; механизм, позволяющий использовать одинаковые имена для сходных по смыслу действий и методов, относящихся к различным объектам (типам и классам). Это означает, что один и то же метод выполняется по разному для различных объектов. Например, метод класса Музыкальных инструментов - PlayMusicForAnOrchestra - может быть определен как общим метод, который может использоваться с любой категорией инструментов. Этот метод написан таким образом, что не важно, какой именно инструмент получает задание играть, однако для классов, описывающих конкретные инструменты, данный метод должен быть переопределен (override), что даст возможность определить конкретные действия, учитывая особенности конкретного инструмента.