Обсуждение:Биномиальная куча — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
 
(не показано 13 промежуточных версий этого же участника)
Строка 1: Строка 1:
 
== Замечания ==
 
== Замечания ==
  
{{tick}} В разделе "Операции над биномиальными кучами" в таблице и в описаниях указаны разные оценки для времени работы. '''UPD''' если возможно, нужно сделать более точные оценки.
+
{{tick}} Сделай у всех рисунков подписи, как у первого в конспекте.
{{tick}} Описание функции merge '''UPD''': перерисовать картинку.
 
{{tick}} Словесное описание функции extractMin '''UPD''': время работы не правильное
 
{{tick}} Словесное описание функции decreaseKey '''UPD''': не нужно описание писать в будущем времени.
 
  
{{tick}} "То для <tex>i</tex> уровня" {{---}} в таких местах нужно добавлять окончание: "То для <tex>i</tex>-го уровня" '''UPD''' не тире, а дефис ([http://www.artlebedev.ru/kovodstvo/sections/97/ рекомендуется к прочтению])
+
{{tick}} Почему пример merge горизонтальный, а extractMin - вертикальный?
{{tick}} Исправить последнее утверждение.
+
 
 +
{{tick}} Рисунки, кажется, сделаны в WYSIWYG-редакторе (с tikZ pdf или METAPOST не было бы таких проблем):  
 +
:{{tick}} стрелки не отцентрированы
 +
:{{tick}} впрочем, как и наложенные красные окружности
 +
:{{tick}} и цифры внутри окружностей
 +
:{{tick}} те отрезки, которые должны быть вертикальными, не вертикальны.
 +
 
 +
{{tick}} на рисунке
 +
[[Файл:BinHeapExampleNew31.png|100px|Примеp извлечения минимума]] все центрировать или сделать горизонтальную большую стрелку
 +
: {{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}} "То для <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}} В описании функции 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 не было бы таких проблем):

стрелки не отцентрированы
впрочем, как и наложенные красные окружности
и цифры внутри окружностей
те отрезки, которые должны быть вертикальными, не вертикальны.

на рисунке Примеp извлечения минимума все центрировать или сделать горизонтальную большую стрелку

и убрать точку слева от двойки в оранжевом прямоугольнике

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

фигурная скобка справа, наверное, должна выделять все поддерево нуля
Разнести левую и правую части рисунка, так чтобы они были слева и справа от стрелки.


Архив

"то переход верный, то свойство доказано." исправить во всех утверждениях. Это касается и "То свойство доказано".

На рисунке BinHeapExample2 5.png точка

псевдокод не соответсвует требованиям



", в случае его минимальности относительно его родителя," — плохая формулировка

"То для [math]i[/math] уровня" — в таких местах нужно добавлять окончание: "То для [math]i[/math]-го уровня" 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:

  1. Нужно разделить два случая и подписи на стрелочках перенести в подписи к изображениям.
    • В принципе достаточно одного случая, а тексте написать, что иначе подвешиваем их наоборот.
  2. Несогласованны обозначения: вместо key[x] нужно x.key
  3. Плохо, когда две одинаковые буквы обозначают разные вещи : x и X. В частности, как и в пункте 2, для степени есть обозначения x.degree
  4. x лучше переименовать в current
  5. сказать о том, что степени узлов равны можно так : b.degree = c.degree
    • Обозначение Y не нужно
  6. x.next и x.prev можно убрать -- и так понятно, что это список
    • офф-топик: от предыдущих версий осталась черточка после prev, а точка (между x и prev/next) слишком выделяется
  7. то, что выделено фигурными скобками можно будет обозначить так [math]c'.degree = c.degree + 1[/math]

Словесное описание функции decreaseKey UPD: не нужно описание писать в будущем времени. UPD2: теперь еще хуже

  • Плохо начиная со слов "... то есть алгоритм состоит в том, что если ...". Можно убрать все после слова "всплывает" до "Процедура выполняется за время". И добавить, что вершина всплывает, как в обычной куче.

В decreaseKey глубина вершины в общем случае - O(log n). Нужно либо указать, что это худший случай, либо исправить.

Путаница next prev sibling. Список корней -- односвязный. В Кормене обозначение для полей в узле это массивы: x.sibling = sibling[x], а next-x - это название переменной. Поэтому нужно убрать упоминания x.next и x.prev, оставив только x.sibling.