Category: SICP

Впечатления о видео лекциях. Лекция 1-А.

15 February, 2008 (23:51) | Видео | 2 comments

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

Решение упражнения 2.68 из SICP

15 February, 2008 (21:24) | Решения упражнений | 3 comments

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

Решение упражнения 2.67 из SICP

15 February, 2008 (20:54) | Решения упражнений | No comments

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

Полгода в эфире

13 February, 2008 (23:05) | Разное, Решения упражнений | 2 comments

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

Решение упражнения 2.66 из SICP

13 February, 2008 (22:26) | Решения упражнений | No comments

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

Решение упражнения 2.65 из SICP

13 February, 2008 (22:04) | Решения упражнений | No comments

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

Решение упражнения 2.64 из SICP

13 February, 2008 (21:29) | Решения упражнений | No comments

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

Решение упражнения 2.63 из SICP

13 February, 2008 (20:54) | Решения упражнений | 7 comments

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

Решение упражнения 2.62 из SICP

12 February, 2008 (21:41) | Решения упражнений | 1 comment

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

Решение упражнения 2.61 из SICP

12 February, 2008 (21:16) | Решения упражнений | 3 comments

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