Обсуждение:Биномиальная куча — различия между версиями
Rybak (обсуждение | вклад) |
Rybak (обсуждение | вклад) м |
||
| (не показано 9 промежуточных версий этого же участника) | |||
| Строка 1: | Строка 1: | ||
== Замечания == | == Замечания == | ||
| − | {{tick}} | + | {{tick}} Сделай у всех рисунков подписи, как у первого в конспекте. |
| − | {{tick}} | + | |
| − | + | {{tick}} Почему пример merge горизонтальный, а extractMin - вертикальный? | |
| − | + | ||
| − | + | {{tick}} Рисунки, кажется, сделаны в WYSIWYG-редакторе (с tikZ pdf или METAPOST не было бы таких проблем): | |
| − | + | :{{tick}} стрелки не отцентрированы | |
| − | + | :{{tick}} впрочем, как и наложенные красные окружности | |
| − | + | :{{tick}} и цифры внутри окружностей | |
| − | + | :{{tick}} те отрезки, которые должны быть вертикальными, не вертикальны. | |
| − | + | ||
| − | + | {{tick}} на рисунке | |
| − | + | [[Файл:BinHeapExampleNew31.png|100px|Примеp извлечения минимума]] все центрировать или сделать горизонтальную большую стрелку | |
| − | {{tick}} | + | : {{tick}} и убрать точку слева от двойки в оранжевом прямоугольнике |
| − | {{tick}} | + | |
| + | {{tick}} на рисунке [[Файл:helpBinaryHeapBoris.png|100px|Пример слияние двух деревьев одного порядка]] фигурные скобки почему-то наклонены влево | ||
| + | : {{tick}} фигурная скобка справа, наверное, должна выделять все поддерево нуля | ||
| + | : {{tick}} Разнести левую и правую части рисунка, так чтобы они были слева и справа от стрелки. | ||
| + | |||
| + | |||
| + | == Архив == | ||
| + | {{tick | ticked = 1}} "то переход верный, то свойство доказано." исправить во всех утверждениях. Это касается и "То свойство доказано". | ||
| + | |||
| + | {{tick | ticked = 1}} На рисунке [[Image:BinHeapExample2_5.png|100px]] точка | ||
| + | |||
| + | {{tick | ticked = 1}} псевдокод не соответсвует требованиям | ||
---- | ---- | ||
| + | |||
{{tick | ticked = 1}} ", в случае его минимальности относительно его родителя," {{---}} плохая формулировка | {{tick | ticked = 1}} ", в случае его минимальности относительно его родителя," {{---}} плохая формулировка | ||
| + | |||
{{tick | ticked = 1}} "То для <tex>i</tex> уровня" {{---}} в таких местах нужно добавлять окончание: "То для <tex>i</tex>-го уровня" '''UPD''' не тире, а дефис ([http://www.artlebedev.ru/kovodstvo/sections/97/ рекомендуется к прочтению]) | {{tick | ticked = 1}} "То для <tex>i</tex> уровня" {{---}} в таких местах нужно добавлять окончание: "То для <tex>i</tex>-го уровня" '''UPD''' не тире, а дефис ([http://www.artlebedev.ru/kovodstvo/sections/97/ рекомендуется к прочтению]) | ||
| + | |||
{{tick | ticked = 1}} Исправить последнее утверждение. | {{tick | ticked = 1}} Исправить последнее утверждение. | ||
| + | |||
{{tick | ticked = 1}} "То имеем асимптотику " - плохая формулировка | {{tick | ticked = 1}} "То имеем асимптотику " - плохая формулировка | ||
| + | |||
{{tick | ticked = 1}} В описании функции insert предложение несогласованно. | {{tick | ticked = 1}} В описании функции insert предложение несогласованно. | ||
| + | |||
{{tick | ticked = 1}} Добавить категории. '''UPD''' Требования - Викификация - пункт 8 | {{tick | ticked = 1}} Добавить категории. '''UPD''' Требования - Викификация - пункт 8 | ||
| + | |||
{{tick | ticked = 1}} Во всем конспекте время работы называется по-разному: "асимптотические оценки ", "общая асимптотика " - сделать однообразно. Не забывайте, что буквы O, o, Омега как раз означают, что время асимптотическое. | {{tick | ticked = 1}} Во всем конспекте время работы называется по-разному: "асимптотические оценки ", "общая асимптотика " - сделать однообразно. Не забывайте, что буквы O, o, Омега как раз означают, что время асимптотическое. | ||
| + | |||
{{tick | ticked = 1}} Свойства оформить в виде утверждения. '''UPD''' Требования - Викификация - пункт 3 | {{tick | ticked = 1}} Свойства оформить в виде утверждения. '''UPD''' Требования - Викификация - пункт 3 | ||
| + | |||
{{tick | ticked = 1}} "Удаление ключа сводится к двум предыдущим операциям: " - написать к каким именно, убрать слова "двум предыдущим". | {{tick | ticked = 1}} "Удаление ключа сводится к двум предыдущим операциям: " - написать к каким именно, убрать слова "двум предыдущим". | ||
| + | |||
{{tick | ticked = 1}} Исправить рисунок в примере к decreaseKey. | {{tick | ticked = 1}} Исправить рисунок в примере к decreaseKey. | ||
| + | |||
{{tick | ticked = 1}} Доказать, что delete работает за логарифм. | {{tick | ticked = 1}} Доказать, что delete работает за логарифм. | ||
| + | |||
{{tick | ticked = 1}} Исправить названия процедур. | {{tick | ticked = 1}} Исправить названия процедур. | ||
| + | |||
{{tick | ticked = 1}} Перерисовать все изображения. | {{tick | ticked = 1}} Перерисовать все изображения. | ||
| + | |||
{{tick | ticked = 1}} Переписать псевдокод по [[Обсуждение:Дискретная математика и алгоритмы#Псевдокод | guideline]]. | {{tick | ticked = 1}} Переписать псевдокод по [[Обсуждение:Дискретная математика и алгоритмы#Псевдокод | guideline]]. | ||
| + | |||
{{tick | ticked = 1}} Исправить раздел "Источники". '''UPD''': лишняя линия + Требования - Викификация - пункт 9 (смотрите [[Алгоритм Хаффмана]] и [[Сокращенная и минимальная ДНФ]]) | {{tick | ticked = 1}} Исправить раздел "Источники". '''UPD''': лишняя линия + Требования - Викификация - пункт 9 (смотрите [[Алгоритм Хаффмана]] и [[Сокращенная и минимальная ДНФ]]) | ||
| + | |||
{{tick | ticked = 1}} <s>Определение Биноминального дерева сделать '''не на всю ширину''' страницы (см. [[Шаблон: Определение]]).</s> - поправил сам, теперь с версткой в этом месте все ОК. | {{tick | ticked = 1}} <s>Определение Биноминального дерева сделать '''не на всю ширину''' страницы (см. [[Шаблон: Определение]]).</s> - поправил сам, теперь с версткой в этом месте все ОК. | ||
| + | |||
{{tick | ticked = 1}} Картинку перенести вправо. Оформить как, например, в конспекте [[Дерево Уоллеса]] (с подписью). | {{tick | ticked = 1}} Картинку перенести вправо. Оформить как, например, в конспекте [[Дерево Уоллеса]] (с подписью). | ||
| + | |||
{{tick | ticked = 1}} "Пример биномиального дерева для k = 0, 2, 3." -- "Пример биномиальных деревьев B_0, B_2 и B_3" | {{tick | ticked = 1}} "Пример биномиального дерева для k = 0, 2, 3." -- "Пример биномиальных деревьев B_0, B_2 и B_3" | ||
| + | |||
{{tick | ticked = 1}} Свойства биномиальных деревьев надо доказать. | {{tick | ticked = 1}} Свойства биномиальных деревьев надо доказать. | ||
| + | |||
{{tick | ticked = 1}} '''Все переменные занести в TeX (перечитайте Требования - TeX)''' | {{tick | ticked = 1}} '''Все переменные занести в TeX (перечитайте Требования - TeX)''' | ||
| + | |||
{{tick | ticked = 1}} Разбить конспект на части, используя заголовки разных уровней. | {{tick | ticked = 1}} Разбить конспект на части, используя заголовки разных уровней. | ||
| + | |||
{{tick | ticked = 1}} Убрать лишнюю линию после заголовка "Операции над биномиальными пирамидами" | {{tick | ticked = 1}} Убрать лишнюю линию после заголовка "Операции над биномиальными пирамидами" | ||
| + | |||
{{tick | ticked = 1}} Из "Определение: Биномиальная пирамида" убрать символ 'H'. | {{tick | ticked = 1}} Из "Определение: Биномиальная пирамида" убрать символ 'H'. | ||
| + | |||
{{tick | ticked = 1}} После " следующим свойствам биномиальных пирамид." должна быть не точка, а двоеточие | {{tick | ticked = 1}} После " следующим свойствам биномиальных пирамид." должна быть не точка, а двоеточие | ||
| + | |||
{{tick | ticked = 1}} В предложении " следующим свойствам биномиальных пирамид." убрать "биномиальных пирамид" | {{tick | ticked = 1}} В предложении " следующим свойствам биномиальных пирамид." убрать "биномиальных пирамид" | ||
| + | |||
{{tick | ticked = 1}} makeHeap -- убрать, не несет смысла | {{tick | ticked = 1}} makeHeap -- убрать, не несет смысла | ||
| + | |||
{{tick | ticked = 1}} В функции delete минус бесконечность | {{tick | ticked = 1}} В функции delete минус бесконечность | ||
| + | |||
{{tick | ticked = 1}} head[H] - head это не массив. Оставьте просто head, без скобок | {{tick | ticked = 1}} head[H] - head это не массив. Оставьте просто head, без скобок | ||
| + | |||
{{tick | ticked = 1}} '''Требования - Викификация - пункт 5''' | {{tick | ticked = 1}} '''Требования - Викификация - пункт 5''' | ||
| + | |||
{{tick | ticked = 1}} "Асимптотика этой операции получается из того" - ужасное предложение, переписать. Асимптотика ниоткуда не получается. | {{tick | ticked = 1}} "Асимптотика этой операции получается из того" - ужасное предложение, переписать. Асимптотика ниоткуда не получается. | ||
| + | |||
{{tick | ticked = 1}} '''Сокращать слова нельзя.''' | {{tick | ticked = 1}} '''Сокращать слова нельзя.''' | ||
| + | |||
{{tick | ticked = 1}} "В силу того, что с увеличением порядка дерева на количество узлов увеличивается вдвое, а изначально дерево имеет узел, то при любом , дерево порядка имеет узлов." - плохое предложение. Нужно написать "Так как в дереве порядка k+1 вдвое больше узлов, чем в дереве порядка k, а в дереве нулевого порядка 1 = 2^0 узел, то дерево порядка k имеет 2^k узлов" '''UDP''' аналогичные предложения исправить в других свойствах. | {{tick | ticked = 1}} "В силу того, что с увеличением порядка дерева на количество узлов увеличивается вдвое, а изначально дерево имеет узел, то при любом , дерево порядка имеет узлов." - плохое предложение. Нужно написать "Так как в дереве порядка k+1 вдвое больше узлов, чем в дереве порядка k, а в дереве нулевого порядка 1 = 2^0 узел, то дерево порядка k имеет 2^k узлов" '''UDP''' аналогичные предложения исправить в других свойствах. | ||
| + | |||
{{tick | ticked = 1}} <s>Найти место и добавить туда ссылку на конспект про кучу.</s> Переставить ссылку. | {{tick | ticked = 1}} <s>Найти место и добавить туда ссылку на конспект про кучу.</s> Переставить ссылку. | ||
| + | |||
| + | ---- | ||
| + | <s> | ||
| + | {{tick}} Оценки времени работы. ''В Кормене даны оценки для'' '''''наихудшего''''' ''случая.''</s> | ||
| + | |||
| + | {{tick | ticked = 1}} Перерисовать картинку для merge: | ||
| + | # Нужно разделить два случая и подписи на стрелочках перенести в подписи к изображениям. | ||
| + | #* В принципе достаточно одного случая, а тексте написать, что иначе подвешиваем их наоборот. | ||
| + | # Несогласованны обозначения: вместо key[x] нужно x.key | ||
| + | # Плохо, когда две одинаковые буквы обозначают разные вещи : x и X. В частности, как и в пункте 2, для степени есть обозначения x.degree | ||
| + | # x лучше переименовать в current | ||
| + | # сказать о том, что степени узлов равны можно так : b.degree = c.degree | ||
| + | #* Обозначение Y не нужно | ||
| + | # x.next и x.prev можно убрать -- и так понятно, что это список | ||
| + | #* офф-топик: от предыдущих версий осталась черточка после prev, а точка (между x и prev/next) слишком выделяется | ||
| + | # то, что выделено фигурными скобками можно будет обозначить так <tex>c'.degree = c.degree + 1</tex> | ||
| + | |||
| + | {{tick | ticked = 1}} Словесное описание функции decreaseKey '''UPD''': не нужно описание писать в будущем времени. '''UPD2''': теперь еще хуже | ||
| + | * Плохо начиная со слов "... то есть алгоритм состоит в том, что если ...". Можно убрать все после слова "всплывает" до "Процедура выполняется за время". И добавить, что вершина всплывает, как в обычной куче. | ||
| + | |||
| + | {{tick | ticked = 1}} В decreaseKey глубина вершины в общем случае - O(log n). Нужно либо указать, что это худший случай, либо исправить. | ||
| + | |||
| + | {{tick | ticked = 1}} Путаница next prev sibling. Список корней -- односвязный. В Кормене обозначение для полей в узле это массивы: x.sibling = sibling[x], а next-x - это название переменной. Поэтому нужно убрать упоминания x.next и x.prev, оставив только x.sibling. | ||
Текущая версия на 22:16, 10 июня 2012
Замечания
☐ Сделай у всех рисунков подписи, как у первого в конспекте.
☐ Почему пример merge горизонтальный, а extractMin - вертикальный?
☐ Рисунки, кажется, сделаны в WYSIWYG-редакторе (с tikZ pdf или METAPOST не было бы таких проблем):
- ☐ стрелки не отцентрированы
- ☐ впрочем, как и наложенные красные окружности
- ☐ и цифры внутри окружностей
- ☐ те отрезки, которые должны быть вертикальными, не вертикальны.
☐ на рисунке
все центрировать или сделать горизонтальную большую стрелку
- ☐ и убрать точку слева от двойки в оранжевом прямоугольнике
☐ на рисунке 
фигурные скобки почему-то наклонены влево
- ☐ фигурная скобка справа, наверное, должна выделять все поддерево нуля
- ☐ Разнести левую и правую части рисунка, так чтобы они были слева и справа от стрелки.
Архив
☑ "то переход верный, то свойство доказано." исправить во всех утверждениях. Это касается и "То свойство доказано".
☑ На рисунке 
точка
☑ псевдокод не соответсвует требованиям
☑ ", в случае его минимальности относительно его родителя," — плохая формулировка
☑ "То для уровня" — в таких местах нужно добавлять окончание: "То для -го уровня" UPD не тире, а дефис (рекомендуется к прочтению)
☑ Исправить последнее утверждение.
☑ "То имеем асимптотику " - плохая формулировка
☑ В описании функции insert предложение несогласованно.
☑ Добавить категории. UPD Требования - Викификация - пункт 8
☑ Во всем конспекте время работы называется по-разному: "асимптотические оценки ", "общая асимптотика " - сделать однообразно. Не забывайте, что буквы O, o, Омега как раз означают, что время асимптотическое.
☑ Свойства оформить в виде утверждения. UPD Требования - Викификация - пункт 3
☑ "Удаление ключа сводится к двум предыдущим операциям: " - написать к каким именно, убрать слова "двум предыдущим".
☑ Исправить рисунок в примере к decreaseKey.
☑ Доказать, что delete работает за логарифм.
☑ Исправить названия процедур.
☑ Перерисовать все изображения.
☑ Переписать псевдокод по guideline.
☑ Исправить раздел "Источники". UPD: лишняя линия + Требования - Викификация - пункт 9 (смотрите Алгоритм Хаффмана и Сокращенная и минимальная ДНФ)
☑ Определение Биноминального дерева сделать не на всю ширину страницы (см. Шаблон: Определение). - поправил сам, теперь с версткой в этом месте все ОК.
☑ Картинку перенести вправо. Оформить как, например, в конспекте Дерево Уоллеса (с подписью).
☑ "Пример биномиального дерева для k = 0, 2, 3." -- "Пример биномиальных деревьев B_0, B_2 и B_3"
☑ Свойства биномиальных деревьев надо доказать.
☑ Все переменные занести в TeX (перечитайте Требования - TeX)
☑ Разбить конспект на части, используя заголовки разных уровней.
☑ Убрать лишнюю линию после заголовка "Операции над биномиальными пирамидами"
☑ Из "Определение: Биномиальная пирамида" убрать символ 'H'.
☑ После " следующим свойствам биномиальных пирамид." должна быть не точка, а двоеточие
☑ В предложении " следующим свойствам биномиальных пирамид." убрать "биномиальных пирамид"
☑ makeHeap -- убрать, не несет смысла
☑ В функции delete минус бесконечность
☑ head[H] - head это не массив. Оставьте просто head, без скобок
☑ Требования - Викификация - пункт 5
☑ "Асимптотика этой операции получается из того" - ужасное предложение, переписать. Асимптотика ниоткуда не получается.
☑ Сокращать слова нельзя.
☑ "В силу того, что с увеличением порядка дерева на количество узлов увеличивается вдвое, а изначально дерево имеет узел, то при любом , дерево порядка имеет узлов." - плохое предложение. Нужно написать "Так как в дереве порядка k+1 вдвое больше узлов, чем в дереве порядка k, а в дереве нулевого порядка 1 = 2^0 узел, то дерево порядка k имеет 2^k узлов" UDP аналогичные предложения исправить в других свойствах.
☑ Найти место и добавить туда ссылку на конспект про кучу. Переставить ссылку.
☐ Оценки времени работы. В Кормене даны оценки для наихудшего случая.
☑ Перерисовать картинку для merge:
- Нужно разделить два случая и подписи на стрелочках перенести в подписи к изображениям.
- В принципе достаточно одного случая, а тексте написать, что иначе подвешиваем их наоборот.
- Несогласованны обозначения: вместо key[x] нужно x.key
- Плохо, когда две одинаковые буквы обозначают разные вещи : x и X. В частности, как и в пункте 2, для степени есть обозначения x.degree
- x лучше переименовать в current
- сказать о том, что степени узлов равны можно так : b.degree = c.degree
- Обозначение Y не нужно
- x.next и x.prev можно убрать -- и так понятно, что это список
- офф-топик: от предыдущих версий осталась черточка после prev, а точка (между x и prev/next) слишком выделяется
- то, что выделено фигурными скобками можно будет обозначить так
☑ Словесное описание функции decreaseKey UPD: не нужно описание писать в будущем времени. UPD2: теперь еще хуже
- Плохо начиная со слов "... то есть алгоритм состоит в том, что если ...". Можно убрать все после слова "всплывает" до "Процедура выполняется за время". И добавить, что вершина всплывает, как в обычной куче.
☑ В decreaseKey глубина вершины в общем случае - O(log n). Нужно либо указать, что это худший случай, либо исправить.
☑ Путаница next prev sibling. Список корней -- односвязный. В Кормене обозначение для полей в узле это массивы: x.sibling = sibling[x], а next-x - это название переменной. Поэтому нужно убрать упоминания x.next и x.prev, оставив только x.sibling.
