SICP по-русски

Просмотрел сегодня первую лекцию (1-а) с полученных DVD. Сделал для себя следующие заметки.

Первую лекцию читал Хэл Абельсон. Оказывается, он левша.
Очень понравилось сравнение computer science и геометрии. Действительно, именно формализация способа мышления делает обе области знания тем, что они есть.
Очень хорошее объяснение отличий между декларативными и императивными знаниями. Просто, но важно.
Отличное описание абстракции черного ящика. Очень […]

Я предлагаю реализацию encode-symbol, приведенную ниже. Она заключается в том, что для символа мы начиная от корня просматриваем вершины дерева кодирования и ищем символ в левом и правом поддеревьях каждой вершины. Если символ найден в левом поддереве, мы дописываем в его код 0, если в правом - 1. Остальная часть кода возвращается вызовом той же […]

Дерево кодирования из примера изображено на рисунке ниже:

При декодировании последовательности
0 1 1 0 0 1 0 1 0 1 1 1 0
будем двигаться в соответствии с описанными в параграфе, предшествующем упражнению, правилами от корня к листам в зависимости от значений входных битов и, достигнув листа, выводить символ в нем.
Сначала, пройдем по левой ветке (0) и попадем […]

Вчера этому ресурсу незаметно (я чуть было не пропустил такое знаменательное событие) стукнуло полгода. Первая заметка датирована 12 августа 2007 года.
На текущий момент статистика следующая:

Написано 137 заметок (включая эту). К заметкам создано 57 комментариев.
Решено 112 упражнений (это меньше упражнения в день в среднем, но в последний месяц я сильно улучшил статистику и буду стараться поддерживать […]

Просто возьмем процедуру element-of-set? для множеств, представленных бинарными деревьями, и модернизируем ее для работы с записями с числовым ключом. Также учтем, что lookup не только проверяет присутствие записи с заданным ключом, но и возвращает саму эту запись в случае успешного поиска.
Получим следующую процедуру:
(define (lookup given-key set-of-records)
  (cond ((null? set-of-records) false)
        ((= given-key (key (entry set-of-records)))
         […]

Процедуры tree->list (я не буду использовать индексы 1 и 2) и list->tree дают нам возможность свободно преобразовывать множества, представленные упорядоченными списками и (сбалансированными) бинарными деревьями, из одного представления в другое за линейное (Θ(n)) число операций.
Это позволяет нам реализовать операции над множествами, представленными бинарными деревьями, через уже реализованные операции над множествами, представленными упорядоченными списками. Для этого […]

Алгоритм работы процедуры partial-tree может быть очень кратко описан следующим образом.
Мы выбираем в списке центральный элемент и разбиваем список на часть до него не включительно (левая часть), сам элемент и часть после него опять не включительно (правая часть). После этого мы строим дерево, корнем которого является выбранный центральный элемент, левое поддерево строится аналогичным образом по […]

Процедуры tree->list-1 и tree->list-2 создают отсортированный список элементов в дереве (фактически, они производят обход дерева в глубину слева направо и собирают значения entry каждого узла дерева в список). Таким образом они делают одно и то же. Разница между ними в том, что tree->list-1 записана в форме, порождающей рекурсивный процесс, а tree->list-2 порождает итеративный процесс.
Поскольку все деревья на […]

Идея реализации union-set за линейный проход абсолютно аналогична идее, положенной в основу intersection-set из книги. Мы движемся параллельно по двум спискам и сравниваем их текущие первые элементы. Если они равны, мы решаем задачу для хвостов списков и приписываем любой из двух равных головных элементов в начало. Если же один из элементов меньше другого, то его […]

Для того, чтобы получить уменьшение вдвое числа шагов, необходимого для добавления элемента во множество, представленное в виде неупорядоченного списка, нам недостаточно просто определить, есть ли элемент во множестве с помощью element-of-set?, а затем добавить его подобно тому, как мы делали для множеств, представленных неупорядоченными списками. В этом случае поиск и вставка потребуют в среднем по […]