учебники, программирование, основы, введение в,

 

Отображения и функционалы

Отображения структур данных и функционалы
Отображения обычно используются при анализе и обработке данных, представляющих информацию разной природы. Вычисление, кодирование, трансляция, распознавание - каждый их таких процессов использует исходное множество цифр, шаблонов, текстов, идентификаторов, по которым конкретная отображающая функция находит пронумерованный объект, строит закодированный текст, выделяет идентифицированный фрагмент, получает зашифрованное сообщение. Таким образом работает любое введение обозначений - от знака происходит переход к его смыслу.
Отображения - ключевой механизм информатики. Построение любой информационной системы сопровождается определением и реализацией большого числа отображений. Сначала выбираются данные, с помощью которых представляется информация. В результате по данным можно восстановить представленную ими информацию - извлечь информацию из данных (по записи числа восстановить его величину). Потом конструируется набор структур, достаточный для размещения и обработки данных и программ в памяти компьютера (по коду команды можно выбрать хранимую в памяти подпрограмму, которая построит новые коды чисел или структур данных).
Говорят, что отображение существует, если задана пара множеств и отображающая функция, для которой первое множество - область определения, а второе - область значения. При определении отображений, прежде всего, должны быть ясны следующие вопросы:

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

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

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

При функциональном стиле программирования ответ на каждый из таких вопросов может быть дан в виде отдельной функции, причем роль каждой функции в схеме реализации отображения четко фиксирована. Схема реализации отображения может быть представлена в виде определения, формальными параметрами которого являются обозначения функций, выполняющих эти роли. Такое определение называется <функционал>. Более точно, функционал может оперировать функциями в качестве аргументов или результатов.
Функции, выполняющие конкретные роли, могут быть достаточно общими, полезными при определении разных отображений, - они получают имена для многократного использования в разных системах определений. Но могут быть и разовыми, нужными лишь в данном конкретном случае - тогда можно обойтись без их имен, использовать определение непосредственно в точке вызова функции. Таким образом, определение отображения может быть разбито на части (функции и функционалы) разного назначения, типичного для многих схем информационной обработки. Это позволяет упрощать отладку систем определений, повышать коэффициент повторного использования отлаженных функций. Можно сказать, что отображения - эффективный механизм абстрагирования, моделирования, проектирования и формализации крупномасштабной обработки информации. Возможности отображений в информатике значительно шире, чем освоено практическим программированием, но их применение требует дополнительных пояснений, которые и являются предметом этой лекции.
Числа и мультиоперации
Любую информацию можно представить в виде символьных выражений. В качестве основных видов символьных выражений выбраны списки и атомы.
Атом - неделимое данное, представляющее информацию произвольной природы.
Во многих случаях знание природы информации дает более четкое понимание особенностей изучаемых механизмов. Программирование работы с числами и строками - привычная, хорошо освоенная область информационной обработки, удобная для оценки преимуществ использования функционалов. Опуская технические подробности, просто отметим, что числа и строки рассматриваются как самоопределимые атомы, смысл которых не требует никакого ассоциирования, он понятен просто по виду записи.
Например, натуральные числа записываются без особенностей и могут быть почти произвольной длины:
1
-123
9876543210000000000000123456789
Можно работать с дробными и вещественными числами:
2/3
3.1415926
Строки заключаются в обычные двойные кавычки: "строка любой длины из произвольных символов, включая все что угодно".
Список - составное данное, первый элемент которого может рассматриваться как функция, применяемая к остальным элементам, также представленным как символьные выражения. Это относится и к операциям над числами и строками:
(+ 1 2 3 4 5 6) = 21
(- 12 6 3) = 3
(/ 3 5) = 3/5
(1+ 3) = 4
Большинство операций над числами при префиксной записи естественно рассматривать как мультиоперации от произвольного числа аргументов.
(string-equal "строка 1" "строка1") = Nil
(ATOM "a+b-c") = T
(char "стр1" 4 ) = "1"
Со строками при необходимости можно работать посимвольно, хотя они рассматриваются как атомы.
Любой список можно превратить в константу, поставив перед ним <'> апостроф. Это эквивалентно записи со специальной функцией QUOTE. Для чисел и строк в этом нет необходимости, но это не запрещено.
'1 = 1
'"abc" = "abc"
Можно строить композиции функций. Ветвления представлены как результат специальной функции COND, использующей отличие от Nil в качестве значения <истина>. Числа и строки таким образом оказываются допустимыми представлениями значения <истина>. Отказ от барьера между представлениями функций и значений дает возможность использовать символьные выражения как для изображения заданных значений, включая любые структуры над числами и строками, так и для определения функций, обрабатывающих любые данные. (Напоминаем, что определение функции - данное.) Функционалы - это функции, которые используют в качестве аргументов или результатов другие функции. При построении функционалов переменные могут играть роль имен функций, определения которых находятся во внешних формулах, использующих функционалы.

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

