Базовые структуры алгоритмов. Презентация к уроку информатики базовые алгоритмические структуры Базовая структура "следование"

Чтобы пользоваться предварительным просмотром презентаций создайте себе аккаунт (учетную запись) Google и войдите в него: https://accounts.google.com

Подписи к слайдам:

Урок-зачёт Алгоритм, его свойства и основные алгоритмические структуры

Ничто не приближает человека к богам настолько, как совершение добрых дел. Марк Тулий Цицерон

План зачёта «Письмо потомкам» Самостоятельная работа Решение задач Домашнее задание

Что такое алгоритм? Алгоритм – описание последовательности действий, направленных на получение из данных за конечное число дискретных шагов с помощью команд, понятных. детерминированной исходных результата исполнителю

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

Формы представления алгоритмов Словесная устная. Словесная письменная Графическая (блок-схема):

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

– начало / конец алгоритма. – ввод / вывод данных. – вычисление (выполнение действия). – проверка условия (принятие решения).

Основные типы алгоритмических структур: Линейная Разветвляющаяся Циклическая

«Развилки» бывают в полной и неполной форме

Циклический алгоритм бывает «цикл со счётчиком», «цикл с предусловием» и «цикл с постусловием»

Вычислить площадь и периметр прямоугольника. начало конец S = a*b Ввести a, b Вывести S , Р Р = (a + b)*2

Вычисления значения гипотенузы прямоугольного треугольника, если известны значения его катетов начало Ввести a, b с = √ a 2 + b 2 Вывести с конец

Вычислить функцию, заданную в зависимости от значения аргумента начало Х

Составить блок-схему определения значения функции у = √ х, при х – неотрица тельном. начало Х > = 0 у = √ х не сущ-ет конец

Сумма чисел из промежутка от 5 до 10 начало а от 5 до 10 s = s + a S = 0 конец начало s = s + a a

Произведение всех чисел из промежутка от 5 до 10 начало а от 5 до 10 s = s * a S = 1 конец начало s = s * a a

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

Попробуйте сформулировать известную русскую пословицу по ее блок-схеме

Попробуйте сформулировать известную русскую пословицу по ее блок-схеме

Определить результат работы алгоритма, представленного в виде блок-схемы

Составьте блок-схему по высказыванию «Если мысль нельзя выразить простыми словами, значит, она ничтожна и надо ее отбросить.»

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

Домашнее задание: Создать в рабочей тетради блок-схему к любой известной русской пословице.

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

Первая базовая структура - следование
состоит из цепочки блоков без
разветвлений.

Ветвление

да
нет
условие

Частный случай ветвления
условие

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

Цикл

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

Цикл с постусловием

Цикл с предусловием

Параметрический цикл

Параметрический цикл управляется
параметром.
Параметр цикла – это переменная,
которая монотонно меняется в цикле,
и от неё зависит критерий выхода из
цикла.

i:= in
Тело
цикла
i:= i + di
нет
да
i > ik

i:=in
i>ik
Тело
цикла
i:=i+di

Проектирование сложных алгоритмов

Метод проектирования алгоритмов «сверху – вниз»

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

Пример

Задано уравнение ax2 + bx + c = 0 и функция
f(x).
Если уравнение имеет два действительных
корня x1 и x2, построить таблицу значений
функции на отрезке , состоящую из n
точек.

Алгоритм верхнего уровня
Ввод a,b,c
Решение
уравнения
нет
х1,х2
найдены
да
Ввод n
Построение
таблицы
Нет решения
STOP

Алгоритм, реализующий подзадачу решения
квадратного уравнения
d:=b2 – 4ac
нет
D>0
да
X1=(- b + √ d)/2/а
X2= (- b - √ d)/2/а

Алгоритм построения таблицы значений
функции
h=(x2-x1)/(n-1)
x = x1
i=1
Вывод x, f(x)
x=x+h
i = i +1
да
нет
i >n

Таким образом, решение поставленной
задачи состоит из алгоритма верхнего
уровня и двух подзадач.
Алгоритм, связывающий подзадачи
Решение
уравнения
Построение
таблицы f(x)

Ширина блока px

Скопируйте этот код и вставьте себе на сайт

Подписи к слайдам:

Алгоритмы и структуры данных Литература:

• Д. Кнут. Искусство программирования для ЭВМ. Т. 1-3, М.: Мир, 1978, 1995 и др..
• Н. Вирт. Алгоритмы и структуры данных. М.: Мир, 1989.

Концепция типа данных

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

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

• Дискретное сообщение - это последовательность знаков (значений сиг-нала) из некоторого конечного алфавита (конечного набора значений па-раметра сигнала), в частности, для компьютера это последовательность знаков двоичного алфавита, то есть последовательность битов .

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

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

• Непосредственные значения это неизменные объекты программы, которые представляют сами себя: числа (25, 1.34E-20), символы (‘A’, ‘!’) , строки (‘Введите элементы матрицы’);
• Константы – это имена, закрепляемые за некоторыми значениями (const pi=3.1415926).
• Переменные это объекты, которые могут принимать значение, сохранять его без изменения, и изменять его при выполнении определенных действий (var k:integer, x:real, a:array).
• Значения выражений и функций . Выражения и функции– это записанные определённым способом правила вычисления значений: k*x+ sqrt(x).

