Основные алгоритмические структуры | Сайт учителя Информатики и Экономики Щёголевой А. П

Примерный конспект урока по информатике для учителя.

____________Тема: Основные алгоритмические структуры: следствие, ветвление, цикл; изображение на блок-схемах. 9 класс

Учитель Информатики и ИКТ: Щёголева А.П.
Цели:
Дидактическая: познакомить учащихся с алгоритмической структурой следствие и ветвление. Сформировать практические навыки составления и записи алгоритмических структур следствие и ветвление.
Развивающая: развивать у учащихся логическое мышление, память, скорость реакции, смекалку.
Воспитывающая: воспитывать творческий интерес к изучению нового материала.
Средства обучения: презентация, программа Вычислительная математика и программирование.

План урока
Орг.момент (3 мин.)
Актуализация опорных знаний (7 мин.)
Изучение нового материала (10 мин.)
Закрепление материала(15 мин. )
Итоги урока (5 мин.)
Домашнее задание
Ход урока

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

Актуализация опорных знаний – фронтальный опрос: слайд 2
1. Что такое алгоритм? (ответ: Алгоритм – это строго детерминированная (однозначная) последовательность действий, описывающая процесс преобразования объекта из начального состояния в конечное, записанная с помощью понятных исполнителю команд.)
2. Какими свойствами обладает алгоритм? (Ответ:
Ученик 1: Процесс решения задачи должен быть разбит на последовательность отдельно выполняемых шагов. Это свойство алгоритма называется дискретностью.
Ученик 2: Алгоритм, составленный для конкретного исполнителя, должен включать только те команды, которые входят в систему команд исполнителя. Это свойство алгоритма называется понятностью.
Ученик 3: Каждая команда алгоритма должна определять однозначное действие исполнителя. Это свойство алгоритма называется точностью.
Ученик 4: Еще одно важное требование, предъявляемое к алгоритму — это свойство конечности (иногда говорят — результативности) алгоритма. Это значит, что: Исполнение алгоритма должно завершиться за конечное число шагов.
Ученик 5: Массовость – алгоритм должен давать решение не только для конкретного набора значений, а для целого класса задач, который определяется диапазоном возможных исходных данных (область применимости алгоритма).
3. Способы записи алгоритмов?(Ответ: словесный, графический, с помощью программ)
4. Кто или что является исполнителем алгоритмов? (Ответ: Исполнителем алгоритма может быть как техническое устройство, так и живое существо.К примеру, человек, собака, компьютер, машина и т.д.)

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

На этом уроке будут рассмотрены алгоритмические структуры : следствие (линейный алгоритм), ветвление, цикл.

Слайд 3
1. Линейный алгоритм – это такой, в котором все операции выполняются последовательно одна за другой (рис. 1.).
2. Разветвляющий алгоритм – это алгоритм, в котором в зависимости от условия выполняется либо одна, либо другая последовательность действий (рис.2). слайд 4
3. В алгоритмической структуре “цикл” серия команд (тело цикла) выполняется многократно.
Цикл – составная команда алгоритма, в которой в зависимости от значения логического выражения возможно многократное выполнение действия. слайд 5
Базовые структуры алгоритмов:

 

 

 

 

Характерной особенностью базовых структур является наличие в них одного входа и одного выхода.

Неполная форма алгоритма ветвления выглядит следующим образом:
ЕСЛИ <условие>ТО <действие >
IF<условие> THEN <ОПЕРАТОР>

Полная форма алгоритма ветвления выглядит следующим образом:
ЕСЛИ <условие>ТО <действие1 >ИНАЧЕ<действие2 >
IF<условие> THEN <действие 1>ELSE <действие 2> (слайд 6-8)

Если в комнате темно, тогда надо включить свет.
ЕСЛИ хочешь быть здоров, ТО закаляйся
ИНАЧЕ можешь часто болеть.

Цикл с предусловием (иначе цикл пока) имеет вид: (слайд 9)

Форматы записи операторов алгоритма	Блок-схема	Форматы записи операторов на Паскале
Пока (условие) нц серия команд кц		while условие do begin             серия команд; end;

Цикл с постусловием (иначе цикл до) имеет вид:

Форматы записи операторов алгоритма	Блок-схема	Форматы записи операторов на Паскале
В алгоритмическом языке нет команды, которая могла бы описать данную структуру, но ее можно выразить с помощью других команд (Например, ветвления).		repeat серия команд until условие

Цикл с параметром (иначе цикл для) имеет вид:

Форматы записи операторов алгоритма	Блок-схема	Форматы записи операторов на Паскале
Для i от а до b шаг h делай Нц Серия команд кц		h = +1 for i:= a to b do      begin        серия команд      end; h = -1 for i:= b downto a do      begin        Cерия команд;      end;

Физкультминутка для глаз: слайд 10-12
Для просмотра физминутки – нажмите на изображение:

Увеличить

1. Голову держать прямо. Поморгать, не напрягая глазные мышцы
2. В среднем темпе проделать 3 круговых движения в правую сторону, столько же в левую сторону
3. В среднем темпе посмотреть на лево, вверх, на право, вниз – проделать 3 и столько же в обратном направлении.
4. В среднем темпе проделать 6 круговых движений в форме восьмёрки.

Приведём примеры алгоритмов в виде блок-схем:
Пример: Алгоритм «Погода»

Словесная форма	Блок-схема
начало определить температуру воздуха если температура ниже 0, то надеть шубу, иначе надеть куртку конец

Вся программа состоит из команд (операторов). Команды бывают простые и составные (команды, внутри которых встречаются другие команды). Составные команды часто называют управляющими конструкциями.
Закрепление материала: Для лучшего понятия и закрепления материала откроем программу Вычислительная математика и программирование и в разделе Курсы выберим тему алгоритмизация – далее урок Практикум 1. Ветвление в алгоритмах. Игра “Ежиные тропы”

Итог урока:
Решите тест. В каждом задании представлены варианты ответов, необходимо выбрать правильный ответ Слайд 15-16.

1. Свойство алгоритма, заключающееся в том, что каждое действие и алгоритм в целом должны иметь возможность завершения…

а) дискретность;

