Однонаправленные процедуры голосования

Размещено на http://www.allbest.ru/

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

Уфимский государственный авиационный технический университет

Кафедра вычислительной математики и кибернетики

Отчет

По курсовой работе

Дисциплина: «Компьютерная обработка экспериментальных данных»

Тема: «Однонаправленные процедуры голосования»

Студент

Бойчук Д.И.

Уфа 2017

Оглавление

1. Содержательная и формальная постановка задачи

2. Структура решения (этапы решения и их взаимосвязь)

Заключение

Список использованных источников

1. Содержательная и формальная постановка задачи

Формальная постановка задачи.

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

Содержательная постановка задачи.

В качестве исходных данных используются индивидуальных упорядочения из множества всех упорядочений сформированные в ходе однонаправленных голосований. Далее, на основе этих данных, находится коллективный выбор при помощи некоторых процедур (процедура Янга, процедура Кемени).

Содержание экрана: на экране отображаются исходные выборки, название процедур и результаты их работы.

Краткие теоретические сведения

В процедурах типа «упорядочение -- выбор» инструкция требует от избирателей упорядочить указанные в бюллетене варианты из множества X. Инструкция обычно требует один из следующих трех типов упорядочений:

а) все варианты должны быть упорядочены избирателем строго, т. е. пронумерованы цифрами 1, 2, ..., n (n = Х) без пропусков так, что вариант, имеющий какой-либо номер считается лучшим для избирателя, чем все варианты, имеющие больший, номер в его упорядочении. Равнозначность, т. е. приписывание двум и более вариантам одного и того же номера, в этом случае не допускается;

б) от избирателей требуется слабое упорядочение вариантов из X, т. е. варианты также должны быть пронумерованы числами 1, 2, ..., однако в этом случае нескольким вариантам может быть приписан одинаковый

номер. Как и в случае (а) вариант, имеющий меньший помер, считается лучшим для избирателя, чем все варианты с большими номерами, а все варианты, имеющие одинаковый номер, считаются одинаково предпочтительными для данного избирателя;

в) избиратель должен не перенумеровать предъявленные ему варианты из Х, а приписать каждому варианту число (не обязательно целое), так что разность этих чисел для двух вариантов трактуется как величина, указывающая «на сколько» (или «в какой мере») один вариант лучше другого, в этом случае фактически от избирателя требуется отображение множества X на числовую шкалу, а не только на ее целочисленные точки 1, 2, 3, ....

процедурах типа УВ упорядочения, полученные от избирателен в одной из указанных выше трех форм, используются для того, чтобы осуществить коллективный выбор Y* ? X. При этом, как уже говорилось выше, предварительно может строиться вспомогательная коллективная структура, либо же коллективный; выбор может осуществляться непосредственно по индивидуальным упорядочениям избирателей без построения промежуточной коллективной структуры.

качестве вспомогательной структуры может быть построена коллективная шкала, либо ориентированный граф, вершинами которого являются варианты из множества X. Затем по этим вспомогательным структурам, применяя то или иное правило П, осуществляется коллективный выбор Y*? Х.

Далее рассматриваются процедуры, в которых вспомогательной структурой является шкала.

Процедура Янга. При использования этой процедуры голосования инструкция разрешает избирателям вырабатывать как строгие, так и нестрогие упорядочения предъявленных вариантов, т. е. избиратель может поставить несколько вариантов па одно и то же место в своем индивидуальном упорядочении. Вспомогательная коллективная шкала строится следующим образом. Каждому варианту х ? Х приписывается числовая оценка р(х), равная числу избирателей в наибольшем подсписке избирателей, в котором этот вариант х лучше любого другого варианта при попарном мажоритарном сравнении. Считается, что вариант х лучше варианта у при попарном мажоритарном сравнении в пределах некоторого подсписка избирателей, если более половины избирателей из этого подсписка предпочитают вариант х варианту у в своих индивидуальных упорядочениях. Так возникает вспомогательная коллективная шкала р, которая используется для нахождения коллективного выбора (например, при помощи правила экстремизмами, т. е. в коллективный выбор включаются варианты, имеющие максимальные оценки по вспомогательной шкале р).

Для каждого варианта х X из предъявления X нахождение числа р(х) осуществляется специальным переборным алгоритмом. С ростом числа избирателей и вариантов в бюллетене переборная задача усложняется, и тогда вспомогательная шкала в процедуре Янга может быть построена лишь с использованием ЭВМ. программа числовой множество

Рассмотрим примеры применения процедуры Янга. Пусть профиль индивидуальных упорядочений трех избирателей имеет вид, представленный в таблице 1, а. Возможные подсписки списка избирателей (И1, И2, И3) изображены в таблице 1, б-ж. Подсчитаем значения р для каждого из вариантов х, y, z и v, т. е. найдем максимальный размер подсписка, в котором данный вариант является лучшим при попарном мажоритарном сравнении с каждым из других вариантов.

Вариант у. Для него р (y)= 3. Действительно, если взять полный список (И1, И2, И3), то у лучше, чем любой другой вариант из предъявления X более чем для половины избирателей: у лучше, чем х для И2 и И3,

Таблица 1 y лучше, чем z для И1, и И3; и y лучше, чем v для всех трех избирателей И1, И2, И3.

Вариант x. Если взять весь список (И1, И2, И3), то вариант х хуже варианта в попарном мажоритарном сравнении (избиратели И2 и И3 предпочитают вариант у варианту х), т. е. р(х)?3.

