Информатика 23-24г Объекты и классы. Свойства и методы объектов.

 

Объекты и классы. Свойства и методы объектов.

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

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

Свойства — это простые переменные, которые описывают состояние объекта. Например, ширина, высота, цвет и т.п. – это свойства объекта.

Методы – это процедуры и функции, определяющие то, что объект умеет делать (вычислять). Например, объект может иметь процедуру для вывода какого-то текста на экран. Эта процедура и есть метод объекта.

События – это процедуры и функции, которые вызываются при наступлении определенного события. Например, если изменилось какое-то свойство объекта, может быть сгенерировано соответствующее событие и вызвана процедура для обработки реакции на это событие.

Указанное объединение в едином объекте свойств, методов и событий называется инкапсуляцией.

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

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

Пример: рассмотрим объект – «кнопка». Такой объект должен обладать следующим минимальным набором:

Свойства:

1.      Левая позиция (Х).

2.      Верхняя позиция (Y).

3.      Ширина.

4.      Высота.

5.      Заголовок.

Методы:

1.      Создать кнопку.

2.      Уничтожить кнопку.

3.      Нарисовать кнопку.

События:

1.     Кнопка нажата.

2.      Заголовок кнопки изменен.

Объект работает как единое целое свойств, методов и событий. Например, вы изменили заголовок кнопки. Объект генерирует событие «Заголовок кнопки изменен». По этому событию вызывается метод «Нарисовать кнопку». Этот метод рисует кнопку в позиции, указанной в свойствах объекта и выводит на кнопке текст, указанный в свойстве «Заголовок».

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

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

Наследование — это такое отношение между объектами, когда один объект повторяет структуру и поведение другого.

С точки зрения программирования наследование — это свойство объектов, посредством которого экземпляры класса получают доступ к данным и методам классов-родителей без их повторного определения. Наследование позволяет различным типам данных совместно использовать один и тот же код, приводя к уменьшению его размера и повышению функциональности.

Принцип наследования действует в жизни повсеместно и повседневно. Млекопитающие и птицы наследуют признаки живых организмов, в отличие от растений, орел и воробей наследуют общее свойство птиц — умение летать. С другой стороны, львы, тигры, леопарды наследуют «структуру» и поведение, характерное для представителей отряда кошачьих и т.д.

Типы верхних уровней ОО-иерархии, как правило, не имеют конкретных экземпляров объектов. Не существует, например, конкретного живого организма (объекта), который бы сам по себе назывался «Млекопитающее» или «Птица». Такие типы называются абстрактными. Конкретные экземпляры объектов имеют, как правило, типы самых нижних уровней ОО-иерархий: «крокодил Гена» — конкретный экземпляр объекта типа «Крокодил», «кот Матроскин» — конкретный экземпляр объекта типа «Кошка домашняя».

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

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

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

Еще одним основополагающим понятием ООП является полиморфизм.

Полиморфизм представляет собой свойство различных объектов выполнять одно и то же действие по-своему.

Например, действие «бежать» свойственно большинству животных. Однако каждое из них (лев, слон, крокодил, черепаха) выполняет это действие различным образом.

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

Таким образом, в данном случае действие «бежать» будет называться полиморфическим действием, а многообразие форм проявления этого действия — полиморфизмом.

 

Информатика 23-24 г Тема. Формализация понятия алгоритма

 

Какими бывают алгоритмы

Несмотря на слово «последовательность», алгоритм не всегда описывает действия в жестко заданном порядке. Особенно это актуально сейчас, с распространением асинхронности в программировании. В алгоритмах есть место для условий, циклов и других нелинейных конструкций.

Линейные. Это самый простой тип алгоритма: действия идут друг за другом, каждое начинается после того, как закончится предыдущее. Они не переставляются местами, не повторяются, выполняются при любых условиях.

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

Циклические. Такие алгоритмы выполняются в цикле. Когда какой-то блок действий заканчивается, эти действия начинаются снова и повторяются некоторое количество раз. Цикл может включать в себя одно действие или последовательность, а количество повторений может быть фиксированным или зависеть от условия: например, повторять этот блок кода, пока в структуре данных не останется пустых ячеек. В некоторых случаях цикл может быть бесконечным.