(defun next (xl)       ; Следующие числа*)
(cond                  ; пока список не пуст
(xl(cons(1+(car xl)) ; прибавляем 1 к его голове
(next(cdr xl))   ; и переходим к остальным,
) ) ) )              ; собирая результаты в список

(next'(1 2 5))         ; = (2 3 6) 
Пример 4.1.
Построить список из <голов> элементов списка
(defun 1st (xl)
; "головы" элементов = CAR
(cond                 ; пока список не пуст
(xl (cons (caar xl); выбираем CAR от его головы
(1st (cdr xl))   ; и переходим к остальным,
) ) ) )                ; собирая результаты в список

(1st'((один два)(one two)(1 2)) )   ; = (один one 1) 
Пример 4.2.
Выяснить длины элементов списка
(defun lens (xl)    ; Длины элементов
(cond            ; Пока список не пуст 
(xl (cons (length (car xl)) 
; вычисляем длину его головы
(lens (cdr xl)); и переходим к остальным,
) ) ) )             ; собирая результаты в список 

(lens'((1 2)()(a b c d)(1(a b c d)3)) )    
; = (2 0 4 3) 
Пример 4.3.
Внешние отличия в записи этих трех функций малосущественны, что позволяет ввести более общую функцию map-el, в определении которой имена <car>, <1+> и <length> могут быть заданы как значения параметра fn:
(defun map-el(fn xl)
; Поэлементное преобразование XL
; с помощью функции FN
(cond         ; Пока XL не пуст
(xl(cons(funcall fn (car xl))
; применяем FN как функцию голове XL**)
(map-el fn (cdr xl))
; и переходим к остальным,
) ) ) )            ; собирая результаты в список
Эффект функций next, 1st и lens можно получить выражениями:
(map-el #'1+ xl)        ; Следующие числа:
(map-el #'car xl)       ; "головы" элементов = CAR
(map-el #'length xl)    ; Длины элементов

(map-el #'1+'(1 2 5))   ; = (2 3 6)
(map-el #'car'((один два)(one two)(1 2)) )
; = (один one 1)
(map-el #'length'((1 2)()(a b c d)(1(a b c d)3)) )
; = (2 0 4 3)
соответственно.
Все три примера можно решить с помощью таких определяющих выражений:
(defun next(xl)
(map-el #'1+ xl)) ; Очередные числа:
(defun 1st(xl)
(map-el #'car xl)) ; "головы" элементов = CAR
(defun lens(xl)
(map-el #'length xl)) ; Длины элементов
Эти определения функций формально эквивалентны ранее приведенным - они сохраняют отношение между аргументами и результатами. Параметром функционала может быть любая вспомогательная функция.
Пусть дана вспомогательная функция sqw, возводящая числа в квадрат
(defun sqw (x)(* x x)) ; Возведение числа в квадрат
(sqw 3)               ; = 9
Пример 4.4.
Построить список квадратов чисел, используя функцию sqw:
(defun sqware (xl)
; Возведение списка чисел в квадрат
(cond      ; Пока аргумент не пуст,
(xl (cons (sqw (car xl))
; применяем sqw к его голове
(sqware(cdr xl))
; и переходим к остальным,
) ) ) )          ; собирая результаты в список

(sqware'(1 2 5 7))      ; = (1 4 25 49 )
Можно использовать map-el:
(defun sqware (xl) (map-el #'sqw xl))
Ниже приведено определение функции sqware- без вспомогательной функции, выполняющее умножение непосредственно. Оно влечет за собой двойное вычисление (CAR xl), т.е. такая техника не вполне эффективна:
(defun sqware- (xl)
(cond
(xl (cons (* (car xl) (car xl) )
; квадрат головы списка
; голову вычислять приходится дважды
(sqware- (cdr xl))
) ) ) )
Пусть дана вспомогательная функция tuple, превращающая любое данное в пару:
(defun tuple (x) (cons x x)) 
(tuple 3)
(tuple 'a)
(tuple '(Ха))
; = (3 . 3)
; = (a . a)
; = ((Ха) . (Ха)) = ((Ха) Ха)
; - это одно и то же! 
Пример 4.5.
Чтобы преобразовать элементы списка с помощью такой функции, пишем сразу:
(defun duble (xl) (map-el #'tuple xl))
; дублирование элементов
(duble '(1(a)()))   ; = ((1 . 1)((a)a)(()))
Немногим сложнее организовать покомпонентную обработку двух списков.
Построить ассоциативный список, т.е. список пар из имен и соответствующих им значений, по заданным спискам имен и их значений:
(defun pairl (al vl) ; Ассоциативный список
(cond             ; Пока AL не пуст, 
(al (cons (cons (car al) (car vl)) 
; пары из <голов>. 
(pairl (cdr al) (cdr vl)) 
; Если VL исчерпается,
; то CDR будет давать NIL 
) ) ) )    

 (pair '(один два two three) '(1 2 два три))
; = ((один . 1)(два . 2)(two . два)(three . три)) 
Пример 4.6.
Определить функцию покомпонентной обработки двух списков с помощью заданной функции fn:
(defun map-comp (fn al vl) 
; fn покомпонентно применить
; к соотвественным элементам
; AL и VL 
(cond    
(xl (cons (funcall fn (car al) (car vl)) 
; Вызов данного FN как функции 
(map-comp (cdr al) (cdr vl))
) ) ) ) 
Пример 4.7.
Теперь покомпонентные действия над векторами, представленными с помощью списков, полностью в наших руках. Вот списки и сумм, и произведений, и пар, и результатов проверки на совпадение:
(map-comp #'+'(1 2 3) '(4 6 9))
; = (5 8 12) Суммы
(map-comp #'*'(1 2 3) '(4 6 9))
; = (4 12 27) Произведения
(map-comp #'cons'(1 2 3) '(4 6 9))
; = ((1 . 4) (2 . 6) (3 . 9)) Пары
(map-comp #'eq'(4 2 3) '(4 6 9))
; = (T NIL NIL) Сравнения
Достаточно уяснить, что надо делать с элементами списка, остальное довершит функционал map-comp, отображающий этот список в список результатов заданной функции.
Для заданного списка вычислим ряд его атрибутов, а именно - длина, первый элемент, остальные элементы списка без первого.
(defun mapf (fl el) 
(cond  ; Пока первый аргумент не пуст, 
(fl (cons (funcall (car fl) el) 
; применяем очередную функцию
; ко второму аргументу 
(mapf (cdr fl) el) 
; и переходим к остальным функциям,
) ) ) )   ; собирая их результаты в общий
; список 

 (mapf '(length car cdr) '(a b c d)) 
; = (4 a (b c d)) 
Пример 4.8.
Композициями таких функционалов можно применять серии функций к списку общих аргументов или к параллельно заданной последовательности списков их аргументов. Естественно, и серии, и последовательности представляются списками.

Безымянные функции
Определения в примерах 4.4 и 4.5 не вполне удобны по следующим причинам:

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

С одной стороны, последнее утверждение противоречит пониманию смысла именования как техники, обеспечивающей неоднократность применения поименованного объекта. С другой стороны, придумывать подходящие, долго сохраняющие понятность и соответствие цели, имена - задача нетривиальная.
Учитывая это, было бы удобнее вспомогательные определения вкладывать непосредственно в определения целевых функций и обходиться при этом вообще без имен. Конструктор функций lambda обеспечивает такой стиль построения определений. Этот конструктор любое выражение expr превращает в функцию с заданным списком аргументов (x1. .. xK) в форме так называемых lambda-выражений:
(lambda (x1 ... xK) expr)
Имени такая функций не имеет, поэтому может быть применена лишь непосредственно. DEFUN использует данный конструктор, но требует дать функциям имена.
Определение функций duble и sqware из примеров 4.4 и 4.5 без использования имен и вспомогательных функций:
(defun sqware (xl)
(map-el #' (lambda (x) (* x x)) xl))

(defun duble (xl)
(map-el #' (lambda (x) (cons x x)) xl))
Пример 4.9.
Любую систему взаимосвязанных функций можно преобразовать к одной функции, используя вызовы безымянных функций.
Композиции функционалов, фильтры, редукции
Вызовы функционалов можно объединять в более сложные структуры таким же образом, как и вызовы обычных функций, а их композиции можно использовать в определениях новых функций. Композиции функционалов позволяют создавать и более мощные построения, достаточно ясные, но требующие некоторого внимания.
Декартово произведение хочется получить определением вида:
(defun decart (x y)
(map-el #' (lambda (i)
(map-el #' (lambda (j) (list i j)) y)
) x) )
Пример 4.10.
Но результат вызова
(decart '(a s d) '( e r t))
дает
(((A E) (A R) (A T)) ((S E) (S R)
(S T)) ((D E) (D R) (D T)))
вместо ожидаемого
((A E) (A R) (A T) (S E) (S R)
(S T) (D E) (D R) (D T))
Дело в том, что функционал map-el, как и map-comp (пример 4.7), собирает результаты отображающей функции в общий список с помощью операции cons так, что каждый результат функции образует отдельный элемент.
А по смыслу задачи требуется, чтобы список был одноуровневым.
Посмотрим, что получится, если вместо cons при сборе результатов воспользоваться функцией append.
Пусть дан список списков. Нужно их все сцепить в один общий список.
(defun list-ap (ll)
(cond
(ll (append (car ll)
(list-ap (cdr ll))
) ) ) )

(list-ap '((1 2)(3 (4))))   ; = (1 2 3 (4))
Пример 4.11.
Тогда по аналогии можно построить определение функционала map-ap:
(defun map-ap (fn ll)
(cond
(ll (append (funcall fn (car ll) )
(map-ap fn (cdr ll) )
) ) ) )

(map-ap 'cdr '((1 2 3 4) (2 4 6 8) (3 6 9 12)))
; = (2 3 4 4 6 8 6 9 12)
Следовательно, интересующая нас форма результата может быть получена:
(defun decart(x y)
(map-ap #'(lambda(i)
(map-el #'(lambda(j)(list i j))
y))x))
(decart '(a s d) '(e r t))
; = ((A E)(A R)(A T)(S E)(S R)(S T)(D E)(D R)(D T))
Сцепление результатов отображения с помощью append обладает еще одним полезным свойством: при таком сцеплении исчезают вхождения пустых списков в результат. А в Лиспе пустой список используется как ложное значение, следовательно, такая схема отображения пригодна для организации фильтров. Фильтр отличается от обычного отображения тем, что окончательно собирает не все результаты, а лишь удовлетворяющие заданному предикату.
Построить список голов непустых списков можно следующим образом:
(defun heads (xl) (map-ap
#'(lambda (x) (cond (x (cons (car x) NIL))))
; временно голова размещается в список,
; чтобы потом списки сцепить
xl
) )
(heads '((1 2) () (3 4) () (5 6)) )
; = (1 3 5)
Пример 4.12.
Рассмотрим еще один типичный вариант применения функционалов. Представим, что нас интересуют некие интегральные характеристики результатов, полученных при отображении, например, сумма полученных чисел, наименьшее или наибольшее из них и т.п. В таком случае говорят о свертке результата или его редукции. Редукция заключается в сведении множества элементов к одному элементу, в вычислении которого задействованы все элементы множества.
Подсчитать сумму элементов заданного списка.
(defun sum-el ( xl)
(cond ((null xl) 0)
(xl (+ (car xl)
(sum-el (cdr xl) )
) ) ) )

(sum-el '(1 2 3 4) )   ; = 10
Пример 4.13.
Перестроим такое определение, чтобы вместо <+> можно было использовать произвольную бинарную функцию:
(defun red-el (fn xl)
(cond ((null xl) 0)
(xl (funcall fn (car xl)
(red-el fn (cdr xl) )
) ) ) )
(red-el '+ '(1 2 3 4) )   ; = 10
В какой-то мере map-ap ведет себя как свертка - она сцепляет результаты без сохранения границ между ними.
Такие формулы удобны при моделировании множеств, графов и металингвистических формул, а к их обработке сводится широкий класс задач не только в информатике.

Встроенные функционалы (Clisp)
Отображающий функционал можно написать самим, а можно и воспользоваться одним из встроенных. Согласно стандарту, в реализацию языка Clisp обычно включены функционалы: map, mapcar,maplist, mapcan, mapcon, mapc, mapl . Каждый из них покомпонентно обработает любой набор списков. Отличаются они схемами выбора аргументов для отображающей функции, характером воздействия на исходные данные и оформлением результатов, передаваемых объемлющим формулам.
Map
( map result-type function sequences ... )
Функция function вызывается на всех первых элементах последовательностей, затем на всех вторых и т.д. Из полученных результатов function формируется результирующая последовательность, строение которой задается параметром result-type с допустимыми значениями cons, list, array, string, NIL.
Mapcar
( mapcar function list ... )
Функция function применяется к первым элементам списков, затем ко вторым и т.д. Другими словами, function применяется к <головам> методично сокращающихся списков, и результаты применения собираются в результирующий список.

(mapcar #'+ '(1 2 3) '(4 5 6))
            ; = (5 7 9)
(mapcar #'list '(1 2 3)'(4 5 6))
            ; = ((1 4)(2 5)(3 6))
(defun evlis (args) (mapcar #'eval args))
            ; вычисление аргументов
Пример 4.14. (
(Без учета ассоциативного списка)
(defun evlis (args AL) (mapcar #'(lambda (x)
(eval x AL)) args))
Maplist
( maplist function list ... )
Функционал аналогичен mapcar, но function применяется к <<хвостам>> списков list, начиная с полного списка.
(maplist #'list '(1 2 3)'(4 5 6))
      ; = (((1 2 3) (4 5 6)) ((2 3)
(5 6)) ((3) (6)))
Пример 4.15.
Mapc и Mapl
Оба функционала работают как mapcar и maplist, соответственно, за исключением того, что они в качестве формального результата выдают первый список (своеобразная аналогия с формальными аргументами).
(mapc #'list '(1 2 3)'(4 5 6)) ; = (1 2 3)
(mapl #'list '(1 2 3)'(4 5 6)) ; = (1 2 3)
Пример 4.16.
Mapcan и Mapcon
И эти два функционала аналогичны mapcar и maplist, но формирование результатов происходит не с помощью операции cons, которая строит данные в новых блоках памяти, а с помощью деструктивной функции nconc, которая при построении новых данных использует память исходных данных, из-за чего исходные данные могут быть искажены.
В общем случае, отображающие функционалы представляют собой различные виды структурной итерации или итерации по структуре данных. При решении сложных задач полезно использовать отображения и их композиции, а также иметь в виду возможность создания своих функционалов.
Map-into отображает результат в конкретную последовательность.
Подведение итогов
Показанные построения достаточно разнообразны, чтобы можно было сформулировать, в чем преимущества применения техники функционального программирования:

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

Для самостоятельного решения
Можно предложить следующие задачи на применение функционалов:
1) Напишите определение функционала F-ALL, выясняющего, все ли элементы множества Set удовлетворяют заданному предикату Pred.
(defun f-all (Pred Set ) . . . )
2) Напишите определение функционала F-ex, выясняющего, найдется ли в множестве Set элемент, удовлетворяющий заданному предикату Pred.
(defun f-ex (Pred Set ) . . . )
3) Пусть программа представляет собой набор списков, содержащих имя команды и произвольное число операндов. Имя расположено первым в списке. Напишите определение функционала, удобного для выдачи списка операндов, встречающихся в программе, а также для выдачи отдельных интегральных характеристик, таких как суммарное число всех операндов, максимальное число операндов в команде и т.п.
4) Напишите универсальный фильтр, позволяющий из произвольного списка выделять при необходимости атомы, числа, строки или списки, начинающиеся с заданного атома, и т.д.
5) Пусть клетки доски типа шахматной пронумерованы по горизонтали символами, а по вертикали числами. И то, и другое перечислено в отдельных списках по порядку. Напишите функцию перечисления координат всех клеток доски, соответствующей размерам списков.
6) При анализе труднодоступных данных требуется всю потенциально полезную информацию выяснять сразу, <в одно касание>. Напишите модель такого стиля работы на примере покомпонетной обработки двух списков чисел. Роль полезной информации могут играть значения любых бинарных операций, таких как +, *, -, /, max, min и т.п.
7) Пусть программа представляет собой набор списков, содержащих имя команды и не более двух операндов. Имя расположено в списке первым. Напишите определение функционала, удобного для выдачи по мере необходимости перечня команд, или перечня первых операндов, или вторых операндов и т.п.
Подготовьте определения вспомогательных функций на все эти случаи.
8) Список содержит ежедневные сведения о количестве осадков, выпавших за весьма длительный период. Напишите функционал, позволяющий по этому списку оперативно выяснять различные сведения, наподобие:

  • суммарный объем осадков;
  • максимальное количество осадков в день;
  • минимальное количество осадков в день;
  • максимальная разница в количестве осадков в соседние дни.

9) Задача повышенной сложности (с решением).
Лексикон ***)
Условие задачи: Группа специалистов договорилась подготовить лексикон программирования для электронной публикации. Было решено, что надо добиться <правильности> определения понятий программирования, а именно не допускать цепочек понятий прямо или косвенно определяемых через себя. Кроме того, следует обеспечить полноту комплекта определений, т.е. всякое включенное в лексикон понятие должно иметь определение.
Напишите программу, помогающую по ходу разработки лексикона отслеживать его <правильность> и полноту.
Входные данные:
(( имя_понятия объяснение ) ... ) -
двухуровневый список, в котором
имя_понятия - атом, обозначающий
определяемое понятие,
объяснение - последовательность строк и/или атомов,
строки не требуют определения,
а атомы должны получить
определения в процессе разработки, но, возможно,
еще не все слова удалось объяснить.
Выходные данные:
Словарь правилен
или
Есть неправильные цепочки
имя_понятия1 ... имя_понятияN
|___________________|______
начала неправильных цепочек
и/или
Есть неопределенные понятия
имя_понятия1 ... имя понятияN
|___________________|_______
имена неопределенных понятий
(слова перечисляются в порядке включения в словарь.)
Пример ввода:
(( автокод язык_программирования
<используется для создания>
операционная_система <и> транслятор)
( язык_программирования <задается множеством правил
для написания> программ)
( операционная_система <комплекс> программа
<управляющих решением задач на
имеющемся оборудовании>)
( транслятор <компилирующая> программа)
( программа <описание> алгоритм
<решения задачи на соответствующем языке>)
( алгоритм <точно определенное правило действий>)
)
Уточнения:

  • Может ли объяснение быть пустым? - Да.
  • Может ли быть много объяснений для одного имени? - Да.
  • Могут ли быть идентичные объяснения? - Да.
  • Может ли одно слово входить в объяснение неоднократно? - Да.
  • Предполагается ли одновременная диагностика и циклов, и неопределенностей? - Да.
  • При выводе результата неопределенные имена надо вывести все.

Пример теста:
(( а-к яп <используется для создания> ос <и> сп)
( яп <задается множеством правил для написания> пр)
( ос <комплекс> пр <управляющих решением
задач на имеющемся оборудовании>)
( сп <компилирующая> пр)
( пр <описание> алг <решения задачи на
соответствующем языке>)
( алг <точно определенное правило действий>)
)
   '(( а-к яп ос сп) ( яп пр) ( ос пр) ( сп пр) ( пр алг) ( алг ))
*) Символ ";" - начало комментария.
**) На Lisp 1.5 это определение выглядит изящнее, не требует встроенной функции funcall, при отладке примеров на Clisp-е :
(defun map-el (fn xl)
   (cond
      (xl (cons (fn (car xl) )
         ; применяем первый аргумент как функцию
         ; к первому элементу второго аргумента
      (map-el fn (cdr xl) )
) ) ) )
***) Эта задача была предложена участникам Открытой Всесибирской студеческой олимпиады в 2000 году и оказалась в числе никем не решенных. Многих смутило отсутствие численных ограничений на допустимые данные. При решении задач на Паскале и Си такие ограничения обычно подсказывают выбор структур данных, поэтому отсутствие ограничений было воспринято как риск. Немногочисленные попытки решить задачу привели к отбраковке на минимальных тестах, вызванной тем, что программы не допускали пустой словарь или словарь, выглядящий как перечень терминов без определений. (Впрочем, возможно, это ошибка разработчика тестов. Видимо, первыми должны располагаться тесты на наиболее типичные, естественные случаи.)

****) Решение этой задачи может быть сведено к задаче <Проверка ацикличности графа>.
 
На главную | Содержание | < Назад....Вперёд >
С вопросами и предложениями можно обращаться по nicivas@bk.ru. 2013 г.Яндекс.Метрика