На этом шаге мы рассмотрим несколько алгоритмов внутренней сортировки. 1. Начнем изложение с описания простого предиката для проверки упорядоченности элементов в числовом списке. Пример 1. (DEFUN TESTP (LAMBDA (LST) ; Предикат для проверки упорядоченности по возрастанию ; ; элементов в числовом списке ; (COND ( (NULL LST) T ) ( (COND ( […]
Архив категории ‘Язык программирования LISP’
Сортировка. Общие положения


На этом шаге мы приведем классификацию методов сортировки. Традиционно методы сортировки делят на внутренние и внешние [1, с.10]. Внутренние методы - это такие методы, которые могут применяться с приемлемой производительностью только к тем спискам данных, которые целиком помещаются в основной (оперативной) памяти процессора. Слово список часто обозначает набор записей, расположенных в […]
Смоделированный психиатр


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


На этом шаге мы рассмотрим реализацию задачи сопоставления с образцом. Часто при обработке символьной информации приходится решать вопрос об эквивалентности двух символьных объектов. Такая задача возникает обычно в случае, когда заданы некоторые правила в виде левой части (образец), правой части и условия. Если обрабатываемая символьная информация может быть отождествлена с образцом таким образом, […]
Прагматика языка LISP. Общие положения


На этом шаге мы рассмотрим понятие прагматики. Применительно к знаковым системам, в частности к языкам программирования, говорят об их синтаксисе - правилах образования сообщений, семантике - правилах истолкования сообщения тем, кому оно адресовано, и прагматике, сопоставляющей сообщения целям и намерениям того, от кого они исходят. Заглянем в толковые словари [1-4]. Прагматика […]
Алгоритмы с возвратом


На этом шаге мы рассмотрим реализацию и использование алгоритмов с возвратом. До сих пор мы рассматривали только такие алгоритмы на графах, в процессе работы которых нам никогда не приходилось возвращаться назад. Если, например, при поиске на графе вершина была просмотрена, то она и останется в списке просмотренных вершин до окончания работы алгоритма. […]
Построение остовного дерева связанного графа


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


На этом шаге мы рассмотрим алгоритм вычисления компонент связности. С помощью поиска на графе можно ответить на некоторые вопросы относительно структуры графа. Мы рассмотрим здесь две задачи, связанные с поиском: вычисление компонент связности графа и построение остовного дерева связного графа. Для вычисления компонент связности графа воспользуемся уже написанной функцией DEPTHFIRST. Рассмотрим еще […]
Поиск в ширину


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


На этом шаге мы рассмотрим алгоритм поиска в глубину. Два наиболее распространенных алгоритма поиска на графе называются "поиск в глубину" и "поиск в ширину". Первый из них основан на таком порядке просмотра вершин графа, когда новая вершина, покуда это возможно, выбирается среди соседей текущей вершины. Если среди соседей текущей вершины нет таких, что […]