Возможны три подсписка, содержащих упорядочения двух избирателей: (И1 И2), (И1, И3) и (И2, И3), изображенные на рис. 3.8, б, в, г соответственно. Ми в одном из этих подсписков вариант х не является победителем при попарном мажоритарном сравнении со всеми другими вариантами. Например, в случае подсписка (И1 И3) (рис. 3.8, в) хотя вариант х лучше, чем вариант z и вариант v для обоих избирателей И1 и И3, но вариант х не лучше варианта у в попарном сравнении (избиратель И1 предпочитает вариант х варианту у, но избиратель из предпочитает вариант у варианту х). Аналогично проверяются подсписки (И1, И2) и (И2, И3). Итак, не существует подсписка, содержащего упорядочения двух избирателей, в котором х является лучшим в попарном мажоритарном сравнении с другими вариантами из предъявления X.

Рассмотрим теперь подсписки, состоящие только из одного избирателя. В подсписке, состоящем из избирателя И1 (таблица 1, д) вариант х является лучшим в попарном мажоритарном сравнении с другими вариантами. Следовательно, р(х)= 1.

Аналогичная проверка показывает, что p(z)=l, p(v)=0.

Итак, числовые оценки вариантов, но вспомогательной шкале р следующие: р(y)=3, р(x)=1, p(z)=l, p(v)=0. Применяя правило максимизации к этой шкале, находим коллективный выбор. Согласно процедуре Янга, он состоит из варианта y, т. е. Y* = {у}.

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

Выработка коллективного упорядочения производится следующим образом. Рассматривается множество L, содержащее все возможные упорядочения вариантов из X. Каждому упорядочению l ? L приписывается числовая оценка о (l), характеризующая степень близости этого упорядочения l к профилю индивидуальных упорядочений избирателей {Рi}, т. е. строится вспомогательная шкала, но уже не на вариантах (как в предыдущих процедурах типа УВ), а на всех возможных упорядочениях вариантов. Эта шкала строится следующим образом:

где в (х, у) -- число избирателей, предпочитающих вариант х варианту у в профиле индивидуальных упорядочений {Рi}, а

Поясним, почему такая оценка о(l) является условной мерой близости упорядочения l к профилю индивидуальных упорядочений избирателей {Pi}. Для каждой нары вариантов х, у соответствующее слагаемое в этой оценке тем больше, чем большее число избирателен взаимно располагают варианты х и у так же, как они расположены в упорядочении l, в связи с тем, что такие

слагаемые суммируются по всем возможным парам вариантов, значения о (l), подсчитанное, но формуле (1), характеризует близость упорядочения l и профиля индивидуальных упорядочений {Pi}.

Так возникает вспомогательная коллективная шкала на множество L всех возможных упорядочений вариантов из X. В качестве вспомогательного коллективного упорядочения выбирается упорядочение l*, имеющее максимальную оценку о(l*), т. е.

,

Это упорядочение может не совпадать ни с одним из индивидуальных упорядочений избирателей. По этому вспомогательному упорядочению l* и осуществляется коллективный выбор. Применение этой процедуры требует решения громоздких переборных задач и практически невозможно без использования ЭВМ.

Приведем пример нахождения числовой оценки о(l), приписываемой упорядочению l ?L, для простого случая, когда число избирателей N = 3 и число вариантов n = 3. Рассмотрим профиль индивидуальных упорядочений избирателей, представленный в таблице 2. Множество всевозможных упорядочений L состоит из шести элементов, приведенных в таблице 3: l1, ..., l6.

Подсчитаем по формуле (3.1) значения о(li) для всех возможных упорядочений: о(l1) =6; о(l2) =5; о(l3) =5, о(l4) = 4; о (l 5) = 4; о(l6) =3. Таким образом, в качестве вспомогательного коллективного упорядочения l* принимается упорядочение l1, имеющее максимальную оценку по шкале о. В коллективный выбор включается вариант, лучший в упорядочении l1, т. е. вариант х.

2. Структура решения (этапы решения и их взаимосвязь)

Ввод данных - индивидуальных упорядочений

Вычисление коллективного выбора

Процедура Янга Процедура Кемени

Вывод результатов на экран

Обзор и анализ методов решения

Вычисление коллективного выбора согласно процедуре Янга

Обобщенный алгоритм:

Формируется список всех подсписпосков избирателей (например, для {I1, I2, I3} список подспиков {{I1}, {I2}, {I3}, {I1, I2}, {I1, I3}, {I2, I3}})

Подсчитаем значения рi для каждого из вариантов т. е. найдем максимальный размер подсписка, в котором данный вариант является лучшим при попарном мажоритарном сравнении с каждым из других вариантов.

Формируется вспомогательная шкале р

Применяя правило максимизации к этой шкале, находим коллективный выбор

Вычисление коллективного выбора согласно процедуре Кемени

Обобщенный алгоритм:

Формируется Множество всевозможных упорядочений L

Вычисляется числовая оценка о(l), приписываемой упорядочению l ?L по формуле

,

в (х, у) -- число избирателей, предпочитающих вариант х варианту у

=1 если в l вариант х лучше, чем у

=0 если в l вариант х не лучше, чем у

Вычисляем максимальную оценку о(l*)

,

В качестве вспомогательного коллективного упорядочения выбирается упорядочение l*

3. Руководство пользователя

После запуска программы на экране появится следующее окно, на котором отображается результат работы процедуры Янга

результат работы процедуры Кемени 

Заключение

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

Список использованных источников

1. Вольский В.И., Лезина З.М.. Голосование в малых группах.

Размещено на Allbest.ru