Рекурсивные. Рекурсия — это явление, когда какой-то алгоритм вызывает сам себя, но с другими входными данными. Это не цикл: данные другие, но «экземпляров» работающих программ несколько, а не одна. Известный пример рекурсивного алгоритма — расчет чисел Фибоначчи.

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

Вероятностные. Такие алгоритмы упоминаются реже, но это довольно интересный тип: работа алгоритма зависит не только от входных данных, но и от случайных величин. К ним, например, относятся известные алгоритмы Лас-Вегас и Монте-Карло.

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

Графическое изображение алгоритмов

Алгоритмы могут записывать текстом, кодом, псевдокодом или графически — в виде блок-схем. Это специальные схемы, состоящие из геометрических фигур, которые описывают те или иные действия. Например, начальная и конечная точка на схеме — соответственно, начало и конец алгоритма, параллелограмм — ввод или вывод данных, ромб — условие. Простые действия обозначаются прямоугольниками, а соединяются фигуры с помощью стрелок — они показывают последовательности и циклы.

В схемах подписаны конкретные действия, условия, количество повторений циклов и другие детали. Это позволяет нагляднее воспринимать алгоритмы.

Сложность алгоритма

Понятие «сложность» — одно из ключевых в изучении алгоритмов. Оно означает не то, насколько трудно понять тот или иной метод, а ресурсы, затраченные на вычисление. Если сложность высокая, алгоритм будет выполняться медленнее и, возможно, тратить больше аппаратных ресурсов; такого желательно избегать.

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

Какой бывает сложность. Полностью разбирать математическую O-нотацию, как ее называют, мы не будем — просто перечислим основные обозначения сложности в теории алгоритмов.

 O(1) означает, что алгоритм выполняется за фиксированное константное время. Это самые эффективные алгоритмы.

 O(n) — это сложность линейных алгоритмов. n здесь и дальше обозначает размер входных данных: чем больше n, тем дольше выполняется алгоритм.

 O(n²) тоже означает, что чем больше n, тем выше сложность. Но зависимость тут не линейная, а квадратичная, то есть скорость возрастает намного быстрее. Это неэффективные алгоритмы, например с вложенными циклами.

 O(log n) — более эффективный алгоритм. Скорость его выполнения рассчитывается логарифмически, то есть зависит от логарифма n.

 O(√n) — алгоритм, скорость которого зависит от квадратного корня из n. Он менее эффективен, чем логарифмический, но эффективнее линейного.

Существуют также O(n³), O(nn) и другие малоэффективные алгоритмы с высокими степенями. Их сложность растет очень быстро, и их лучше не использовать.

Графическое описание сложности. Лучше разобраться в сложности в O-нотации поможет график. Он показывает, как изменяется время выполнения алгоритма в зависимости от размера входных данных. Чем более пологую линию дает график, тем эффективнее алгоритм.

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

Использование алгоритмов в IT

Мы приведем несколько примеров использования разных алгоритмов в отраслях программирования. На самом деле их намного больше — мы взяли только часть, чтобы помочь вам понять практическую значимость алгоритмов.

Разработка ПО и сайтов. Алгоритмы используются для парсинга, то есть «разбора» структур с данными, таких как JSON. Парсинг — одна из базовых задач, например в вебе. Также алгоритмы нужны при отрисовке динамических структур, выводе оповещений, настройке поведения приложения и многом другом.

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

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

Поисковые задачи. Алгоритмы поиска — отдельная сложная отрасль. Их выделяют в отдельную группу, в которой сейчас десятки разных алгоритмов. Поиск важен в науке о данных, в методах искусственного интеллекта, в аналитике и многом другом. Самый очевидный пример — поисковые системы вроде Google или Яндекса. Кстати, подробности об используемых алгоритмах поисковики обычно держат в секрете.

