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

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

Используя процедуру generate-huffman-tree, построим следующее дерево для заданного “рок-алфавита”:

> (generate-huffman-tree '((A 2) (BOOM 1) (GET 2) (JOB 2) 
                           (NA 16) (SHA 3) (YIP 9) (WAH 1))) 
((leaf NA 16) 
 ((leaf YIP 9) 
  (((leaf A 2) 
    ((leaf WAH 1) 
     (leaf BOOM 1) 
     (WAH BOOM) 
     2) 
    (A WAH BOOM) 
    4) 
   ((leaf SHA 3) 
    ((leaf JOB 2) 
     (leaf GET 2) 
     (JOB GET) 
     4) 
    (SHA JOB GET) 
    7) 
   (A WAH BOOM SHA JOB GET) 
   11) 
  (YIP A WAH BOOM SHA JOB GET) 
  20) 
 (NA YIP A WAH BOOM SHA JOB GET) 
 36)

Оно может быть схематически изображено так (я оставил только листья и веса поддеревьев):

2701.png

Обозначив построенное дерево Хаффмана через ht, закодируем текст песни:

> (encode '(GET A JOB 
          SHA NA NA NA NA NA NA NA NA 
          GET A JOB 
          SHA NA NA NA NA NA NA NA NA 
          WAH YIP YIP YIP YIP YIP YIP YIP YIP YIP 
          SHA BOOM) 
        ht)
(1 1 1 1 1 1 1 0 0 1 1 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 
 1 1 1 0 0 1 1 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 0 1 0 1 0 1 
 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 1 0 1 1)

Получили код из 84 битов.

Для кодирования этой же песни кодом фиксированной длины для алфавита из 8 символов нам пришлось бы выделить минимум 3 бита на кодирование одного символа (так как 8 – это 2 в третьей степени). Всего символов в песне 36. Таким образом нам бы потребовалось 36*3 = 108 битов, что больше, чем в случае использования кодирования по Хаффману.

Выигрыш мы получаем за счет того, что слова-символы NA и YIP встречаются значительно чаще остальных.

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

18 February, 2008 (20:42) | Решения упражнений | 5 comments

На самом деле построить процедуру successive-merge совсем не сложно. Алгоритм наших действий прост. Мы будем хранить все деревья и листья в упорядоченном по возрастанию веса списке. Раз так, два самых легких элемента всегда будут находиться на двух первых позициях в списке. Стало быть, нам достаточно на каждом этапе алгоритма последовательного слияния брать два первых элемента из списка, соединять их в один и возвращать полученное дерево обратно в список (при этом оно в нем займет место в соответствии со своим весом, то есть список сохранит свойство упорядоченности). На каждом шаге количество элементов в списке уменьшается на один. Заканчиваем слияния мы тогда, когда в списке остался ровно один элемент, который и является искомым деревом Хаффмана.

Процедура successive-merge, реализующая эту идею, представлена ниже:

(define (successive-merge trees) 
  (if (null? (cdr trees)) 
      (car trees) 
      (successive-merge (adjoin-set (make-code-tree (car trees) 
                                                    (cadr trees)) 
                                    (cddr trees)))))

Определение не лишено некоторой элегантности.

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

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

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

  1. Первую лекцию читал Хэл Абельсон. Оказывается, он левша.
  2. Очень понравилось сравнение computer science и геометрии. Действительно, именно формализация способа мышления делает обе области знания тем, что они есть.
  3. Очень хорошее объяснение отличий между декларативными и императивными знаниями. Просто, но важно.
  4. Отличное описание абстракции черного ящика. Очень просто и понятно.
  5. Разговор об объектно-ориентированном программировании. Напоминаю, на дворе середина 80-ых годов. Официально С++ еще не существует. ООП означает Smalltalk. То есть это еще не мейнстрим.
  6. Отличный акцент на трех основных составляющих языка программирования: примитивах, средствах комбинирования и средствах абстракции.
  7. Очень позабавило выделение соответствующих скобок в допотопном редакторе. К сожалению, инструменты, в отличие от концепций, быстро устаревают. Отличная иллюстрация этой важной для программистов мысли.
  8. Отличное объяснение объявления процедуры через назначение имени процедуре, заданной через lambda.
  9. Понятие синтаксический сахар вводится так рано, еще до написания хотя бы одной более-менее серьезной программы.
  10. Отличное ударение на том, что в лиспе нет разницы между встроенными и пользовательскими процедурами.
  11. Очень понравилось, как Харольд использует то доску, то экран со слайдами для демонстрации фрагментов кода. Совместное использование, думаю, эффективнее использования только одного из этих способов демонстрации.
  12. Красивое дерево вызовов процедур для sqrt. Очень удобный способ для иллюстрации.
  13. В лекции есть несущественная ошибка на слайде, демонстрируемом в 1:05:30. (average 1.5 (/ 2 1.5)) явно не равно 1.3333.
  14. Блочная структура и фактически инкапсуляция введена очень просто и естественно. Мастерски. Просто аплодирую мысленно.
  15. Красивая и полезная для понимания таблица примитивов, средств комбинирования и средств абстрагирования для данных и процедур.