• К данным в программах относятся:

• Тип данных представляет собой важнейшую характеристику, которая определяет:

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

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

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

• Основные принципы концепции типа данных
• в языках программирования:

• Разновидности типов и структур данных

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

• Если структура данного по ходу выполнения алгоритма не изменяется, то такая структура считается статической , Статические структуры данных существуют в неизменном виде в течение всего времени исполнения алгоритма .

• Значение скалярного (простого, атомарного) типа представлено ровно одним компонентом (пример: время, температура).

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

• Значение структурированного (составного) типа представлено более чем одним компонентом (пример: вектор, матрица, таблица и т.д.).

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

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

• Статические типы (структуры данных)

• Наиболее часто используемые предопределенные скалярные типы: целый (integer ), вещественный (real ), символьный (char ), логический (boolean ).

• Целочисленные точные значения. Примеры: 73, -98, 5, 19674.
• Машинное представление: формат с фиксированной точкой. Диапазон значений определяется длиной поля. Операции: +, -, *, div, mod,=, <, и т.д.

• Тип integer

• Нецелые приближенные значения. Примеры: 0.195, -91.84, 5.0
• Машинное представление: формат с плавающей точкой. Диапазон и точность значений определяется длиной поля. Операции: +, -, *, /, =, <, и т.д.

• Тип real

• Одиночные символы текстов. Примеры: ‘a’, ‘!’, ‘5’.
• Машинное представление: формат ASCII. Множество значений определяется кодовой таблицей и возможностями клавиатуры. Операции: +, =, <, и т.д.

• Тип char

• Два логических значения false и true. Причем, false
• Машинное представление ─ нулевое и единичное значение бита: false кодируется 0, true ─ 1. Операции: , , , =, < и т.д.

• Тип boolean

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

• Различают дискретные и непрерывные скалярные типы. Множество значений дискретного типа конечное или счетное. Множество значений непрерывного типа более чем счетное. К дискретным стандартным типам относятся целый, символьный и логический. К непрерывным стандарт-ным типам относится вещественный.

• Структурированные (составные) типы характеризуются: количеством и возможным типом компонентов значения, а также способом доступа к отдельному компоненту значения.

• Структуры аналогичные векторам и матрицам в информатике принято называть массивами . Все элементы массива должны быть одного и того же типа.

• Массив или регулярный тип

• Для доступа (обращения) к отдельному элементу массива используется индекс или несколько индексов (w; w; A). Индексы могут быть выражениями, значения которых могут произвольным образом изменяться в заранее заданных границах. Поэтому говорят, что к элементам массивов имеется прямой доступ .

• Структуры, аналогичные строкам таблицы, называют записями . Компоненты записей принято называть полями . Различные поля (столбцы таблицы) могут быть разных типов. Для доступа к отдельным полям записи используются их фиксированные и неизменные имена . Например: День Победы. Месяц:= май . Поля могут выбираться для обработки в произвольном порядке, поэтому говорят, что доступ к компонентам записи прямой .

• Запись или комбинированный тип

• День Победы:

• Файл (последовательность)

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

• Полёт Гагарина:

• Множество

• Во многих математических и информационных задачах возникает необходимость в прямом или косвенном использовании основного математического объекта множества . Соответствующая множеству тип данных по определению отно-сится к структурированным, так как в общем случае множество может состоять более чем из одного элемента, и при этом со всеми элементами множества приходится выполнять операции как с единым целым. Количество элементов в множестве заранее не определяется, и с течением времени оно может изменятся. Все элементы множества должны быть одного и того же типа. Доступа к отдельным элементам множества нет . Можно только узнать принад-лежит элемент множеству или нет, включить элемент в множество или исклю-чить его из множества. Предусмотрены также стандартные операции над мно-жествами: объединение, пересечение, вычитание и т.д.

• X1 X5 X4

• Динамические структуры данных

• У данных с динамической структурой с течением времени изменяется сама структура , а не только количество элементов, как у файлов или последова-тельностей. Базовыми динамическими структурами данных являются:

• объект;
• линейный список;
• дерево;
• граф.

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

• Линейный список

• В целом получается цепочка элементов, в которой можно осуществлять поиск, в которую можно вставлять элементы или исключать их.

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

• Структура кольца

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

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

• Структура очереди

• У очереди доступен для включения конец, а для исключения (выборки) ─ начало. Элемент, поступивший в очередь раньше и обслуживается раньше. Говорят, что очередь это структура с дисциплиной обслуживания FIFO (F irst I n, F irst O ut) ─ «первый пришёл, первый ушел».

• Структура дека

• У дека оба конца доступны, как для включения, так и для выборки. Таким обра-зом, можно сказать, что дек ─ это двусторонняя очередь.

• Структура стека

• У стека для взаимодействия доступна только один конец структуры ─ вершина стека. И включение нового элемента в стек и выборка последнего ранее включенного идет через вершину стека. Таким образом на обслуживание попадает первым элемент, поступивший последним. Говорят, что стек ─ это структура с дисциплиной обслуживания LIFO (L ast I n, F irst O ut) ─ «последним пришёл, первым ушёл».

• СПАСИБО ЗА ВНИМАНИЕ!