Что такое 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
  • Количество просмотров: 90
  • Количество скачиваний: 0
- Предыдущая Экологические проблемы мира
Следующая - День рождения

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

Работа с многочленом Работа с многочленом 106
Презентация Цветик-семицветик презентация к занятию по математике (старшая группа) Презентация Цветик-семицветик презентация к занятию по математике (старшая группа) 63
Мастер-класс Работа с одаренными детьми в начальной школе при изучении математики учебно-методический материал по математике по теме Задача 3  6 спичек и 4 треугольникаЗадача 4  Чётырёхугольник, линия и 4 треугольника Мастер-класс Работа с одаренными детьми в начальной школе при изучении математики учебно-методический материал по математике по теме Задача 3  6 спичек и 4 треугольникаЗадача 4  Чётырёхугольник, линия и 4 треугольника 149
m urok70 m urok70 129
Презентация по математике на тему Задача. Условие и вопрос (1 класс) Презентация по математике на тему Задача. Условие и вопрос (1 класс) 86
Урок по теме: Что такое алгоритм Урок по теме: Что такое алгоритм 127
Простейшие вероятностные задачи Простейшие вероятностные задачи 132
Интервальное оценивание данных Интервальное оценивание данных 123
Метематика, один из важнейших предметов в мире Метематика, один из важнейших предметов в мире 92
Презентация по математике на темудроби Презентация по математике на темудроби 101
Числовой луч – твой помощник! Мозаика заданий. Числовой луч – твой помощник! Мозаика заданий. 106
Решаем задачи Решаем задачи 93
Математика 1 класс Число 6 - Цифра 6 Математика 1 класс Число 6 - Цифра 6 147
Тренажер по умножению Тренажер по умножению 101
Симметрия в животном мире Симметрия в животном мире 102
Презентация по математике на тему Деление обыкновенных дробей (6 класс) Презентация по математике на тему Деление обыкновенных дробей (6 класс) 118
Тренажёр - раскраска Бабочка тренажёр по математике (2 класс) Тренажёр - раскраска Бабочка тренажёр по математике (2 класс) 128
Презентация математический диктант №14 5 класс Презентация математический диктант №14 5 класс 109
Учебно-исследовательские технологии обучения математике Учебно-исследовательские технологии обучения математике 160
Расчет неопределенности измерения Расчет неопределенности измерения 144
Задания по математике для подготовки детей к школе презентация урока для интерактивной доски по математике (подготовительная группа) Задания по математике для подготовки детей к школе презентация урока для интерактивной доски по математике (подготовительная группа) 143
8 raund 8 raund 131
Дидактические игры по ФЭМП картотека по математике (средняя, старшая, подготовительная группа) Дидактические игры по ФЭМП картотека по математике (средняя, старшая, подготовительная группа) 179
Целое и части. Состав чисел. Целое и части. Состав чисел. 115
Индексный метод Индексный метод 146
Урок – путешествие по математике Сложение и вычитание в пределах 100. Закрепление.(2 класс) Урок – путешествие по математике Сложение и вычитание в пределах 100. Закрепление.(2 класс) 127
Двоичная система счисления Двоичная система счисления 112
Числовые и буквенные выражения Числовые и буквенные выражения 128
Презентация Отработка вычислительных навыков 4 класс презентация к уроку по математике (4 класс) по теме Презентация Отработка вычислительных навыков 4 класс презентация к уроку по математике (4 класс) по теме 135
Игра по математике Что?Где?Когда? Игра по математике Что?Где?Когда? 159