течение 1 единицы времени равна р, где 0<р<1. В течение единицы времени никогда не появляются два и более клиентов. Последите за переполнением очереди как за функцией от р.

2.3.10. Замкнутые связанные списки. На рис. 2.3.18 приведен пример замкнутого связанного списка. Можете ли вы придумать какое-либо применение для этой структуры данных. Попытайтесь реализовать одну из ваших идей.

2.3.11. Работа со связанными списками. Разработайте алгоритмы, выполняющие для списков с одной связью следующее:

(а) Преобразование связанного списка в замкнутый связанный список (см. упр, 2.3.10).

(б) Обьединение двух списков, в каждом из которых ячейки INFO упорядочены лексикографически.

(в) Преобразование связанного списка в последовательный список (обычный одномерный массив).

2.3.12. Упакованное десятичное представление. Разберитесь, что имеется в виду, когда говорят «упакованное десятичное представление целых чисел» (см. [77], стр. 37), Каковы преимущества и недостатки этого представления?

*L2.3.13. Шах. Напишите программу, которая будет считывать шахматную позицию и определять, не находится ли один из королей под шахом. Можно затем попытаться определить, не является ли шах матом.

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

**L2.3.15. Кроссворды. Напишите программу составления кроссвордов. Предположим, что исходными данными является конфигурация 6x6 (некоторое расположение пустых и заполненных квадратов) и список слов, состоящих из шести или менее букв. Результатом должно быть расположение этих слов, образующее общепринятый кроссворд, или сообщение о том, что такая конфигурация невозможна.

*2.3.16. Рекурсивные деревья. Разработайте алгоритм построения единстаенного пути в рекурсивном дереве Т между произвольно заданными вершинами и и v, используя компактное линейное представление на рис. 2.3.17. Указание: Можно построить алгоритм, просматривающий это представление справа налево один раз.

2.4. Элементарные лонятия теории вероятностей и статистики

Очень много важных задач содержат в той или иной степени неопределенность. Представляющие интерес величины заранее непредсказуемы, а имеют случайный, характер, который должен быть отражен в любой корректной модели. Модели такого типа называются ве-роятностными.

В данном разделе мы будем рассматривать некоторые понятия из теории вероятностей и статистики. Ниже кратко описаны некоторые применения этого аппарата к разработке и анализу алгоритмов.

1. Анализ средней трудоемкости алгоритма. Предположим, что У нас есть алгоритм (алгоритм S), оптимизирующий (в некотором смьгсле) порядок выполнения заданий на вычислительной машине. К числу важнейших факторов, определяющих время работы алгоритма, относятся общее число (Л) и типы заданий, ожидающих выполне-

ния. Если все задания простого типа, то алгоритм S может построить расписание за время 0{N). Но если все задания очень сложные, то алгоритм S требует 0{N) времени. Предположим, что между этими

Рис. 2.3.18.

Крайними случаями имеется 12 различных типов заданий и что пакеты, как правило, содержат смесь из заданий различных типов. Насколько хорош наш алгоритм? Чтобы ответить на этот вопрос, нам нужно знать, каково среднее, представительное множество заданий. Затем мы должны решить, насколько хорошо работает алгоритм в среднем. Отсюда следует необходимость точно определить, что такое «среднее». Возможно, что худший случай 0{N) для операционной системы неприемлем; например, может оказаться, что вся система будет бездействовать в ожидании, пока подпрограмма не составит расписание. Если худший случай встречается редко и средняя трудоемкость алгоритма равна 0{N/), то можно использовать алгоритм S в операционной системе. С другой стороны, если средний режим 0{N), мы, по-видимому, будем вынуждены применить какой-то другой быстрый, грубый, эвристический алгоритм, не гарантирующий оптимального расписания. На этом примере отчетливо виден ряд важнйх моментов, связанных с анализом алгоритмов.

2. Моделирование. Одним из самых важных применений вычислительной машины является ее использование в качестве средства проведения управляемых экспериментов на сложных реальных системах за короткое время и при относительно низких затратах. Для этого строят алгоритм, моделирующий реальную систему. Во многих отношениях это крайнее средство. К моделированию прибегают, как правило, когда задачи безнадежно превышают наши аналитические возможности и сочетают в себе трудоемкость и неопределенность. В сущности, все серьезные модели вероятностны.

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

4. Алгоритмы принятия решений. Вычислительная машина становится все более популярной в мире коммерции и государственного управления как помощник при решении важных вопросов. Все задачи

в этой области существенно включают процесс принятия решений в условиях неопределенности.

Рассмотрим, например, следующую задачу. В текущий момент гуэавительство поддерживает ряд административных и обслуживающих агентств. В условиях катастрофического уменьшения бюджета некоторое число агентств необходимо упразднить или сильно ограничить нх в средствах. Имеется огромный объем данных, относящихся к прошлой, настоящей и будущей деятельности этих агентств. Как принять решение? Один из самых обещающих количественных методов разрешения таких проблем известен как теория статистических решений Байеса. К сожалению, в этой теории совершенно отсутствуют хорошие вычислительные алгоритмы. В настоящее время ее полезность ограничивается относительно простыми задачами.

5. Генерация случайных чисел. Почти во всех предыдущих приложениях теории вероятностей и статистики требуется средство внесения в данные неопределенности. Хотелось бы, если возможно, делать это с помощью механизма, внутреннего по отношению к самой вычислительной машине, избегая дорогостоящей и потребляющей много времени внешней активности. Разработка и анализ хороших алгоритмов генерации случайных данных - это серьезная самостоятельная проблема.

Мультипроцессорные системы

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

Каждая вероятностная модель формулируется в терминах эксперимента. Эксперимент - это любое точно определенное действие. В нашем примере эксперимент состоит в том, чтобы определить, сколько в системе свободных процессоров. С каждым экспериментом мы можем связать множество исходов. Пометим наши пять процессоров целыми числами от 1 до 5. Один возможный исход эксперимента может быть тогда обозначен вектором с 5 компонентами (1,0, 1,0, 0), что означает состояние системы, когда процессоры 1 и 3 заняты, а процессоры 2, 4 и 5 свободны. Если система находится в этом состоянии, то программа будет принята. Множество всех возможных исходов называется пространством элементарных событий эксперимента. Используя 5-компонентное представление, можно увидеть, что в нашем мультипроцессорном эксперименте имеется 2 элементов пространства элементарных, событий. Ниже все они явно перечислены: