» » » Объектно-ориентированное программирование

Презентация на тему Объектно-ориентированное программирование

tapinapura

Презентацию на тему Объектно-ориентированное программирование можно скачать абсолютно бесплатно на нашем сайте. Предмет презентации : Информатика. Красочные слайды и илюстрации помогут вам заинтересовать своих одноклассников или аудиторию. Для просмотра содержимого презентации воспользуйтесь плеером, или если вы хотите скачать презентацию - нажмите на соответствующий текст под плеером. Презентация содержит 36 слайдов.

скачать презентацию

Слайды презентации

Слайд 1: Презентация Объектно-ориентированное программирование
Слайд 1

Олимпиадная работа по ИКТ: “Нахождение кратчайшего пути с использованием графов и алгоритма Дейкстры” Ученика 10 “В” класса гимназии г. Обнинска Кашкарова Михаила (Объектно-ориентированное программирование - Delphi)

Слайд 2: Презентация Объектно-ориентированное программирование
Слайд 2

Содержание:

Графы: определения и примеры Ориентированные графы Путь в орграфе Матрица смежности Иерархический список Алгоритм Дейкстры Программа “ProGraph” Описание работы программы Достоинства программы Список литературы

Слайд 3: Презентация Объектно-ориентированное программирование
Слайд 3

Графы: определения и примеры

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

Слайд 4: Презентация Объектно-ориентированное программирование
Слайд 4

Рис. 1. Три способа изображения одного графа

Например, три графа на рис. 1 совпадают

Слайд 5: Презентация Объектно-ориентированное программирование
Слайд 5

А два графа на рис. 2 - различны

Рис. 2. Пример двух разных графов

Слайд 6: Презентация Объектно-ориентированное программирование
Слайд 6

Степень вершины

Любому ребру соответствует ровно две вершины, а вот вершине может соответствовать произвольное количество ребер, это количество и определяет степень вершины. Изолированная вершина вообще не имеет ребер (ее степень равна 0).

Слайд 7: Презентация Объектно-ориентированное программирование
Слайд 7

Смежные вершины и рёбра

Две вершины называются смежными, если они являются разными концами одного ребра. Два ребра называются смежными, если они выходят из одной вершины.

Слайд 8: Презентация Объектно-ориентированное программирование
Слайд 8

Путь в графе

Путь в графе - это последовательность вершин (без повторений), в которой любые две соседние вершины смежны. Например, в изображенном графе, есть два различных пути из вершины a в вершину с: adbc и abc.

Слайд 9: Презентация Объектно-ориентированное программирование
Слайд 9

Достижимость

Вершина v достижима из вершины u, если существует путь, начинающийся в u и заканчивающийся в v. Граф называется связным, если все его вершины взаимно достижимы.

Слайд 10: Презентация Объектно-ориентированное программирование
Слайд 10

Длина пути

Длина пути - количество ребер, из которых этот путь состоит. Например, длина уже упомянутых путей adbc и abc - 3 и 2 соответственно. Расстояние между между вершинами u и v - это длина кратчайшего пути от u до v. Из этого определения видно, что расстояние между вершинами a и c в графе на рис. равно 2. Цикл - это замкнутый путь. Все вершины в цикле, кроме первой и последней, должны быть различны. Например, циклом является путь abda в графе на рис.

Слайд 11: Презентация Объектно-ориентированное программирование
Слайд 11

Примеры неориентированных графов

Слайд 12: Презентация Объектно-ориентированное программирование
Слайд 12

Ориентированные графы

Орграф - это граф, все ребра которого имеют направление. Такие направленные ребра называются дугами. На рисунках дуги изображаются стрелочками ( рис.3)

Рис. 3. Орграф

Слайд 13: Презентация Объектно-ориентированное программирование
Слайд 13

Смешанный граф

В отличие от ребер, дуги соединяют две неравноправные вершины: одна из них называется началом дуги (дуга из нее исходит), вторая - концом дуги (дуга в нее входит). Можно сказать, что любое ребро - это пара дуг, направленных навстречу друг другу. Если в графе присутствуют и ребра, и дуги, то его называют смешанным

