Спирина, М.С. Дискретная математика

Применение комбинаторики. Комбинаторный анализ имеет практическое применение в про­ граммировании при вычислениях дискретных конечных математических структур. Задача 7. Служба занятости населения рас­ полагает базой данных из п записей, каждая из которых содержит одно предложение —на ­ личие вакансий, и один запрос — что востре­ бовано на рынке труда. Необходимо найти ва­ риант трудоустройства безработных в соответ­ ствии с имеющимися вакансиями. На языке математики это означает, что нужно найти такие пары записей, в которых предложение первой записи совпадает с запросом вто­ рой, и наоборот. Какое количество вариантов пересмотрит ком ­ пьютер при поиске таких пар? Решение. Так как надо учесть все п записей предложений, а также п - 1 запросов, то при сравнении каждого предложения с Рис. 1.18. Точки пе­ ресечения диаго­ налей многоуголь­ ника каждым запросом потребуется л (и -1 ) сравнений. Можно узнать время t, затраченное на обработку информации. Если проверка одного варианта осуществляется за одну миллисекунду, то при заданном п соответствующие результаты можно представить в табл. 1.7. Для конкретной службы занятости эти результаты означают, что машинная обработка запросов ста клиентов потребует всего 5 с непрерывной работы компьютера. Если на бирже труда 20 000 безработных, то необходимо 55,6 ч для непосредственного поис­ ка вариантов трудоустройства с помощью ЭВМ. Эти знания помо­ гут руководителям службы определить потребность в кадрах и ЭВМ в соответствии с реальной обстановкой в конкретном городе. Точ ­ нее говоря, мы получили ответ на вопрос, какое минимальное число сравнений сделает компьютер. Но многое зависит от квали­ фикации программиста, писавшего программу: не заставил ли он машину делать дублирующие сравнения. Т а б л и ц а 1.7 Время поиска вакансии в зависимости от объема базы данных п 100 1000 10000 15 000 20000 п(п - 1) 2 4950 499500 4999500 112492500 19999000 t, с 4,95 499,5 4999,5 112492,5 199990 U ч 0,0014 0,14 1,4 31,2 55,6 51