Задачи по программированию  

Разные задачи

к содержанию задачника

1. Исследование потоков вызовов. Сгенерировать простейший поток с интенсивностью λ = 3 заявки/мин, состоящий из N = 1000 заявок.
   Провести статистическое исследование: найти среднее значение, моду, дисперсию и среднеквадратическое отклонение длительности паузы между вызовами на всем интервале наблюдения; построить гистограмму распределения длительности паузы между вызовами и сопоставить ее графически с теоретическим распределением; обосновать выбор величины шага при построении гистограммы; проверить гипотезу о виде распределения.
   Построить зависимость среднего значения и дисперсии количества вызовов, приходящихся на интервал 5 минут в зависимости от общей длительности наблюдаемого простейшего потока с интенсивностью λ = 3 заявки/мин. Общую длительность потока рассматривать в пределах от 15 мин до 24 часов
2. Одноканальная СМО с отказами представляет собой одну телефонную линию, на вход которой поступает простейший поток вызовов с интенсивностью 0,4 вызов/мин. Средняя продолжительность разговора 3 мин, время разговора имеет показательное распределение. Определите абсолютную и относительную пропускные способности СМО, а также вероятность отказа в обслуживании. Сравните пропускную способность СМО с номинальной, которая была бы, если бы разговор длился ровно 3 минуты, а заявки шли одна за другой непрерывно.
3. Исследование СМО с отказами. Рассчитать прибыль П от работы СМО с отказами в зависимости от числа каналов при известном доходе от обслуживания одной заявки Д и расходе на содержание одного канала Р. Интенсивность входящего потока заявок λ и среднее время обслуживания t_обс являются параметрами алгоритма. В результате работы программы должен быть график зависимости П от числа каналов, оптимальное число каналов и само значение максимальной прибыли.
4. Исследование СМО с очередями. В гипермаркете 100 касс, одновременно работают не все. Постройте график зависимости минимально необходимого числа работающих касс от суммарного потока посетителей на входе гипермаркета. Среднее время обслуживания одного покупателя на кассе 4 минуты. Посетители сами выбирают кассу таким образом, что загрузка касс примерно одинакова. Критерий оптимизации – средняя длина очереди не более 3 человек. Второй вариант: критерий оптимизации – среднее время ожидания в очереди не более 10 минут. Дополнительно требуется построить гистограмму вероятности времени ожидания в очереди. Постройте графики зависимости минимально необходимого числа операторов центрального почтового отделения от потока посетителей. Среднее время обслуживание одного человека – 5 минут. Среднее время терпения в очереди 40 минут. Очередь не ограничена. График привести для системы с общей очередью ко всем окнам и с отдельной очередью к каждому окну. Критерий – число ушедших без обслуживания не более 1, 3, 5 в час.
5. Задача Прима-Краскала (жадный алгоритм) - L. Дана плоская страна и в ней n городов. Нужно соединить все города телефонной связью так, чтобы общая длина телефонных линий была минимальной.
   Уточнение задачи. В декартовой системе координат положение i-го города, i = 1,..,n, задано парой координат (x[i],y[i]). d[i,j] - декартово расстояние между i-ым городом и j-ым городом , j=1,...,n. В задаче речь идет о телефонной связи, т. е. подразумевается транзитивность связи: если i-й город связан с j-ым, а j-ый с k-ым, то i-й связан с k-ым. Подразумевается также, что телефонные линии могут разветвляться только на телефонной станции, а не в чистом поле. Наконец, требование минимальности (вместе с транзитивностью) означает, что в искомом решении не будет циклов. В терминах теории графов задача Прима-Краскала выглядит следующим образом:
   Дан граф с n вершинами; длины ребер заданы матрицей (d[i,j]), i,j = 1,..,n. Найти остовное дерево минимальной длины. Как известно, дерево с n вершинами имеет n-1 ребер. Каждое ребро надо выбирать жадно (что бы ни возникали циклы).
   Необходимо написать программу для решения задачи Прима-Краскала. Предусмотреть возможность построения карты городов и их связей пользователем.
6. Для данного числа $q=891622222219$ постройте простое число $p$ вида $p=qr+1$, где $q+1\le r\le 4q+2$, по методу Моурера. Для проверки простоты примените вероятностный тест Рабина-Миллера. Вероятность "простоты" $p$ должна быть не менее $0,999$.
7. Звездочки. Астрономы часто изображают карту звездного неба на бумаге, где каждая звезда имеет декартовы координаты. Пусть уровнем звезды будет количество других звезд, которые расположены на карте не выше и не правее данной звезды. Астрономы решили узнать уровни всех звезд. Требуется определить, сколько звезд каждого уровня имеется на карте.
8. Хорды. На окружности отмечены $2N$ различных точек, пронумерованных против часовой стрелки от 1 до $2N$. Петя нарисовал $N$ хорд, $i$-ая из которых соединяет точки с номерами $a_i$ и $b_i$. При этом каждая точка является концом ровно одной хорды. Теперь Петя заинтересовался, сколько пар хорд пересекаются. Помогите ему определить это количество.