Слайд 14: Презентация Объектно-ориентированное программирование
Слайд 14

Путь в орграфе

Путь в орграфе - это последовательность вершин (без повторений), в которой любые две соседние вершины смежны, причем каждая вершина является одновременно концом одной дуги и началом следующей дуги. Например, в орграфе на рис. 3 нет пути, ведущего из вершины 2 в вершину 5. "Двигаться" по орграфу можно только в направлениях, заданных стрелками.

Слайд 15: Презентация Объектно-ориентированное программирование
Слайд 15

Примеры ориентированных графов

Слайд 16: Презентация Объектно-ориентированное программирование
Слайд 16

Взвешенные графы

Взвешенный (другое название: размеченный) граф (или орграф) - это граф (орграф), некоторым элементам которого (вершинам, ребрам или дугам) сопоставлены числа. Наиболее часто встречаются графы с помеченными ребрами. Числа-пометки носят различные названия: вес, длина, стоимость.

Рис. 4 Взвешенный граф

Слайд 17: Презентация Объектно-ориентированное программирование
Слайд 17

Длина пути во взвешенном графе

Длина пути во взвешенном (связном) графе - это сумма длин (весов) тех ребер, из которых состоит путь. Расстояние между вершинами - это, как и прежде, длина кратчайшего пути. Например, расстояние от вершины a до вершины d во взвешенном графе, изображенном на рис. 4, равно 6.

Слайд 18: Презентация Объектно-ориентированное программирование
Слайд 18

Примеры взвешенных графов

Слайд 19: Презентация Объектно-ориентированное программирование
Слайд 19

Способы представления графов

Существует довольно большое число разнообразных способов представления графов. Однако мы изложим здесь только самые полезные с точки зрения программирования.

Слайд 20: Презентация Объектно-ориентированное программирование
Слайд 20

Матрица смежности

Матрица смежности Sm - это квадратная матрица размером N x N (N - количество вершин в графе), заполненная по следующему правилу: Если в графе имеется ребро e, соединяющее вершины u и v, то Sm[u,v] = Ves(e), в противном случае Sm[u,v] = “-”.

Слайд 21: Презентация Объектно-ориентированное программирование
Слайд 21

Пример матрицы смежности

Слайд 22: Презентация Объектно-ориентированное программирование
Слайд 22

Преимущества матрицы смежности

Удобство матрицы смежности состоит в наглядности и прозрачности алгоритмов, основанных на ее использовании. А неудобство - в несколько завышенном требовании к памяти: если граф далек от полного, то в массиве, хранящем матрицу смежности, оказывается много "пустых мест" (нулей). Кроме того, для "общения" с пользователем этот способ представления графов не слишком удобен: его лучше применять только для внутреннего представления данных.

Слайд 23: Презентация Объектно-ориентированное программирование
Слайд 23

Иерархический список

В одном линейном списке содержатся номера "начальных вершин", а в остальных - номера смежных вершин или указатели на эти вершины. В качестве примера приведем иерархический список, задающий орграф, изображенный на рис.3

Слайд 24: Презентация Объектно-ориентированное программирование
Слайд 24

Пример иерархического списка

Рис. 5 Пример иерархического списка

Рис. 3 Орграф

Слайд 25: Презентация Объектно-ориентированное программирование
Слайд 25

Преимущества иерархического списка

Вершина = запись Номер: Число; Имя: Строка; След Вершина: указатель на Вершина; Список Дуг: Дуга; end; Дуга = запись Стоимость: Число; Конец Дуги: Вершина; След Дуга: Дуга; end; Очевидное преимущество такого способа представления графов заключается в экономичном использовании памяти. И даже небольшая избыточность данных, к которой приходится прибегать в случае неориентированного графа, задавая каждое ребро как две дуги, искупается гибкостью всей структуры, что особенно удобно при необходимости частых перестроений в процессе работы программы.

Слайд 26: Презентация Объектно-ориентированное программирование
Слайд 26

Программа “ProGraph”