Лекция очень понравилась. Она дает дополнительное по сравнению с книгой понимание.

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

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

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

Если, спускаясь по поддеревьям, мы достигли листового элемента, значит генерация кода для символа окончена.

Если символ не найден в обоих поддеревьях, это ошибочная ситуация, о чем мы и сообщаем.

Определение процедуры ниже:

(define (encode-symbol symbol tree) 
  (if (leaf? tree) 
      null 
      (cond ((element-of-set? symbol (symbols (left-branch tree))) 
             (cons 0 (encode-symbol symbol (left-branch tree)))) 
            ((element-of-set? symbol (symbols (right-branch tree))) 
             (cons 1 (encode-symbol symbol (right-branch tree)))) 
            (else (error "символ не найден в дереве -- ENCODE-SYMBOL" symbol)))))
(define (element-of-set? x set) 
  (cond ((null? set) false) 
        ((equal? x (car set)) true) 
        (else (element-of-set? x (cdr set)))))

Процедура element-of-set? – это процедура проверки принадлежности элемента множеству, представленному неупорядоченным списком, данная в разделе 2.3.3.

Проверка также отрабатывает:

> (encode '(A D A B B C A) sample-tree) 
(0 1 1 0 0 1 0 1 0 1 1 1 0)

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

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

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

2671.png

При декодировании последовательности

0 1 1 0 0 1 0 1 0 1 1 1 0

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

Сначала, пройдем по левой ветке (0) и попадем в лист А:

0 1 1 0 0 1 0 1 0 1 1 1 0  

A

Теперь, двигаясь направо (1), опять направо (1) и налево (0), получим D:

0 1 1 0 0 1 0 1 0 1 1 1 0  

A D

Дальше действуем аналогично (шаги показаны ниже, результат на каждом шаге выделен жирным шрифтом):

0 1 1 0 0 1 0 1 0 1 1 1 0  

A D A
0 1 1 0 0 1 0 1 0 1 1 1 0  

A D A B
0 1 1 0 0 1 0 1 0 1 1 1 0  

A D A B B
0 1 1 0 0 1 0 1 0 1 1 1 0  

A D A B B C
0 1 1 0 0 1 0 1 0 1 1 1 0  

A D A B B C A

И действительно:

> (decode sample-message sample-tree)  

(A D A B B C A)

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

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

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

На текущий момент статистика следующая:

  • Написано 137 заметок (включая эту). К заметкам создано 57 комментариев.
  • Решено 112 упражнений (это меньше упражнения в день в среднем, но в последний месяц я сильно улучшил статистику и буду стараться поддерживать высокий темп).
  • Я на 163-ей странице книги.
  • Посещаемость сайта пока невысока, обычно 15-20 уникальных посетителей в день, но это и не массовый ресурс.
  • RSS-подписчиков пока целых 14 человек, причем один из них я сам 🙂

Надеюсь, информация, которую я здесь публикую, полезна и кому-то, кроме меня. Если у кого-нибудь из читателей есть пожелания или предложения, буду рад любым комментариям. Можно также связаться со мной и непосредственно.

Решение упражнения 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) 
        ((= given-key (key (entry set-of-records))) 
         (entry set-of-records)) 
        ((< given-key (key (entry set-of-records))) 
         (lookup given-key (left-branch set-of-records))) 
        ((> given-key (key (entry set-of-records))) 
         (lookup given-key (right-branch set-of-records)))))