Машинное обучение. В машинном обучении и искусственном интеллекте подход к алгоритмам немного другой. Если обычная программа действует по заданному порядку действий, то «умная машина» — нейросеть или обученная модель — формирует алгоритм для себя сама в ходе обучения. Разработчик же описывает модель и обучает ее: задает ей начальные данные и показывает примеры того, как должен выглядеть конечный результат. В ходе обучения модель сама продумывает для себя алгоритм достижения этого результата.

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

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

Информатика 23-24 г Понятие о парадигмах программирования

 

Понятие о парадигмах программирования

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

Популярные подходы

Практически все современные языки программирования (далее ЯП) в той или иной мере позволяют разработчику использовать две или более различных парадигм, на первый взгляд сильно отличных друг от друга. В этом случае речь идет о так называемом мультипарадигменном создании приложений. Есть 4 популярных подхода к разработке программ, коротко рассмотрим их далее.

1.     Объектно-ориентированный подход

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

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

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

Инкапсуляция. Каждый объект независим, все данные и методы содержатся внутри него.

Наследование. ООП позволяет создавать массу новых объектов, похожих на уже готовый.

Полиморфизм. Взаимодействие между участками кода строится на базе единых правил.

Абстракция. Программа всегда может обратиться к методам и свойствам объекта извне.

Объектно-ориентированное программирование поддерживается большим числом языков, в числе которых известные С++, Java, JavaScript, Python, Swift.

2.     Декларативный подход

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

Главное достоинство декларативной методики в том, что написанный в соответствии с ней код компактен и прост для понимания. Но есть и серьезные недостатки:

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

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

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

3.     Императивный подход

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

В составе программы, написанной в императивном стиле, могут быть следующие инструкции:

1.     сложи два числа и выведи результат;

2.     отправь запрос на файловый сервер;

3.     открой программу и сверни ее в окно;

4.     выведи на экран сообщение и так далее.

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

4.     Функциональный подход

Используя функциональный стиль, разработчик описывает не четкую инструкцию в формате последовательности действий, а взаимодействие между командами и подпрограммами. В этом плане есть сходство с ООП, однако здесь такой подход реализуется на уровне всего приложения. Функциональная разработка поддерживается языками Haskell, Lisp, Erlang, Clojure и F#.

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

·        последовательность правил не имеет значения, они работают в любом месте кода;

·        все переменные работают как константы, иные данные хранятся в самих функциях;

·        функции возвращают предсказуемый результат, который не зависит от переменных;

·        последовательность исполнения подпрограмм определяет не программист, а код.

Функциональная парадигма существует более 60 лет, но до сих пор применяется точечно, имеет узкую сферу применения и проигрывает по популярности объектно-ориентированному подходу.

Объекты

Природа объектов

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

В общем случае каждый объект «помнит» необходимую информацию, «умеет» выполнять некоторый набор действий и характеризуется набором свойств.

То, что объект «помнит», хранится в его полях.
То, что объект «умеет делать», реализуется в виде его внутренних процедур и функций, называемых методами.
Свойства объектов аналогичны свойствам, которые мы наблюдаем у обычных предметов. Значения свойств можно устанавливать и читать. Программно свойства реализуются через поля и методы.

Пример:

Объект «кнопка» имеет свойство «цвет». Значение цвета кнопка запоминает в одном из своих полей. При изменении значения свойства «цвет» вызывается метод, который перерисовывает кнопку.

Этот пример позволяет сделать важный вывод: свойства имеют первостепенное значение для программиста, использующего объект. Чтобы понять суть и назначение объекта, вы обязательно должны знать его свойства, иногда — методы.

Задача1

 По каналу связи передаются сообщения, содержащие только семь букв: А, Б, В, Г, Й, К, Л. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Б  — 00, Г  — 010, К  — 101. Какое наименьшее количество двоичных знаков потребуется для кодирования слова БАЛАЛАЙКА?

 

Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.

Информатика 23-24гг Тема. Модели и моделирование. Графы и деревья.

 

Модели и моделирование. Графы и деревья.

Модель — это объект, который обладает существенными свойствами другого объекта, процесса или явления и используется вместо него.

