Задача - сортировка
Cтраница 3
Заметим, что при таком способе построения множества S каждый элемент ( xi, yi) является максимальным. XN, что дает решение задачи сортировки. [31]
Метод, альтернативный поразрядной сортировке, предусматривает просмотр байтов в направлении справа налево. На рис. 10.14 показано, как задача сортировки трехбуквенных слов может быть решена за три прохода по файлу. [32]
Для любого комбинаторного источника, порождающего некоторое подмножество слов множества А, в Рт ( А В) найдется отображение, решающее задачу заданного сжатия производимой этим источником информации. Помимо задач сжатия и поиска универсальные множества нумераторов полезны в задачах сортировки данных, передачи информации по каналам с множественным доступом. [33]
Задача триангуляции простого многоугольника с п вершинами состоит в выборе п - 3 непересекающихся диагоналей, разбивающих его внутренность на я - 2 треугольника. Тем самым показывается, что задача триангуляции не такая сложная, как задача сортировки. Полученный результат позволяет улучшить алгоритмы для решения некоторых других задач вычислительной геометрии, включая проверку многоугольника на простоту. [34]
На этом заканчивается наше обсуждение сложности задачи. Прежде чем закончить эту тему, заметим, что двумерные варианты как задачи об упорядоченной выпуклой оболочке ВО1, так и задачи о крайних точках ВО2 имеют тесную связь с задачей сортировки. Действительно, задача ВО1 явным образом связана с ней посредством прямого сведения, в то время как связь ВО2 осуществляется через мощность симметрической группы. Эта связь является довольно глубокой, и в дальнейшем в этой главе мы будем часто обращаться к ней. [35]
То, что вершины многоугольника, являющегося выпуклой оболочкой, следуют в определенном порядке ( в действительности мы можем говорить об упорядоченной выпуклой оболочке), указывает на естественную связь с задачей сортировки. В самом деле, следующая теорема устанавливает тот факт, что любой алгоритм решения задачи ВО1 должен быть способен выполнять сортировку. [36]
В методах сортировки, обсуждавшихся в предыдущем разделе, мы полагали, что таблица умещается в быстродействующей внутренней памяти. Например, часто бывает необходимо сортировать отдельные предметы во время исчерпывающего поиска ( гл. Однако задача сортировки таблицы, которая слишком велика для основной памяти, служит хорошей иллюстрацией работы с данными большого объема, и поэтому в этом разделе мы обсудим важные идеи внешней сортировки. [37]
Сначала будет рассмотрен случай, когда элементы, подлежащие сортировке, представлены целыми числами или ( что почти эквивалентно) словами в конечном алфавите. В этой ситуации мы увидим, что сортировку можно выполнить за линейное время. Затем изучим задачу сортировки, когда специальные свойства чисел или слов не используются и приходится строить разветвления в программе только на основе результатов сравнений сортируемых элементов. При этих условиях необходимо 0 ( п log n) сравнений; это же количество сравнений достаточно для упорядочения последовательности из п элементов. [38]
 |
Структурная схема устройства автоматического опознавания. [39] |
Устройство для опознавания грузов по высоте показано на рис. 7.24. Ящики 6 подаются рольгангом 7 из упаковочного отделения для транспортировки на склад готовой продукции. Участки склада закреплены за определенными грузами. При автоматизации загрузки склада возникла задача сортировки ящиков в зависимости от нх габаритных размеров. Задача сводится к опознаванию ящиков только в зависимости от их высоты. Опознавание производится электроконтактньш способом. [40]
Здесь следует отметить, что такую двухшаговую процедуру можно было применить к любой из рассматривавшихся нами ранее задач. Например, сортировку списка можно выполнять, генерируя произвольный порядок элементов исходного списка и проверяя, не является ли этот порядок возрастающим. Не относит ли это рассуждение задачу сортировки к классу NP. Разница между классом Р и классом NP в том, что в первом случае у нас имеется детерминированный алгоритм, решающий задачу за полиномиальное время, а во втором мы такого алгоритма не знаем. [41]
Уместно сделать следующее замечание. Если смотреть более строго, то аналогия будет довольно полной, когда все заданные точки являются вершинами выпуклой оболочки. Это вполне понятно, так как в задаче сортировки нет аналога для внутренних точек выпуклой оболочки. [42]
Характерной особенностью проектирования АСУ является изменение веса задач каждого класса в системе на соответствующем этапе ее создания. По мере разработки системы поток системных задач и задач оперативного взаимодействия увеличивается и становится более разнообразным. Поток задач по отладке программ уменьшается, а задач сортировки, оптимизации и других увеличивается. По окончании разработки АСУ устанавливаются определенные весовые соотношения между классами задач. [43]
Одним из условий удовлетворительного обессоливания нефтей является раздельное обеосоливание каждого сорта нефти. В связи с тем, что нефти на завод поступали в самых разнообразных смесях, прежде всего необходимо было добиться тщательной и сортировки, что требовало дополнительного количества емкостей. В результате перевода установок АВТ, а затем и комбинированных термических крекингов на прямую связь с ЭЛОУ было высвобождено значительное количество емкостей, что и обусловило успешное решение задачи сортировки нефтей. [44]
Необходимо помнить, что в случае небольших массивов те алгоритмы, которые сформулированы в задаче 628, дают вполне удовлетворительное решение задачи. При больших п требуется тщательно изучить все особенности конкретной ситуации и, исходя из этого, подобрать алгоритм. Задачи сортировки массивов возникают не только в связи с числовыми массивами. Тип элемента может быть довольно сложным, и надо учитывать, во что обходится сравнение и перемещение элементов в том или ином случае. [45]
Страницы: 1 2 3 4