Bonnie and Slide
» » » Основы программирования на С++

Презентация на тему Основы программирования на С++

tapinapura
Рейтинг:
Категория: Информатика
Класс: 10 класс
Дата добавления: 21-01-2019
Содержит:14 слайдов

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

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

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

Слайд 1: Презентация Основы программирования на С++
Слайд 1

Основы программирования на C++

Лекция 5. Начало алгоритмов. Сортировки

Слайд 2: Презентация Основы программирования на С++
Слайд 2

Мем в начале

Слайд 3: Презентация Основы программирования на С++
Слайд 3

Трудоемкость: О-большое, затраты на время и память

Алгоритмы бывают разные, и все они различаются по следующим параметрам: Скорость выполнения – характеризует быстродействие алгоритма. Затраты по памяти – некоторые алгоритмы требуют ещё переменных или массивов Устойчивость - устойчивая сортировка не меняет взаимного расположения равных элементов

Слайд 4: Презентация Основы программирования на С++
Слайд 4

Порядок роста

Порядок роста описывает то, как сложность алгоритма растет с увеличением размера входных данных. Чаще всего он представлен в виде O-нотации (от нем. «Ordnung» — порядок) : O(f(x)), где f(x) — формула, выражающая сложность алгоритма. В формуле может присутствовать переменная n, представляющая размер входных данных.

Слайд 5: Презентация Основы программирования на С++
Слайд 5

Часто встречающиеся порядки

O(1) – константный. Выполняется каждый раз одинаково. Например, алгоритм обмена значений. O(n) – линейный. Прямо зависит от размера входных данных. Например, отображение всех значений в массиве. O(n2) – квадратичный. Часто встречается в алгоритмах сортировок. Лучше не употреблять, так как на большом объеме данных долго будет работать. O(n3) – кубический. Это вообще п*&$@ц кромешный. Задумайтесь перед тем, как использовать алгоритм с таким порядком роста. O(log n) – логарифмический. Самые лучшие сортировки имеют такой порядок роста или O(n*log n). Используется в поиске в двоичном дереве. Крутая вещь :D

Слайд 6: Презентация Основы программирования на С++
Слайд 6

Как измеряем?

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

Слайд 7: Презентация Основы программирования на С++
Слайд 7

Пузырьковая сортировка

Слайд 8: Презентация Основы программирования на С++
Слайд 8

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

Слайд 9: Презентация Основы программирования на С++
Слайд 9

Сортировка вставками

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

Слайд 10: Презентация Основы программирования на С++
Слайд 10

Сортировка выбором

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

Слайд 11: Презентация Основы программирования на С++
Слайд 11

Шейкер-сортировка

Шейкер-сортировка – это разновидность «пузырьковой сортировки», которая работает в две стороны: цикл доходит до правого конца массива и оставляет значение, потом сужает область сортировки в правой части и идёт до левой части. Потом перемещает самый малый элемент в левый конец и, дойдя до него, сужает область сортировки в левой части. Сортировка продолжается до тех пор, пока область не будет исчерпана.

Слайд 12: Презентация Основы программирования на С++
Слайд 12

Быстрая сортировка (quicksort)

Быстрая сортировка — это алгоритм типа «разделяй и властвуй». Он работает, рекурсивно повторяя следующие шаги: Выбрать ключевой индекс и разделить по нему массив на две части. Это можно делать разными способами Переместить все элементы больше ключевого в правую часть массива, а все элементы меньше ключевого — в левую. Теперь ключевой элемент находится в правильной позиции — он больше любого элемента слева и меньше любого элемента справа. Повторяем первые два шага, пока массив не будет полностью отсортирован. Быстрая сортировка реализована в C++ в библиотеке методом std::sort. Псевдокод остается в виде домашнего рассмотрения 

Слайд 13: Презентация Основы программирования на С++
Слайд 13

Задача.

Все вместе разберите один из алгоритмов сортировки. Например, Шейкер-сортировка и сортировка выбором.

Слайд 14: Презентация Основы программирования на С++
Слайд 14

Мем в конце.

Список похожих презентаций