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


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

Содержание

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

Слайды и текст этой презентации

Слайд 1Алгоритмы и структуры данных

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

Слайд 2Литература:
Д. Кнут. Искусство программирования для ЭВМ. Т. 1-3, М.: Мир,

1978, 1995 и др..
Н. Вирт. Алгоритмы и структуры данных. М.:

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

Слайд 3Концепция типа данных
Информация, которая должна обрабатываться на компьютере является абстракцией,

отображением некоторого фрагмента реального мира. А именно того фрагмента, который

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

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

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

Концепция типа данныхИнформация, которая должна обрабатываться на компьютере является абстракцией, отображением некоторого фрагмента реального мира. А именно

Слайд 4Компьютерные данные это дискретные сообщения, которые представлены в форме, используемой

в компьютере, понятной компьютеру. Для процессора компьютера любые данные представляют

собой неструктурированную последовательность битов (иногда используют термин поток битов).

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


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

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

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

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

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

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

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

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

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

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

Слайд 6Разновидности типов и структур данных
В информатике используется большое количество различных

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

в рассматриваемых задачах.

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

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

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

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

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

Слайд 7Различают предопределенные (предварительно определенные) - стандартные и определяемые в программе

типы. Для стандартных типов в описании языка программирования заданы все

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

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

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

Различают предопределенные (предварительно определенные) - стандартные и определяемые в программе типы. Для стандартных типов в описании языка

Слайд 8Наиболее часто используемые предопределенные скалярные типы: целый (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

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

Слайд 9Основные механизмы построения новых скалярных дискретных типов: перечисление, ограничение. В

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

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

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

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

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

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

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

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

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

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

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

полями. Различные поля (столбцы таблицы) могут быть разных типов. Для

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

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

День Победы:

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

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




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

Структуры, аналогичные строкам таблицы, называют записями. Компоненты записей	 принято называть полями. Различные поля (столбцы таблицы) могут быть

Слайд 12
Множество
Во многих математических и информационных задачах возникает необходимость в прямом

или косвенном использовании основного математического объекта множества. Соответствующая множеству тип

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

X1 X5 X4

X17

X2

X3

?

X17

?

X3

X

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

Слайд 13Динамические структуры данных
У данных с динамической структурой с течением

времени изменяется сама структура, а не только количество элементов, как

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

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

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

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

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

Динамические структуры данных У данных с динамической структурой с течением времени изменяется сама структура, а не только

Слайд 14На базе линейного списка организуются много других типов динамических структур.

Это в частности: кольца, очереди, деки и стеки.
Структура кольца
Отличие

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

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

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

Слайд 15Структура очереди
У очереди доступен для включения конец, а для исключения

(выборки) ─ начало. Элемент, поступивший в очередь раньше и обслуживается

раньше. Говорят, что очередь это структура с дисциплиной обслуживания FIFO (First In, First Out) ─ «первый пришёл, первый ушел».

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

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

Структура очередиУ очереди доступен для включения конец, а для исключения (выборки) ─ начало. Элемент, поступивший в очередь

Слайд 16Структура стека
У стека для взаимодействия доступна только один конец структуры

─ вершина стека. И включение нового элемента в стек и

выборка последнего ранее включенного идет через вершину стека. Таким образом на обслуживание попадает первым элемент, поступивший последним. Говорят, что стек ─ это структура с дисциплиной обслуживания LIFO (Last In, First Out) ─ «последним пришёл, первым ушёл».
Структура стекаУ стека для взаимодействия доступна только один конец структуры ─ вершина стека. И включение нового элемента

Слайд 17СПАСИБО ЗА ВНИМАНИЕ!

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

Обратная связь

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

Email: Нажмите что бы посмотреть 

Что такое TheSlide.ru?

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


Для правообладателей

Яндекс.Метрика