б) детерминированность;

в) конечность;

г) массовость.

2. Свойством алгоритма является:

а) результативность;

б) цикличность;

в) возможность изменения последовательности выполнения команд;

г) возможность выполнения алгоритма в обратном порядке.

3. Алгоритмом является:

а) прайс лист;

б) инструкция по получению денег в банкомате;

в) расписание уроков;

г) список класса.

4. Алгоритм это:

а) правила выполнения определённых действий;

б) ориентированный граф, указывающий порядок выполнения некоторого набора команд;

в) описание последовательности действий, строгое исполнение которых приводит к решению поставленной задачи за конечное число шагов;

г) набор команд ля компьютера.

5. Алгоритм называется циклическим:

а) если он начинается с конца;

б) если серия команд повторяется многократно, в зависимости от условия задачи;

в) если в программе упорядочены действия;

г) всё выше перечисленное верно.

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

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

Lecture Slides for Algorithm Design by Jon Kleinberg And Éva Tardos

Это переработанная версия слайдов лекций. которые сопровождают учебник Разработка алгоритма

Джон Клейнберг и Эва Тардос. Вот оригинальная и официальная версия слайды, распространяемые Пирсон.

ТЕМА	СЛАЙДЫ	ЧТЕНИЯ	ДЕМОС
Стабильное соответствие ( Гейл–Шепли )	1 шт. · 4 шт.	Глава 1	Гейл-Шепли
Анализ алгоритмов ( большое обозначение O )	1 шт. · 4 шт.	Глава 2	бинарный поиск
Графики ( поиск по графику )	1 шт. · 4 шт.	Глава 3	–
Жадные алгоритмы I ( основные методы )	1 шт. · 4 шт.	Глава 4	интервальное планирование интервальное разбиение
Жадные алгоритмы II ( кратчайших путей и MST )	1 шт. · 4 шт.	Глава 4	Дейкстра Прим, Крускал, Борувка Эдмондс
Разделяй и властвуй I ( сортировка и отбор )	1 шт. · 4 шт.	Глава 5	слияние быстрый выбор
Разделяй и властвуй II ( целочисленное и полиномиальное умножение )	1 шт. · 4 шт.	Глава 5	–
Динамическое программирование I ( основные техники )	1 шт. · 4 шт.	Глава 6	–
Динамическое программирование II ( выравнивание последовательностей, Беллман-Форд )	1 шт. · 4 шт.	Глава 6	–
Сетевой поток I ( теория максимального потока )	1 шт. · 4 шт.	Глава 7	Форд-Фулкерсон
Сетевой поток II ( приложений максимального потока )	1 шт. · 4 шт.	Глава 7	–
Сетевой поток III ( задача назначения )	1 шт. · 4 шт.	Глава 7	–
Неразрешимость I ( сокращения за полиномиальное время )	1 шт. · 4 шт.	Глава 8	–
Неразрешимость II ( P, NP и NP-complete )	1 шт. · 4 шт.	Глава 8	–
Непокорность III ( преодоление неподатливости )	1 шт. · 4 шт.	Раздел 10.2, 11.8	независимый комплект крышка вершины
PSPACE ( PSPACE класса сложности )	1 шт. · 4 шт.	Глава 9	–
Пределы управляемости ( расширение границ управляемости )	1 шт. · 4 шт.	Глава 10	–
Алгоритмы аппроксимации ( алгоритмы аппроксимации )	1 шт. · 4 шт.	Глава 11	список планирования
Локальный поиск ( Метрополис, сети Хопфилда )	1 шт. · 4 шт.	Глава 12	–
Рандомизированные алгоритмы ( рандомизированные алгоритмы )	1 шт. · 4 шт.	Глава 13	–
Структуры данных I ( амортизированный анализ )	1 шт. · 4 шт.	Глава 17 ( CLRS )	динамическая таблица
Структуры данных II ( двоичные и биномиальные кучи )	1 шт. · 4 шт.	Глава 6 ( CLRS, 2-е издание )	двоичная куча куча
Структуры данных III ( Кучи Фибоначчи )	1 шт. · 4 шт.	Глава 19 ( CLRS )	–
Структуры данных IV ( объединение-найти )	1 шт. · 4 шт.	Раздел 5.1.4 ( Дасгупта и др. )	–
Линейное программирование I ( симплексный алгоритм )	1 шт. · 4 шт.	( Хватал )	–
Линейное программирование II ( двойное линейное программирование )	1 шт. · 4 шт.	( Хватал )	–
Линейное программирование III ( Алгоритм эллипсоида )	1 шт. · 4 шт.	конспект лекций ( Мишель Гуманс )	–

