Month: February, 2008

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

22 February, 2008 (11:37) | Решения упражнений | 4 comments

Это упражнение сформулировано довольно обобщенно и допускает достаточно широкий диапазон трактовок. Я предлагаю один из вариантов по мотивам предшествующего раздела книги, который демонстрирует основные идеи. Итак, пусть в компании Insatiable Enterprises, Inc. есть два отела: разработки (инженерный) и продаж. В отделе разработки записи о сотрудниках содержат имена, должности и размеры окладов. Запись соединяет поля с […]

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

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

Выполнять это упражнение не очень удобно, так как операции put и get пока что для нас виртуальны, а значит опробовать код на практике не удастся. Тем не менее начнем. а. В приведенном определении процедуры deriv после проверок выражения на числовое значение и переменную происходит диспетчеризация по типу операции. То есть код смотрит, какая операция находится […]

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

19 February, 2008 (20:57) | Решения упражнений | 2 comments

Количество шагов, необходимых для кодирования одного символа в общем случае может сильно розниться. Можно говорить о наилучшем, наихудшем и среднем случаях для разных символов и разных конфигураций дерева Хаффмана. Говорить же о порядке роста числа шагов, ничего не зная о символах и дереве, сложно. В качестве иллюстрации рассмотрим случай, когда относительные частоты символов таковы, как […]

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

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

Заметим, что для заданных частот символов справедливо утверждение о том, что сумма двух наименьших частот меньше любой из оставшихся частот. Следовательно, дерево будет вырождено. Также отметим, что: 1+2 = 3 = 4 – 1, 3+4 = 7 = 8 – 1, … 2n-1 + 2n = 2n+1-1. Таким образом дерево Хаффмана для n=5 будет выглядеть следующим […]

Решение упражнения 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) […]

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

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

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

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

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

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

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

15 February, 2008 (21:24) | Решения упражнений | 2 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 упражнений (это меньше упражнения в день в среднем, но в последний месяц я сильно улучшил статистику и […]