Cтраница 3
Для приближенного решения задачи о сумме элементов подмножества имеется и другой алгоритм, который также не лишен жадности. Этот алгоритм выдает тем лучший результат, чем дольше он работает, и если его можно прогнать N 1 раз, то выданный им результат будет оптимальным. Причина этого в том, что на каждом проходе он вовлекает в рассмотрение новые случаи. На первом проходе алгоритм начинает с пустого множества и добавляет в него элементы в убывающем порядке до тех пор, пока не будет достигнут предел или не будут опробованы все элементы входного списка. На втором проходе алгоритм начинает со всевозможных одноэлементных подмножеств и добавляет к ним элементы списка. На третьем проходе изучаются все двухэлементные подмножества. Число проходов ограничено только временем, отведенным на работу алгоритма. Если при списке из 10 элементов удается выполнить 11 проходов, то оптимальное решение будет найдено. Для списка из 10 элементов на первом проходе имеется единственное пустое подмножество, на втором проходе есть 10 одноэлементных подмножеств, на третьем имеется 45 двухэлементных подмножеств. Больше всего начальных подмножеств встречается на шестом проходе - это 252 пя-тиэлементных подмножества. Поэтому хотя сам процесс и выглядит простым, он все равно требует значительного времени. [31]
Обменом информацией между интерпретатором L4 и внешними устройствами ( телетайпом и телефонными линиями связи) управляют специальные программы - драйверы устройств. Имеются две программы, с помощью которых организуется работа с драйверами. Одна программа служит для ввода литер через указанный драйвер, другая - для вывода литер через указанный драйвер. Когда основная ЭВМ начинает передавать в терминал блок графических данных, инициируется программа, которая преобразует поступающую строку литер в команды L4 и помещает их во входную таблицу сообщений и во входной список данных. Программа завершает работу, когда заканчивается передача блока. [32]
Заметим, что ПГ являются ациклическими, и поэтому инструкция, соответствующая вершине в ПГ, после выполнения удаляется, поскольку данные на ее входящих дугах появиться не могут. Заметим также, что набор все необходимые аргументы соответствует входам вершины ПГ, на которых наличие данных обязательно, чтобы операция этой вершины могла быть выполнена. Эти входы задаются правилами, специфическими для каждого типа инструкций. В случае инструкции типа слияние необходим первый ( управляющий) вход, а также второй ( Т) или третий ( F) в зависимости от того, имеется ли на первом входе значение true или false соответственно. В случае примитивной функции входы, на которых требуется наличие данных, соответствуют определяемым б-правилами строгим аргументам этой функции. Таким образом, в каждом случае все из необходимых элементов входного списка известны. [33]