Задачи по Python с решениями

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

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

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

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

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

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

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

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

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

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