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

Август 23, 2022

Главная
Информатика
Алгоритмы и структуры данных. Введение

Содержание

2. Обо мне Крахмалёв Денис Сергеевич Аспирант ФПМИ МФТИ CV-Engineer в PicsArt krakhmalev23@gmail.com vk.com/d_krakhmalev tg: @krakhmalyov Чат
3. Алгоритм Это последовательность команд, предназначенная исполнителю, в результате выполнения которой он должен решить поставленную задачу.
4. Примеры простых алгоритмов вычисление факториала числа проверка числа на простоту быстрое возведение в степень
5. Структура и Абстрактный тип данных Структура -- программная единица, позволяющая хранить и обрабатывать множество однотипных и/или
6. Динамический массив
7. Двусвязный и односвязный списки
8. Стек и очередь
9. Двусторонная очередь (дек)
10. Хранение стека, дека, очередь в массиве/списке
11. Поиск элемента в массиве Линейный Бинарный
12. Поддержка минимума в стеке
13. Асимптотические обозначения
14. Асимптотика простых алгоритмов
15. Амортизационный анализ Средняя амортизационная стоимость операций — величина a, находящаяся по формуле: t1,t2…tn — время выполнения
16. Метод усреднения Считаем среднюю амортизационную стоимость по формуле
17. Метод предоплаты Каждой операции над структурой присваивается “стоимость” При проведении операции от этой стоимости отнимается фактическое
18. Метод потенциалов
19. Представление очереди в виде двух стеков
20. Поддержка минимума в очереди
21. Двоичная куча. АТД “Очередь с приоритетом”
23. Скачать презентацию

Слайд 2

Обо мне
Крахмалёв Денис Сергеевич
Аспирант ФПМИ МФТИ
CV-Engineer в PicsArt
krakhmalev23@gmail.com
vk.com/d_krakhmalev
tg: @krakhmalyov
Чат курса
https://t.me/joinchat/R_TklPBYtH8wNWIy

Слайд 3

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

решить поставленную задачу.

Слайд 4

Примеры простых алгоритмов
вычисление факториала числа
проверка числа на простоту
быстрое возведение в степень

Слайд 5

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

обрабатывать множество однотипных и/или логически связанных данных в вычислительной технике. Для добавления, поиска, изменения и удаления данных структура данных предоставляет некоторый набор функций, составляющих её интерфейс.
Абстра́ктный тип да́нных (АТД) — это математическая модель для типов данных, где тип данных определяется поведением (семантикой) с точки зрения пользователя данных, а именно в терминах возможных значений, возможных операций над данными этого типа и поведения этих операций.

Слайд 6

Динамический массив

Слайд 7

Двусвязный и односвязный списки

Слайд 8

Стек и очередь

Слайд 9

Двусторонная очередь (дек)

Слайд 10

Хранение стека, дека, очередь в массиве/списке

Слайд 11

Поиск элемента в массиве
Линейный
Бинарный

Слайд 12

Поддержка минимума в стеке

Слайд 13

Асимптотические обозначения

Слайд 14

Асимптотика простых алгоритмов

Слайд 15

Амортизационный анализ
Средняя амортизационная стоимость операций — величина a, находящаяся по формуле:

t1,t2…tn — время выполнения операций 1,2…n, совершённых над структурой данных.
Метод усреднения
Метод предоплаты
Метод потенциалов

Слайд 16

Метод усреднения
Считаем среднюю амортизационную стоимость по формуле

Слайд 17

Метод предоплаты
Каждой операции над структурой присваивается “стоимость”
При проведении операции от этой

стоимости отнимается фактическое время работы операции, остаток кладётся в “банк” Если стоимости не хватает на проведение операции, то можно взять часть из банка
Тогда амортизационная стоимость операций -- все затраченные деньги/количество операций

Слайд 18

Метод потенциалов

Слайд 19

Представление очереди в виде двух стеков

Слайд 20

Поддержка минимума в очереди

Слайд 21

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

Содержание

Обо мнеКрахмалёв Денис СергеевичАспирант ФПМИ МФТИCV-Engineer в PicsArtkrakhmalev23@gmail.comvk.com/d_krakhmalevtg: @krakhmalyovЧат курсаhttps://t.me/joinchat/R_TklPBYtH8wNWIy

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

Примеры простых алгоритмоввычисление факториала числапроверка числа на простотубыстрое возведение в степень

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