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

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

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

(define (union-set set1 set2) 
  (cond ((null? set1) set2) 
        ((null? set2) set1) 
        (else 
         (let ((x1 (car set1)) (rest1 (cdr set1)) 
               (x2 (car set2)) (rest2 (cdr set2))) 
           (cond ((= x1 x2) (cons x1 (union-set rest1 rest2))) 
                 ((< x1 x2) (cons x1 (union-set rest1 set2))) 
                 (else (cons x2 (union-set set1 rest2))))))))

Под головным элементом списка s я подразумеваю (car s), а хвостом обзываю (cdr s).

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

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

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

Мы пойдем другим путем: объединим проверку нахождения элемента во множестве с добавлением элемента. Воспользуемся упорядоченностью списка. Если элемент x содержится во множестве, то он должен находиться в списке раньше, чем любой элемент, больший его. Таким образом мы просто будем идти по элементам списка, пока не встретим среди них либо x, либо какой-нибудь y больший x. Если мы встретили x, то просто вернем исходное множество без изменений. Если же нам встретился y, а x не встретился до него, то значит x в списке (и множестве, им представленном) отсутствует и должен быть добавлен непосредственно перед y.

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

(define (adjoin-set x set) 
  (cond ((null? set) (list x)) 
        ((= x (car set)) set) 
        ((< x (car set)) (cons x set)) 
        (else (cons (car set) (adjoin-set x (cdr set))))))

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

Мы делаем число шагов, пропорциональное позиции наименьшего элемента, не меньшего x, в списке. В среднем оно будет равно половине длины списка.

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

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

Очень показательное упражнение, которое одновременно является достаточно простым. SICP продолжает радовать.

Итак, как будут выглядеть операции проверки принадлежности множеству, добавления элемента, пересечения и объединения множеств в случае, если элементы в списке, представляющем множество, могут повторяться?

Во-первых, я хочу заметить, что мы можем вообще ничего не менять: старые операции работают корректно и на новом представлении множеств. Но это не единственный способ задать операции для такого внутреннего представления. Мы можем более вольно обращаться с операциями, создающими большие множества из меньших. Я имею в виду операции adjoin-set и union-set. Если операции element-of-set? и intersection-set мы оставим без изменений, то  adjoin-set и union-set можно сильно упростить, аж до неприличия:

(define (adjoin-set x set) 
  (cons x set))
(define (union-set set1 set2) 
  (append set1 set2))

Это упрощение возможно из-за того, что нас теперь не заботит многократное повторение одинаковых элементов в списке.

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

Число шагов, требующихся для операций element-of-set?, пропорционально числу элементов, то же можно сказать и о union-set (выигрыш по сравнению с квадратичным числом шагов ранее). Процедура intersection-set, по-прежнему, требует числа шагов, пропорционального квадрату длины списка (только вот длина его теперь будет больше). Наконец, adjoin-set выполняется за константное число шагов (большой выигрыш).

Итак, мы выигрываем в скорости операций adjoin-set и union-set, но проигрываем на операциях element-of-set? и intersection-set.

Таким образом представление множеств в виде списков с повторяющимися элементами имеет смысл тогда, когда операции добавления элемента и объединения множеств производятся часто, а проверка принадлежности элемента множеству и пересечение множеств производятся редко.

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

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

Для реализации операции объединения множеств мы можем применить рекурсивную стратегию, близкую по задумке к той, которая приводится при описании операции пересечения множеств в тексте книги. А именно, воспользуемся следующими тремя правилами при объединении множеств set1 и set2:

  1. Если set1 пусто, то объединение set1 и set2 есть set2.
  2. Если элемент x из set1 содержится в set2, то объединение set1 и set2 – это то же, что и объединение set1 без элемента x и set2.
  3. Если элемент x из set1 не содержится в set2, то объединение set1 и set2 – это то же, что и объединение set1 без элемента x и set2, к которому добавлен элемент x.

Воспользовавшись этими тремя правилами и выбирая в качестве элемента x первый элемент списка, представляющего множество set1, получим следующее определение union-set:

(define (union-set set1 set2) 
  (cond ((null? set1) set2) 
        ((element-of-set? (car set1) set2) 
         (union-set (cdr set1) set2)) 
        (else 
         (cons (car set1) 
               (union-set (cdr set1) set2)))))

Оно очень похоже на определение intersection-set.

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

10 February, 2008 (13:01) | Решения упражнений | 6 comments