Ссылки.

Слайды лекций основаны в первую очередь на учебнике:

• Разработка алгоритма Джон Клейнберг и Эва Тардос. Аддисон-Уэсли, 2005 г.

Некоторые слайды лекций основаны на материалах из следующих книг:

• Введение в алгоритмы, третье издание Томас Кормен, Чарльз Лейзерсон, Рональд Ривест и Клиффорд Штейн. Массачусетский технологический институт, 2009.
• Алгоритмы Санджой Дасгупта, Христос Пападимитриу и Умеш Вазирани. Макгроу Хилл, 2006 г.
• Разработка и анализ алгоритмов Декстер Козен. Спрингер, 1992.
• Алгоритмы 4/e Роберт Седжвик и Кевин Уэйн. Эддисон-Уэсли Профессионал, 2011.
• Структуры данных и сетевые алгоритмы Роберт Тарьян. Общество промышленной и прикладной математики, 1987.
• Линейное программирование Автор Вашек Хватал. WH Freeman, 1983.

Инструкторы.

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

Исправления.

Вот известные опечатки в этих слайдах лекции.

Кредиты.

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

10 графических алгоритмов с визуальным объяснением | by Vijini Mallawaarachchi

Краткое введение в 10 основных графовых алгоритмов с примерами и визуализациями

Vijini Mallawaarachchi

·

Подписаться

Опубликовано в

·

Чтение: 8 мин.

·

27 августа 2020 г.

Графики стали мощным средством моделирования и сбора данных в реальных сценариях, таких как социальные сети, веб-страницы и ссылки, и местоположения и маршруты в GPS. Если у вас есть набор объектов, связанных друг с другом, вы можете представить их с помощью графа.

В этой статье я кратко объясню 10 основных алгоритмов работы с графами, которые очень полезны для анализа и их применения.

Во-первых, давайте представим график.

Граф состоит из конечного набора вершин или узлов и набора ребер , соединяющих эти вершины. Две вершины называются 90 528 смежными 90 529, если они соединены друг с другом одним и тем же ребром.

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

