Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.

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

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

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

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

Презентация на тему Лабиринтики и quickunion

Содержание

ПРОСЫПАЕМСЯ!!!Сколько связанных компонент можно получить при выполнении следующей последовательности команд union на наборе из 10 элементов?1-2; 3-4; 5-6; 7-8; 7-9; 2-8; 0-5; 1-9Варианты:
Лабиринтики и quickunion ПРОСЫПАЕМСЯ!!!Сколько связанных компонент можно получить при выполнении следующей последовательности команд union на ПРОСЫПАЕМСЯ!!!Какое максимальное число элементов массива id[] может быть изменено при выполнении одной ПРОСЫПАЕМСЯ!!!Есть структура данных quick-union из 10 элементов и их id[] соответственно равны 0 ПРОСЫПАЕМСЯ!!!Каким может быть максимальное число запросов к массиву во время операции поиска ПРОСЫПАЕМСЯ!!!Дан массив id[] для WQU алгоритмаКакой id[] изменится при выполнении операции Union(3,6)Варианты:ID[0]ID[3]ID[6]ID[8] < см. сл слайд0156273849 ОтветОтвет – id[8]. Так как сравниваем алгоритмы по числу элементов, а не Вопрос для суперигрыКогда открывается новый узел, сколько раз вызывается команда UNION()?Варианты:0,1,2,3 или Анализ алгоритмов ПРОСЫПАЕМСЯ!Дано: N = 1,000,000 (1 миллион)Во сколько быстрее работает алгоритм N*log2N по ПросыпаемсяВы измеряете время работы программы T(N) (сек), как функции размера входных данных Просыпаемся!Сколько обращений к массиву происходит в следующем фрагменте кода? ОтветНе все тройные циклы работают за кубическое время. В данном случае в Просыпаемся!Чему равно максимальное число обращений к массиву в алгоритме бинарного поиска в Просыпаемся!Какая из следующих функций O(N3)? ОтветO() определяет верхнюю границу роста функции, кубичность характерна для них всех. Просыпаемся!Сколько памяти (в байтах) использует взвешенный QuickUnionUF состоящий из массива в N Стеки и очереди Просыпаемся!Какой из следующих входных данных в стек не сможет воспроизвести следующий вывод Просыпаемся!Дана ссылка first, ссылающаяся на 1ый элемент стека (реализация с пом списка ОтветX.next.next != null – проверяет, не является ли следующий за ним элемент Просыпаемся!Предположим, что начиная с пустой структуры, мы производим N push() операций в Сортировка ПРОСЫПАЕМСЯ!Число сравнений для уже отсортированного входного массива алгоритма сортировки с выбором…ЛинейноКвадратично < ПросыпаемсяЧисло сравнений для уже отсортированного массива для метода сортировки с вставкой…ПостоянноЛогарифмичноЛинейно < ПРОСЫПАЕМСЯ!Число сравнений для уже отсортированного массива для метода сортировки Шелла при инкременте Просыпаемся!Каково максимальное число раздач 52 карт? 52! На предыдущем слайде ответ Просыпаемся!Максимальное число вершин на выпуклой оболочке для множества из N точек…ПостоянноЛогарифмичноЛинейно <
Слайды презентации

Слайд 2 ПРОСЫПАЕМСЯ!!!
Сколько связанных компонент можно получить при выполнении следующей

ПРОСЫПАЕМСЯ!!!Сколько связанных компонент можно получить при выполнении следующей последовательности команд union

последовательности команд union на наборе из 10 элементов?
1-2; 3-4;

5-6; 7-8; 7-9; 2-8; 0-5; 1-9
Варианты: решение:
1
2
3 < Прав ответ
4
P.S. Рисуем-соединяем, нумерация не имеет значения, так как ответ всегда один

Слайд 3 ПРОСЫПАЕМСЯ!!!
Какое максимальное число элементов массива id[] может быть

ПРОСЫПАЕМСЯ!!!Какое максимальное число элементов массива id[] может быть изменено при выполнении

изменено при выполнении одной команды union когда мы используем

quick-find, а размер массива N?
Варианты:
1
LgN
N-1 < Прав ответ
N

Слайд 4 ПРОСЫПАЕМСЯ!!!
Есть структура данных quick-union из 10 элементов и

ПРОСЫПАЕМСЯ!!!Есть структура данных quick-union из 10 элементов и их id[] соответственно

их id[] соответственно равны
0 9 6 5 4 2

6 1 0 5
Чему равны корни 3 и 7, соответственно?
Варианты:
3 и 7
4 и 4
6 и 4
6 и 6 <Прав ответ

Слайд 5 ПРОСЫПАЕМСЯ!!!
Каким может быть максимальное число запросов к массиву

ПРОСЫПАЕМСЯ!!!Каким может быть максимальное число запросов к массиву во время операции

во время операции поиска (connected) для алгоритма Quick-union от

числа элементов N в массиве
Варианты:
постоянно
логарифмично
Линейно < пр. отв
Квадратично

Операция connected сравнивает корни 2ух чисел,
возможна ситуация, когда числа находятся в самом низу
необходимо пройти весь массив от начала до конца, чтобы
узнать корни

Слайд 6 ПРОСЫПАЕМСЯ!!!
Дан массив id[] для WQU алгоритма


Какой id[] изменится

ПРОСЫПАЕМСЯ!!!Дан массив id[] для WQU алгоритмаКакой id[] изменится при выполнении операции Union(3,6)Варианты:ID[0]ID[3]ID[6]ID[8] < см. сл слайд0156273849

при выполнении операции Union(3,6)
Варианты:
ID[0]
ID[3]
ID[6]
ID[8] < см. сл слайд
0
1
5
6
2
7
3
8
4
9

Слайд 7 Ответ
Ответ – id[8]. Так как сравниваем алгоритмы по

ОтветОтвет – id[8]. Так как сравниваем алгоритмы по числу элементов, а

числу элементов, а не по высоте.
У дерева с 0

вес ~ 6, a у дерева 8 вес ~ 4. По правилу присоединяем меньшее дерево к большему, сравнивая по весу => меняется id[8]

Слайд 8 Вопрос для суперигры
Когда открывается новый узел, сколько раз

Вопрос для суперигрыКогда открывается новый узел, сколько раз вызывается команда UNION()?Варианты:0,1,2,3

вызывается команда UNION()?
Варианты:
0,1,2,3 или 4 < пр. ответ
1,2,3 или

4
2,3 или 4
4

Сначала проверяем состояние соседей
(открыты или закрыты). С открытыми
Делаем команду union, с закрытыми
– ничего не делаем. Поэтому вызовов
Union может быть от 0 до 4

Слайд 9 Анализ алгоритмов

Анализ алгоритмов

Слайд 10 ПРОСЫПАЕМСЯ!
Дано: N = 1,000,000 (1 миллион)
Во сколько быстрее

ПРОСЫПАЕМСЯ!Дано: N = 1,000,000 (1 миллион)Во сколько быстрее работает алгоритм N*log2N

работает алгоритм N*log2N по сравнению с N2?
в 20
в 1000
в

50,000 < пр отв
в 1,000,000

Слайд 11 Просыпаемся
Вы измеряете время работы программы T(N) (сек), как

ПросыпаемсяВы измеряете время работы программы T(N) (сек), как функции размера входных

функции размера входных данных N. Какая из этих функций

лучше всего описывает время работы.

3.3 * 10-4 * N
N2
5.0 * 10-9 * N2 < Пр отв.
6.25 * 10-9 * N2

Подставляем самый большой N
В каждую из функций и считаем T
Там где он будет точнее, та и функция

Слайд 12 Просыпаемся!
Сколько обращений к массиву происходит в следующем фрагменте

Просыпаемся!Сколько обращений к массиву происходит в следующем фрагменте кода?

кода?


Слайд 13 Ответ
Не все тройные циклы работают за кубическое время.

ОтветНе все тройные циклы работают за кубическое время. В данном случае

В данном случае в цикл с параметром k работает

3lgN раз, вместо N раз, так как каждую итерацию k увеличивается вдвое.
Первые 2 цикла работают по N раз каждый
Итого 3/2 * N * N * lgN

Слайд 14 Просыпаемся!
Чему равно максимальное число обращений к массиву в

Просыпаемся!Чему равно максимальное число обращений к массиву в алгоритме бинарного поиска

алгоритме бинарного поиска в отсортированном массиве длины N

Постоянно
Логарифмично

отв.
Линейно
N log N (Linearithmic)

Каждый раз область поиска
(обрабатываемый массив)
Уменьшается в 2 раза при
нахождении середины.
А это подобно логарифму по основанию 2

Слайд 15 Просыпаемся!
Какая из следующих функций O(N3)?


Просыпаемся!Какая из следующих функций O(N3)?

Слайд 16 Ответ
O() определяет верхнюю границу роста функции, кубичность характерна

ОтветO() определяет верхнюю границу роста функции, кубичность характерна для них всех.

для них всех.

Слайд 17 Просыпаемся!
Сколько памяти (в байтах) использует взвешенный QuickUnionUF состоящий

Просыпаемся!Сколько памяти (в байтах) использует взвешенный QuickUnionUF состоящий из массива в

из массива в N элементов?







Hint: 2 integer arrays size

of N

Вещественное число (int) занимает в памяти 4 байта
Если массив состоит из N веществ чисел,
то занимает 4*N байт памяти
В QuickUnion находится 2 целочисленных массива
значит он занимает ~ 8N байт

Слайд 18 Стеки и очереди

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

Слайд 19 Просыпаемся!
Какой из следующих входных данных в стек не

Просыпаемся!Какой из следующих входных данных в стек не сможет воспроизвести следующий

сможет воспроизвести следующий вывод на экран:
5 4 3 2

1
Варианты:
1 2 3 4 5 - - - - -
1 2 5 - 3 4 - - - -
5 - 1 2 3 -4 - - - < ответ
5 - 4 - 3 - 2-1

Он возвращает: 5 3 4 2 1
Почему? – смотри предыдущие слайды лекции про
стеки

Слайд 20 Просыпаемся!
Дана ссылка first, ссылающаяся на 1ый элемент стека

Просыпаемся!Дана ссылка first, ссылающаяся на 1ый элемент стека (реализация с пом

(реализация с пом списка связанных элементов), в котором минимум

2 элемента, что делает представленный код?



Удаляет первый элемент в стеке
Удаляет второй элемент стека
Удаляет предпоследний элемент стека
Удаляет последний элемент в стеке < пр отв

Слайд 21 Ответ
X.next.next != null – проверяет, не является ли

ОтветX.next.next != null – проверяет, не является ли следующий за ним

следующий за ним элемент последним в стеке. Так как

если a.next == null, то он последний, так как уже ни на что не указывает. Соответственно, как только предпоследний элемент достигается по проходу цикла, условие в while уже не выполняется и происходит выход из цикла. После которого следующий за предпоследним элемент, то есть последний, удаляется (зануляется).

Слайд 22 Просыпаемся!
Предположим, что начиная с пустой структуры, мы производим

Просыпаемся!Предположим, что начиная с пустой структуры, мы производим N push() операций

N push() операций в стеке, реализованном на основе массива

изменяемого размера. Как будет вызываться метод resize()?
Постоянно
Логарифмично < пр. отв
Линейно
Квадратично

Как обычно имеем степень двойки, то есть
Массив каждый раз увеличивается в 2 раза
1 2 4 8 16 32 и тд пока не дойдем до N
Типа.. Массив растет от 1 до N каждый раз
увеличиваясь в 2 раза

Слайд 23 Сортировка

Сортировка

Слайд 24 ПРОСЫПАЕМСЯ!
Число сравнений для уже отсортированного входного массива алгоритма

ПРОСЫПАЕМСЯ!Число сравнений для уже отсортированного входного массива алгоритма сортировки с выбором…ЛинейноКвадратично

сортировки с выбором…
Линейно
Квадратично < ответ на предыдущем слайде (сортировка

#22)
Логарифмично
Экспоненциально

Слайд 25 Просыпаемся
Число сравнений для уже отсортированного массива для метода

ПросыпаемсяЧисло сравнений для уже отсортированного массива для метода сортировки с вставкой…ПостоянноЛогарифмичноЛинейно

сортировки с вставкой…
Постоянно
Логарифмично
Линейно < просто сравниваем соседствующие элемены, левый

эл-т всегда будет меньше правого, условие всегда будет выполняться, следовательно пройдет всего N сравнений
Квадратично

Слайд 26 ПРОСЫПАЕМСЯ!
Число сравнений для уже отсортированного массива для метода

ПРОСЫПАЕМСЯ!Число сравнений для уже отсортированного массива для метода сортировки Шелла при

сортировки Шелла при инкременте 3x+1…
Постоянно
Логарифмично
Линейно
N*logN < на слайде 48

ответ

Слайд 27 Просыпаемся!
Каково максимальное число раздач 52 карт?
52! На

Просыпаемся!Каково максимальное число раздач 52 карт? 52! На предыдущем слайде ответ

предыдущем слайде ответ

  • Имя файла: labirintiki-i-quickunion.pptx
  • Количество просмотров: 68
  • Количество скачиваний: 0
- Предыдущая Экологические проблемы мира
Следующая - День рождения

Похожие презентации

Умножение обыкновенных дробей Умножение обыкновенных дробей 77
Круг. Оркужность Круг. Оркужность 92
НОД по математическому развитию в старшей группе компенсирующей направленности (для детей с нарушением зрения) план-конспект занятия по математике (старшая группа) НОД по математическому развитию в старшей группе компенсирующей направленности (для детей с нарушением зрения) план-конспект занятия по математике (старшая группа) 170
Исследование функций на монотоноость Исследование функций на монотоноость 78
Презентация по математике на тему Задача(1 класс) Презентация по математике на тему Задача(1 класс) 90
Деление с остатком Деление с остатком 118
Презентация Сложение и вычитание чисел в пределах 10 презентация к уроку по математике (1 класс) по теме Презентация Сложение и вычитание чисел в пределах 10 презентация к уроку по математике (1 класс) по теме 137
Презентация к технологической карте по математике Умножение многозначного числа на однозначное презентация к уроку по математике Презентация к технологической карте по математике Умножение многозначного числа на однозначное презентация к уроку по математике 86
Свойства функций Свойства функций 87
Презентация к УИК Лист Мёбиуса Презентация к УИК Лист Мёбиуса 100
Подготовка к ОГЭ по математике Подготовка к ОГЭ по математике 91
презентация к уроку математики 1 класс. Тема Вычитание числа 3 презентация к уроку по математике (1 класс) презентация к уроку математики 1 класс. Тема Вычитание числа 3 презентация к уроку по математике (1 класс) 32
Проект электронного портфолио учащегося по предмету Математика Проект электронного портфолио учащегося по предмету Математика 83
Презентация к уроку математики Прием вычислений вида 30 – 7. 2 класс. презентация к уроку по математике (2 класс) Презентация к уроку математики Прием вычислений вида 30 – 7. 2 класс. презентация к уроку по математике (2 класс) 87
Таблица презентация к уроку по математике (2 класс) по теме Таблица презентация к уроку по математике (2 класс) по теме 99
Математика пәні бойынша Математикалық сайыс тақырыбына презентация (6 сынып) Математика пәні бойынша Математикалық сайыс тақырыбына презентация (6 сынып) 141
Урок 79. Длина. Решение задач Урок 79. Длина. Решение задач 78
Путешествие в страну Фигурляндию план-конспект занятия по математике (средняя группа) Путешествие в страну Фигурляндию план-конспект занятия по математике (средняя группа) 92
Презентация по математике на тему Умножение и деление на однозначное число (6 класс) Презентация по математике на тему Умножение и деление на однозначное число (6 класс) 101
Основное свойство дроби 5 класс Основное свойство дроби 5 класс 84
Презентация для занятия на основе ИКТ Путешествие к вершине горы презентация к уроку по математике (подготовительная группа) Презентация для занятия на основе ИКТ Путешествие к вершине горы презентация к уроку по математике (подготовительная группа) 92
Радиус вписанной и описанной окружности Радиус вписанной и описанной окружности 92
Путешествие в цирк Путешествие в цирк 237
Статья и презентация Активные методы обучения на уроках математики при решении задач в условиях реализации ФГОС НОО. презентация к уроку Статья и презентация Активные методы обучения на уроках математики при решении задач в условиях реализации ФГОС НОО. презентация к уроку 116
Сумма углов треугольника Сумма углов треугольника 108
Использование инструментов Панели рисования на уроках математики Использование инструментов Панели рисования на уроках математики 72
Презентация по математике Числовые выражения Презентация по математике Числовые выражения 108
Презентация по математике Задачи на движение Презентация по математике Задачи на движение 100
Конспект урока + презентация по математике по теме: Деление меньшего числа на большее, 3 класс план-конспект урока по математике (3 класс) Конспект урока + презентация по математике по теме: Деление меньшего числа на большее, 3 класс план-конспект урока по математике (3 класс) 145
Презентация по математике на тему Уравнения (5 класс) Презентация по математике на тему Уравнения (5 класс) 161