Программа “ProGraph” была специально созданна для создания графов в графической оболочке. Поддерживает возможность добавления алгоритмов на графах.

Слайд 27: Презентация Объектно-ориентированное программирование
Слайд 27

Алгоритм Дейкстры

Мы рассмотрим один из основных алгоритмов поиска кратчайших путей в графе – алгоритм Дейкстры, применимый для графов с неотрицательными весами.

Слайд 28: Презентация Объектно-ориентированное программирование
Слайд 28

Описание алгоритма

Основная идея основана на простой формуле: (Dist(x) – расстояние до вершины x из исходной) Dist(Xi) = Минимум(Dist(Xi), Dist(p) +Matr(p,i))

Слайд 29: Презентация Объектно-ориентированное программирование
Слайд 29

Допустим, нам надо найти кратчайший путь из вершины A в вершину D. Перебираем все возможные расстояния до вершин, находим из них минимальное и выводим кратчайший путь.

Слайд 30: Презентация Объектно-ориентированное программирование
Слайд 30

Описание работы программы

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

Слайд 31: Презентация Объектно-ориентированное программирование
Слайд 31

Создание графа в Редакторе

Запустите программу “ProGraph.exe”

Вы увидите это окно.

В данном окне вы должны ввести параметры: Количество вершин графа (‘AddNode’) Ребра и их вес (‘AddNode’, ‘Matrix’ – веса ребер) Имена вершин (ПКМ на вершине, поле ‘NodeName’) Здесь вы можете дополнительно выбрать графическое изображение вершин.

Слайд 32: Презентация Объектно-ориентированное программирование
Слайд 32

У вас должно получиться примерно так:

Мы видим пример сети, оформленной в виде графа. Расстояние между вершинами показаны на линиях. В оформлении вершин используется пиктограмма компьютера.

Для сохранения полученного графа выбираем из меню File -> Save as и сохраняем под любым именем. Полученную заготовку будем использовать для второй части.

Слайд 33: Презентация Объектно-ориентированное программирование
Слайд 33

Применение алгоритма Дейкстры

Для вызова программы загружаем (File -> Load) ранее сохранённый файл. Открываем из главного меню ‘ALGOR -> algor_Dijkst’. Появится новое окно, в котором необходимо задать начальный и конечный номер вершины.

(Чтобы переключить показ ‘Имена вершин/Индексы’ необходимо поставить флажок в поле ‘ShowNodInd’)

Заполнить поля ‘From’ и ‘To’ и запустить алгоритм на выполнение (‘OK’)

Слайд 34: Презентация Объектно-ориентированное программирование
Слайд 34

Просмотр результата

Вы увидите результат работы: В окне задания параметров появится строка с длиной кратчайшего пути и сам путь.

В окне редактора отобразится пройденный путь и вершины окрасятся в следующие цвета: Красный – начальная вершина. Синий – конечная вершина. Желтый – вершины искомого пути. Серый – вершины, посещенные при работе алгоритма, но не включённые в конечный путь.

Слайд 35: Презентация Объектно-ориентированное программирование
Слайд 35

Достоинства программы

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

Программа была создана на языке “Delphi” с использованием объектно-ориентированного программирования.

Данная программа может быть использована для подготовки к ЕГЭ по информатике.

Слайд 36: Презентация Объектно-ориентированное программирование
Слайд 36

Кирюхин В.М., Лапунов А.В., Окулов С.М. Задачи по информатике: Международные олимпиады 1989 – 1996: Для факультативов по информатике в старших классах. – М.: ABF, 1996 Боглаев Ю.П. Вычислительная математика и программирование. – М.: Высшая школа, 1990 Кушниренко А.Г., Лебедев Г.В. Программирование для математиков. – М.: Наука, 1988. Майерс Г. Искусство тестирования программ. – М.: Финансы и статистика, 1982. Никольская И.Л. Математическая логика. – M.: Высшая школа, 1981.

Список использованной литературы

Список похожих презентаций

  • Яндекс.Метрика
  • Рейтинг@Mail.ru