• Порядок: Количество вершин в графе
• Размер: Количество ребер в графе
• Степень вершины: Количество ребер, инцидентных вершине
• Изолированная вершина: Вершина, не связанная ни с какими другими вершинами в графе
• Самопетля : Ребро из вершины в себя
• Ориентированный граф: Граф, в котором все ребра имеют направление, указывающее начальную вершину и конечную вершину
• Неориентированный граф: 9Рис. )Рис. 2. Анимация обхода BFS графа (изображение автора)

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

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

  Приложения

  • Используется для определения кратчайших путей и минимальных остовных деревьев.
  • Используется сканерами поисковых систем для создания индексов веб-страниц.
  • Используется для поиска в социальных сетях.
  • Используется для поиска доступных соседних узлов в одноранговых сетях, таких как BitTorrent.
  Рис. 3. Анимация обхода графа DFS (Изображение автора) ). В DFS мы также должны отслеживать посещенные вершины. При реализации DFS мы используем структуру данных стека для поддержки поиска с возвратом.

  На рис. 3 показана анимация обхода в глубину того же примера графа, что и на рис. 2. Обратите внимание, как он перемещается вглубь и возвращается назад.

  Приложения

  • Используется для поиска пути между двумя вершинами.
  • Используется для обнаружения циклов на графике.
  • Используется в топологической сортировке.
  • Используется для решения головоломок, имеющих только одно решение (например, лабиринты)
  Рис. 4. Анимация, показывающая кратчайший путь из вершины 1 в вершину 6 (Изображение автора)

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

  На рис. 4 показана анимация, в которой кратчайший путь определяется из вершины 1 в вершину 6 графа.

  Алгоритмы

  1. Алгоритм кратчайшего пути Дейкстры
  2. Алгоритм Беллмана-Форда

  Приложения

  • Используется для поиска направления движения из одного места в другое в картографических программах, таких как карты Google или Apple. .
  • Используется в сети для решения проблемы пути с минимальной задержкой.
  • Используется в абстрактных машинах для определения вариантов достижения определенного целевого состояния путем перехода между различными состояниями (например, может использоваться для определения минимально возможного количества ходов для победы в игре).
  Изображение Daniel Dino-Slofer с PixabayРис. 5. Цикл (изображение автора)

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

  Алгоритмы

  1. Алгоритм обнаружения цикла Флойда
  2. Алгоритм Брента

  Приложения

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

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

  На рис. 6 показана анимация, показывающая процесс получения минимального остовного дерева.

  Алгоритмы

  1. Алгоритм Прима
  2. Алгоритм Крускала

  Приложения

  • Используется для построения деревьев для вещания в компьютерных сетях.
  • Используется в графическом кластерном анализе.
  • Используется при сегментации изображений.
  • Используется при районировании социально-географических районов, когда регионы группируются в смежные регионы.
  Рис. 7. Сильно связанные компоненты (изображение автора)

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

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

  Алгоритмы

  1. Алгоритм Косараджу
  2. Алгоритм компонентов сильной связности Тарьяна

  Приложения

  • ребра двудольного графа.
  • Используется в социальных сетях для поиска группы людей, тесно связанных между собой, и предоставления рекомендаций на основе общих интересов.
  Изображение Gerd Altmann с PixabayРис. 8. Топологическое упорядочение вершин в графе (Изображение автора)

  Топологическая сортировка графа представляет собой линейное упорядочение его вершин так, что для каждого направленного ребра (u, v ) в упорядочении вершина u предшествует v.

  На рис. 8 показан пример топологического упорядочения вершин (1, 2, 3, 5, 4, 6, 7, 8). Вы можете видеть, что вершина 5 должна идти после вершин 2 и 3. Точно так же вершина 6 должна идти после вершин 4 и 5.

  Алгоритмы

  1. Алгоритм Кана
  2. Алгоритм, основанный на поиске в глубину

  Приложения

  • Используется при планировании команд.
  • Используется при сериализации данных.
  • Используется для определения порядка выполнения задач компиляции в make-файлах.
  • Используется для разрешения зависимостей символов в компоновщиках.
  Рис. 9. Окраска вершин (Изображение автора)

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

  Хроматическое число графика — это наименьшее количество цветов, необходимое для раскрашивания графика.

  На рис. 9 показана раскраска вершин примера графа с использованием 4 цветов.

  Алгоритмы

  1. Алгоритмы, использующие поиск в ширину или поиск в глубину
  2. Жадная раскраска

  Приложения

  • Используется для планирования расписания.
  • Используется для присвоения частот мобильной радиосвязи.
  • Используется для моделирования и решения таких игр, как судоку.
  • Используется для проверки двудольности графа.
  • Используется для раскрашивания географических карт стран или штатов, где соседние страны или штаты окрашены в другой цвет.
  Изображение TheAndrasBarta с PixabayРис. 10. Определение максимального потока (Изображение автора)

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

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

  Алгоритмы

  1. Алгоритм Форда-Фалкерсона
  2. Алгоритм Эдмондса-Карпа
  3. Алгоритм Диника

  Приложения

  • Используется в расписании авиакомпаний для составления расписания полетов.
  • Используется при сегментации изображения для поиска фона и переднего плана в изображении.
  • Используется для устранения бейсбольных команд, которые не могут выиграть достаточно игр, чтобы догнать текущего лидера в своем дивизионе.
  Рис. 11. Сопоставление двудольного графа (изображение автора)

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

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

  Алгоритмы

  1. Алгоритм Хопкрофта-Карпа
  2. Венгерский алгоритм
  3. Алгоритм цветения

  Приложения

  • Используется в сватовстве для сватовства женихов и невест (задача стабильного брака).
  • Используется для определения покрытия вершин.
  • Используется в теории транспорта для решения задач распределения ресурсов и оптимизации путешествий.

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

  Вы можете ознакомиться с реализациями графовых алгоритмов, найденными в networkx и igraph модули python. Вы можете прочитать о python-igraph в моей предыдущей статье «Руководство для новичков по Python-igraph».

  Руководство для новичков по Python-igraph

  Простое руководство по основным функциям python-igraph с примерами и кодом

  в направлении datascience.