Начнем с более простой части А упражнения. При записи в инфиксной форме с расстановкой всех скобок операции сложения и умножения принимают всегда по два аргумента. Причем порядок следования элементов в списке всегда такой: первый аргумент, знак операции, второй аргумент.

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

(define (sum? e)
  (and (pair? e) (eq? (cadr e) '+)))

(define (addend e)
  (car e))

(define (augend e)
  (caddr e))

(define (make-sum a1 a2)
  (list a1 '+ a2))

(define (product? e)
  (and (pair? e) (eq? (cadr e) '*)))

(define (multiplier e)
  (car e))

(define (multiplicand e)
  (caddr e))

(define (make-product m1 m2)
  (list m1 '* m2))

Теперь перейдем к части Б упражнения. Здесь ситуация осложняется тем, что каждая операция уже не задается жестко списком из трех элементов в фиксированном порядке. Для того, чтобы определить, какая операция перед нами, нужно найти то действие, которое будет выполняться первым и, соответственно, по нему определить, что это за операция и к каким операндам она применяется. Для этого введем вспомогательную процедуру split, которая, получив на вход элемент и последовательность, разбивает последовательность на список элементов до заданного элемента и список элементов после заданного элемента и возвращает список из этих двух списков. Если же элемент отсутствует в последовательности, split возвращает null:

(define (split el seq)
  (define (split-iter before after)
    (cond ((null? after) null)
          ((eq? (car after) el) (list before (cdr after)))
          (else (split-iter (append before (list (car after)))
                            (cdr after)))))
  (split-iter '() seq))

С помощью процедуры split мы теперь сможем разделять выражение для суммы или произведения по операции + или * и тем самым определить предикаты и селекторы:

(define (sum? e)
  (and (pair? e)
       (not (null? (split '+ e)))))

(define (omit-parenthesis e)
  (if (null? (cdr e))
      (car e)
      e))

(define (addend e)
  (omit-parenthesis (car (split '+ e))))

(define (augend e)
  (omit-parenthesis (cadr (split '+ e))))

(define (product? e)
  (and (pair? e)
       (not (sum? e))
       (not (null? (split '* e)))))

(define (multiplier e)
  (omit-parenthesis (car (split '* e))))

(define (multiplicand e)
  (omit-parenthesis (cadr (split '* e))))

Обратите внимание на две вещи:

  1. При проверке на то, является ли выражение произведением, мы сначала убеждаемся в том, что оно не является суммой. Это необходимо делать, так как сложение имеет более низкий приоритет, а значит выражение вида A*B+C является суммой, а не произведением.
  2. Мы вводим процедуру omit-parenthesis, которая убирает ненужные скобки вокруг переменных и чисел при получении аргументов сложения и умножения.

Теперь определим конструкторы для сложения и умножения. Здесь нам снова понадобятся вспомогательные процедуры:

(define (add-parenthesis predicate? e)
  (if (predicate? e)
      e
      (list e)))

(define (sum-or-product? e)
  (pair? e))

(define (make-operation op predicate? arg1 arg2)
  (append (add-parenthesis predicate? arg1)
          (list op)
          (add-parenthesis predicate? arg2)))

Процедура add-parenthesis в некотором смысле обратна omit-parenthesis. Она окружает скобками выражения, не удовлетворяющую предикату. Процедура sum-or-product? является предикатом, возвращающим истину на сумме и произведении и ложь на всем остальном. В нашем случае он может быть записан очень просто. Наконец, make-operation выполняет основную работу, соединяя выражения-операнды, окружая их скобками при необходимости.

Записать конструкторы для сложения и умножения очень просто:

(define (make-sum a1 a2)
  (make-operation '+ sum-or-product? a1 a2))

(define (make-product m1 m2)
  (make-operation '* product? m1 m2))

На этом адаптация программы дифференцирования для записей в инфиксной форме завершена. Проверим, как она работает на каком-нибудь примере:

> (deriv '(x + 3 * (x + y + 2)) 'x)
(1 + 3 * (1 + 0 + 0) + 0 * (x + y + 2))

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

(define (make-sum a1 a2)
  (cond ((=number? a1 0) a2)
        ((=number? a2 0) a1)
        ((and (number? a1) (number? a2)) (+ a1 a2))
        (else (make-operation '+ sum-or-product? a1 a2))))

(define (make-product m1 m2)
  (cond ((or (=number? m1 0) (=number? m2 0)) 0)
        ((=number? m1 1) m2)
        ((=number? m2 1) m1)
        ((and (number? m1) (number? m2)) (* m1 m2))
        (else (make-operation '* product? m1 m2))))

Теперь результат вычисления производной упрощается:

> (deriv '(x + 3 * (x + y + 2)) 'x)
4

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

Видео лекции SICP. Самые первые впечатления.

9 February, 2008 (13:22) | Видео, Материалы | 3 comments

Итак, после сегодняшней счастливой развязки истории с заказом дисков с видео Абельсона и Сассмана я успел только бегло проглядеть сами видео-ролики. Потому впечатления, которые есть у меня сейчас, предельно поверхностны и наверняка очень субъективны. Тем не менее, считаю, что есть смысл ими поделиться хотя бы для того, чтобы потом после более близкого знакомства оценить степень своих заблуждений.

Итак, что сразу бросается в глаза:

  1. Оба лектора очень хороши. Они разные, но манера преподнесения материала весьма приятна. Их интересно слушать.
  2. На протяжении всего курса есть определенный налет волшебства, который подчеркивает Абельсон уже с первых минут. Создается впечатление, что смотришь сказку для инженеров.
  3. Аудитория очень возрастная. Молодежи довольно мало. Это сразу бросается в глаза. Сейчас более типично было бы ожидать увидеть среди слушателей около 80% 20-25 летних. Но прошло 20 лет, индустрия программного обеспечения здорово изменилась.
  4. Структура лекций близка к книге, но не полностью повторяет ее. Некоторые разделы пропущены, некоторые вещи идут в другом порядке, что-то вообще в книге отсутствует. Естественно, на чем-то делается больший акцент, на чем-то меньший. Это не странно, особенно учитывая, что книга с тех пор пережила второе издание, в котором были сделаны изменения.
  5. Английский обоих лекторов мне показался очень понятным и достаточно простым.

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

Как получить видео лекции SICP, если у вас нет безлимитки. Часть 3.

9 February, 2008 (13:02) | Видео, Материалы | 2 comments

Окончание истории. Начало читайте здесь, а продолжение здесь.

Субботним зимним утром я отправился на почтовое отделение с целью получить свои законные диски с видео-материалами SICP, которые по всем расчетам просто обязаны были дойти до нашей забытой богом почты.

После непродолжительного разбирательства выяснилось, что бандероль действительно уже пришла и ждет своего адресата. Заплатив 42 гривны 10 копеек (чуть больше $8), я забрал диски. Упакованы они были достаточно аккуратно, в специальный защитный пакет с воздушной прослойкой, оберегающей диски от повреждений.

Сейчас успел только бегло просмотреть видео, которые, конечно же, нужно будет внимательно изучать. Первые впечатления опишу в следующей заметке. Диски отлично читаются. Лекции записаны в DivX, их 10 штук, каждая состоит их двух частей. Одна часть представлена одним avi-файлом, размером около 500М.

Хочу поблагодарить Lafox.net за отличную работу.

Со своей стороны готов поделиться видео-файлами лекций со всеми желающими, живущими в Днепропетровске или бывающими в нашем городе. Если нужно, просто сообщите мне об этом.

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

8 February, 2008 (22:10) | Решения упражнений | 6 comments

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

Мы будем представлять сумму как список из символа + и последующего произвольного количества слагаемых. 

Селектор addend вообще не меняется:

(define (addend s) (cadr s))

Селектор augend будет возвращать либо одно последнее слагаемое, если слагаемых было всего два, либо сумму всех слагаемых, начиная со второго:

(define (make-sum-list seq) 
  (if (null? (cdr seq)) 
      (car seq) 
      (cons '+ seq)))
(define (augend s) 
  (make-sum-list (cddr s)))

Процедура make-sum-list вынесена специально, так как она нам еще понадобится.

При построении суммы с помощью make-sum мы будем делить все слагаемые на две группы: числа (константы), которые будen сразу суммироваться в число const, и выражения (с переменные значениями), которые будут накапливаться в списке vars. Затем в зависимости от результирующих значений мы будем их комбинировать для получения окончательного результата. Определение выглядит так:

(define (make-sum . seq) 
  (let ((vars (filter non-number? seq)) 
        (const (accumulate + 0 (filter number? seq)))) 
    (cond ((null? vars) const) 
          ((= 0 const) (make-sum-list vars)) 
          (else (make-sum-list (cons const vars))))))

Абсолютно аналогичные построения можно проделать и для произведения:

(define (multiplier p) (cadr p))
(define (make-product-list seq) 
  (if (null? (cdr seq)) 
      (car seq) 
      (cons '* seq)))
(define (multiplicand p) 
  (make-product-list (cddr s)))
(define (make-product . seq) 
  (let ((vars (filter non-number? seq)) 
        (const (accumulate * 1 (filter number? seq)))) 
    (cond ((null? vars) const) 
          ((= 0 const) 0) 
          ((= 1 const) (make-product-list vars)) 
          (else (make-product-list (cons const vars))))))

Попробуем вычислить производную из условия упражнения:

> (deriv '(* x y (+ x 3)) 'x) 
(+ (* x y) (* y (+ x 3)))

Результат ожидаемый.

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

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

Сначала модифицируем процедуру deriv с тем, чтобы она распознавала и операцию возведения в степень:

(define (deriv exp var)
  (cond ((number? exp) 0)
        ((variable? exp)
         (if (same-variable? exp var) 1 0))
        ((sum? exp)
         (make-sum (deriv (addend exp) var)
                   (deriv (augend exp) var)))
        ((product? exp)
         (make-sum
           (make-product (multiplier exp)
                         (deriv (multiplicand exp) var))
           (make-product (deriv (multiplier exp) var)
                         (multiplicand exp))))
        ((exponentiation? exp)
         (make-product
           (make-product
             (exponent exp)
             (make-exponentiation (base exp)
                                  (- (exponent exp) 1)))
           (deriv (base exp) var)))
        (else
         (error "неизвестный тип выражения -- DERIV" exp))))

Теперь доопределим новые операции, связанные с возведением в степень. Проверка exponentiation?, а также селекторы base и exponent записываются абсолютно аналогично соответствующим процедурам для сложения и умножения:

(define (exponentiation? x) 
  (and (pair? x) (eq? (car x) '**)))
(define (base e) (cadr e))
(define (exponent e) (caddr e))

Теперь перейдем к конструктору, в котором сразу же учтем правила сокращения. Хочу подчеркнуть, что в данный момент мы будем работать только лишь с выражениями, показатель степени которых числовой. То есть для показателя не допускается содержание выражений либо переменных. Это ограничение мы приняли еще на этапе записи процедуры deriv. В противном случае задача усложняется, так как нам нужно вводить производную для сложной функции, вводить операцию вычитания, рассматривать существенно больше случаев сокращения, оповещать об ошибках несоответствия аргументов области определения функций и т.д. – коротко говоря, последствия столь опрометчивого поступка весьма существенны. Итак, примем, что показатель является числом. Будем учитывать такие 2 правила сокращения выражений:

  1. x0 = 1,
  2. x1 = x.

Тогда получим следующее определение процедуры make-exponentiation:

(define (power a b) 
  (exp (* b (log a))))
(define (make-exponentiation base expt) 
  (cond ((=number? expt 0) 1) 
        ((=number? expt 1) base) 
        ((and (number? base) (number? expt)) (power base expt)) 
        (else (list '** base expt))))

Проверим работу на примере:

> (deriv '(+ (** x 3) (** x 2)) 'x) 
(+ (* 3 (** x 2)) (* 2 x))

Ответ правильный и даже сокращен.

Как получить видео лекции SICP, если у вас нет безлимитки. Часть 2.

7 February, 2008 (23:23) | Видео, Материалы | 1 comment

Продолжение истории. Начало читайте здесь.

При столкновении красивой теории с жестокой реальностью рождается горькая практика. В моем случае оптимистичные ожидания получить диски с видео лекций курса “Структура и интерпретация компьютерных программ” еще к концу прошлой недели не оправдались.

Сегодня прошло 9 дней с момента отправки бандероли, и я посетил свое почтовое отделение, ожидая обнаружить диски там (у нас иногда почтальон “забывает” принести оповещение о приходе посылки). Однако, на почте меня огорчили, сказав, что никаких писем и посылок для меня у них нет.

Уточнив ситуацию у Lafox.net, выяснил, что днепропетровские почтальоны у них на плохом счету. Буду в субботу делать второй заход на почту. Все же нужно было выбирать доставку “Автолюксом”.

Тем не менее не теряю надежду получить диски в ближайшее время. Следите за новостями 🙂