Последнее условие в cond можно заменить на else.

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

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

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

Это позволяет нам реализовать операции над множествами, представленными бинарными деревьями, через уже реализованные операции над множествами, представленными упорядоченными списками. Для этого просто переведем исходные множества в списочное представление, воспользуемся старыми операциями и переведем результат в “деревянное” представление.

Вот как можно записать реализации операций объединения и пересечения множеств, представленных бинарными деревьями, воспользовавшись этой идеей:

(define (union-set-tree set1 set2) 
  (list->tree (union-set (tree->list set1)          
                         (tree->list set2))))
(define (intersection-set-tree set1 set2) 
  (list->tree (intersection-set (tree->list set1)          
                                (tree->list set2))))

Я дал процедурам новые имена, чтобы не было путаницы со старыми процедурами, определенными для списочного представления. Поскольку все преобразования из одной форму в другую и обратно, а также старые операции над списочными представлениями имели порядок роста Θ(n), новые операции также имеют порядок роста Θ(n).

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

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

Алгоритм работы процедуры partial-tree может быть очень кратко описан следующим образом.

Мы выбираем в списке центральный элемент и разбиваем список на часть до него не включительно (левая часть), сам элемент и часть после него опять не включительно (правая часть). После этого мы строим дерево, корнем которого является выбранный центральный элемент, левое поддерево строится аналогичным образом по левой части списка, а правое – аналогично по правой части списка.

Определение процедуры несколько усложнено, поскольку нам нужен удобный способ выделять части списка. Это достигается с помощью преобразования левой части в дерево и возвращения результата и остатка в виде пары.

При построении дерева из списка (1 3 5 7 9 11) сначала центральным элементом выбирается 5. Левым подсписком становится (1 3), правым – (7 9 11). В (1 3) центральный элемент – 1, левый подсписок пуст, правый – 3. В (7 9 11) центральный элемент – 9, левый подсписок – 7, правый – 11. В результате строится дерево, изображенное на рисунке ниже:

2641.png

Хочу отметить, что по построению дерево получается сбалансированным (так как поддеревья строятся из примерно равных половин списка).

Порядок роста – Θ(n), поскольку каждый элемент списка обрабатывается ровно по одному разу (назовем обработкой выбор элемента в качестве центрального и запись в узел дерева), а сама обработка элемента требует константного числа операций.

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

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

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

Поскольку все деревья на рисунке 2.16 содержат представление одного и того же множества, а стало быть содержат одни и те же элементы, обе процедура для каждого из этих деревьев будут выдавать список элементов множества в порядке возрастания: (1 3 5 7 9 11).

Несмотря на то, что процедуры делают одно и то же и похожи по используемым конструкциям, порядки их роста различны.

Второй вариант для каждого узла дерева выполняет константное число операций и вызывает себя для обоих поддеревьев. Следовательно, порядок его роста – Θ(n), где n – число элементов множества (узлов дерева).

Первый же вариант на каждом шаге рекурсии (для каждого узла дерева) вызывает процедуру append, которая на самом деле не выполняется за константное время, а требует числа шагов порядка количества элементов в поддереве. Будем предполагать, что дерево сбалансировано, то есть в поддеревьях каждого узла примерно поровну элементов. Пусть некоторое дерево содержит n элементов. Тогда поддеревья его корневого элемента содержат по n/2 элементов. Процедура tree->list-1 на корневом элементе потребует n/2 шагов для append и запустится на каждом из поддеревьев. На каждом из них (их два) аналогичным образом потребуется по n/4 шагов для append, то есть суммарно опять n/2. И так далее. То есть, спускаясь на один уровень по дереву от корня к листовым элементам, мы выполняем для всех вершин на этом уровне в сумме около n/2 шагов. Уровней в сбалансированном бинароном дереве, с которым мы имеем дело, примерно двоичный логарифм от числа элементов. Таким образом нам потребуется примерно n/2 * log2n, следовательно порядок роста – Θ(n log n).

Как вывод, есть смысл пользоваться вторым вариантом реализации, поскольку он порождает итеративный процесс и имеет меньший порядок роста.