Моделирование — это создание и исследование моделей с целью их изучения.

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

Информационные модели — это информация о свойствах оригиналах и его связях с внешним миром.

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

Еще информационные модели можно различать по фактору времени. Статистические, то есть те, в которых интересующие нас свойства не изменяются со временем, и динамические — это модели, которые описывают движение, развитие.

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

По характеру связей выделяются детерминированные и стохастические (случайные).

Стохастический -случайный, зависящий от случайных обстоятельств. Стохастическим считается непредсказуемый процесс, полностью зависящий от фактора случайности.

Детерминированность (от латинского-определяющий) — определяемость. Детерминированность -это процесс, исход которого полностью определен алгоритмом.

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

При моделировании всегда возникает вопрос: «Можно ли верить полученным результата?» Для этого проверяется свойство модели — АДЕКВАТНОСТЬ.

Адекватность — это совпадение существенных свойств модели и оригинала в рассматриваемой задаче. Доказать адекватность модели можно только в сравнении с оригиналом.

Для этого проверяется:

— не противоречит ли результат моделирования выводам теории,

— подтверждается ли результат моделирования результатами эксперимента.

Таким образом, любое моделирование должно соответствовать следующей схеме.

Такое моделирование позволяет:

1. Существенно расширить круг исследуемых объектов.
2. Исследовать процессы и явления, при необходимости ускорять или замедлять процесс.
3. Находить оптимальное соотношение затрат.
4. Проводить эксперименты без риска негативных последствий.
5. Визуализировать полученные результаты.

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

Графом называется геометрическая фигура, состоящая из точек и соединяющих их линий. Точки называются вершинами графа, а линии — ребрами. Каждому ребру сопоставлены две вершины — концы ребра.

Граф является многосвязной структурой, обладающей следующими свойствами:

— на каждый элемент может быть произвольное количество ссылок;

— каждый элемент может иметь связь с любым количеством элементов;

— каждая связка может иметь направление и вес.

Направленная (без стрелки) линия, соединяющая вершины графа, называется ребром.

Линия направленная (со стрелкой) называется дугой.

Граф называется неориентированным, если его вершины соединены ребрами.

Граф называется ориентированным, если его вершины соединены дугами.

Граф называется взвешенным, если его вершины или ребра характеризуются некоторой дополнительной информацией — весами вершин или ребер.

Среди информационных моделей можно выделить графические информационные модели, к которым относятся карты, чертежи, схемы, диаграммы, графики и предмет сегодняшнего рассмотрения — графы.

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

Если рёбра графа имеют направление, то оно отображается стрелками, а граф называется ориентированным (направленным).

Вершины графа могут отображаться точками, кругами, прямоугольниками и т.д.

Если вершины или ребра графа характеризуются некоторой дополнительной информацией — весом вершины или ребра, то такой граф называют взвешенным.

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

Проведём путь, проходящий по вершинам и ребрам графа так, чтобы любое ребро входило в него не более одного раза. Такой путь называется цепью. Цепь, у которой совпадают начальная и конечная вершины, называется циклом.

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

Информационные модели в виде графов широко используются в повседневной жизни.

Например, при проектировании нового жилого района можно здания обозначить как вершины графа, а дороги, коммуникации и т.д. — ребрами графа. По таким графам удобно, например, прогнозировать загрузку дорог и находить оптимальные транспортные маршруты. Другим примером является схема метрополитена. Вершинами в графе в этом случае являются станции метро.

Граф, в котором отсутствуют циклы, называется деревом.

В этом случае между любыми двумя вершинами существует только один путь.

С помощью дерева удобно представлять иерархическую систему.

У дерева выделяется одна главная вершина, которую называют корнем.

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

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

Существуют задачи, которые удобно решать с помощью графов.

Например, если мы хотим отобразить все возможные варианты трехзначных чисел, которые могут получиться из цифр 7 и 8.

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

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

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

Вводятся понятия — Граф. Вершина, ребро, путь. Ориентированные и неориентированные графы. Длина (вес) ребра и пути. Дерево. Корень, лист, вершина.