Модель колективного вибору

РефератДопомога в написанніДізнатися вартістьмоєї роботи

Модель колективного вибору (реферат, курсова, диплом, контрольна)

Кафедра «Інформаційні системи та мережі».

Фах «Інтелектуальні системи прийняття рішень».

Базовий напрямок «Комп'ютерні науки».

ЗАВДАННЯ НА КУРСОВУ РОБОТУ.

із предмета «Методи підтримки прийняття рішень».

студентки грн. ІСМ-5М.

Шаховської Наталі.

1. Тема: «Модель колективного вибору рішень».

2. Завдання: розробити програму для демонстрації роботи одного із методів голосування.

3. Зміст пояснювальної записки.

1 Змістовна постановка задачі.

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

3 Математичні методи розв’язку.

4 Опис алгоритму.

4.1 Визначення переможця Борда.

4.2 знаходження оцінки Копленда.

4.3 Алгоритм визначення переможця за правилами Борда чи Копленда.

5 Опис програми.

5.1 Вибір технології програмування.

5.2 Структура програми.

5.3 Інструкція користувачеві.

6 Контрольний приклад.

Висновки.

4. Перелік графічного матеріалу.

Кількість малюнків — 5.

Завдання видане: 10.09.99.

Завдання видав: доц. Катренко А. У. ______________________.

Завдання прийняла: Шаховська Наталю ______________________.

Львів — 99.

ЗМІСТ.

Вступ 4.

1 Змістовна постановка задачі 6.

2 Формальна постановка задачі 10.

3 Математичні методи розв’язку 18.

4 Опис алгоритму 23.

4.1 Визначення переможця Борда 23.

4.2 Знаходження оцінки Копленда 25.

4.3 Алгоритм визначення переможця за правилами Борда чи Копленда 28.

5 Опис програми 31.

5.1 Вибір технології програмування 31.

5.2 Структура програми 33.

5.3 Інструкція користувачеві 35.

6 Контрольний приклад 37.

Висновки 39.

Список літератури 40.

Додатки 41.

Програму 41.

Результати роботи програми 45.

ВСТУП.

«Демократія як метод керування.

використовує результати суспільних.

рішень громадян на виборах й рішень.

законодавців у представницьких органах".

(Рікер [1982]).

Більшість суспільних розподілених рішень (таких, як податки й суспільні витрати) приймається на основі голосування. Вибори також використовуються для поповнення багатьох суспільних закладів. Тут ми маємо важливі приклади чистих суспільних продуктів (наприклад, усі громадяни даного міста без яких-небудь винятків беруть доля в «споживанні» свого міра), що вибираються на основі голосування й без побічних платежів.

Починаючи із політичної філософії Просвітництва, вибір правил голосування був головною етичною проблемою, заговорили українською у «язаною із додатками, що далеко йдуть, для функціонування більшості політичних інститутів. Дебати про справедливість різноманітних методів голосування почалися із досліджень де Борда [1781] й Кондорсе [1785]. У 1952 році Ерроу запропонував формальну модель, що протягом трьох десятиліть аналізувалася в численних роботів математичної орієнтації по так званому колективному виборі.

Формально правило голосування вирішує завдання колективного ухвалення рішення, у котрої декілька індивідуальних агентів (виборців) повинні спільно вибрати один з декількох результатів (також званих кандидатами), щодо яких їхні думи розходяться. Будемо припускати, що кінцева множина N виборців винна зверни одного кандидата із кінцевої множини А. Для простоти припустимо, що індивідуальні думи (чи переваги) не припускають випадків байдужності. Кожна така перевага є довільним лінійним порядком на А.

Правило голосування вибирає кандидата на основі повідомлених порядкових переваг й лише на основі цих переваг. У цьому істотна відмінність від моделей, у які гроші і інші продукти дозволяли здійснювати довільно малі компенсації для агентів. Голосування не припускає вчинки між двома кандидатами інакше, ніж за рахунок можливого обрання третього кандидата.

Якщо кандидатів лише два, то звичайне правило голосування більшістю голосів безперечно є найбільш справедливим методом. Цей принцип більшості - вихідний пункт процесу демократичного прийняття рішень. Він був явно сформульований два сторіччя тому, а його основа є набагато более древньою. Аксіоматична формалізація принципу більшості запропонована Меєм.

Розгляду методів голосування й втіленню в однієї із них й присвячена дана курсова робота. Буді проведена порівняльна характеристика різних методів голосування, й за допомогою контрольного приклада продемонстрована робота одного із них.

ЗМІСТОВНА ПОСТАНОВКА ЗАДАЧІ.

Завдання, яку переносити переді мною у даній курсовій роботі - забезпечити процес виборів, тобто кінцева множина N виборців винна зверни одного кандидата із кінцевої множини А. Обов’язковою умовою є обрання єдиного кандидата. Для простоти припустимо, що індивідуальні думи (чи переваги) не припускають випадків байдужності. Кожна така перевага є довільним лінійним порядом на, А (тобто повне транзитивне і асиметричне бінарне ставлення). Це припущення не призводить до істотних втрат загальності.

Правило голосування являє собою систематичне рішення, яку у всій повноті опирається на індивідуальні думи. Позначимо через L (А) множину лінійних порядків на А, тоді правило голосування є відображенням L (А)N в А. Ті, що правило голосування може бути визначене для будь-якої мислимої конфігурації переваг, виражає фундаментальний принцип свободи думок: кожний виборець має право ранджувати кандидатів будь-яким чином. Проте в деяких моделях голосування, що містять економічні змінні чи невизначені результати, можна припускати, що переваги виборців задовольняють деякій загальній умові. Це особливо зручно при стратегічному аналізі голосування й при агрегуванню переваг.

Нехай дано як контрольний приклад наступний профіль для 9 виборців й 5-ти кандидатів:

1 4 1 3.

e c.

a e.

з e.

У кожному стовпці кандидати розташовані у порядку зменшення їхні значущості для кожної групи виборців. Тобто, для Першого стовпця (групи виборців, що складається із однієї людини) можна визначити переваги наступним чином: група виборців, що складається із однієї особини, вважає кандидата a найкращим. На іншому місці смердоті ставлять кандидата b, на третьому місці з й т.д. аналогічно кандидати ранджовані у кожній групі.

Завдання: визначити єдиного переможця виборів.

Існує багато способів визначення переможця. Вони будуть описані й відповідним чином порівняні у наступних розділах.

Зазначимо тепер, що дана курсова робота присвячена розгляду й втіленню у програму методу Копленда й порівнянню отриманого результату з результатом за методом Борда.

Визначимо правило Копленда.

Порівняємо кандидата a із будь-яким іншим кандидатом x. Нарахуємо йому +1, якщо для більшості a краще за x, -1, якщо для більшості x краще за a, й 0 при всіх x, x? a, одержуємо оцінку Копленда для a. Обираємо кандидат, назв переможцем за Коплендом, з найвищою такою оцінкою [див. 1, ст. 321].

У даному правилі не вказано, що робити у тому випадку, коли знайдуться два чи понад кандидати із однаковою оцінкою Копленда. Припустимо, що обереться тієї кандидат, ім'я й прізвище якого стоїть найближче за списком. Це припущення порушує правило нейтральності [див. 1, ст. 329], але й, як якщо доведено у наступних розділах, кожне правило голосування Копленда є найбільш наочним й легким для комп’ютерної реалізації.

Правило Борда: кожний виборець повідомляє свої переваги, ранджуючи p кандидатів від найкращого до найгіршого (байдужість забороняється). Кандидат не одержує очок за останнє місце, одержує одне очко за передостаннє місце й т.д., одержує p-1 очко за перше місце. Перемагає кандидат з найбільшою сумою очок. Він називається переможцем за Борда.

Тут так і не вказується, що робити при рівності очок, тобто також може порушуватись умова нейтральності.

Охарактеризуємо вище поставлену задачу.

Її критерієм якості є максимізація оцінки Копледа (Борда).

Обмеженнями виступають переваги виборців й їхнього ранджування кандидатів. як якщо вказано далі, фактично потрібно накладати також обмеження й на кількість виборців та кількість кандидатів. Проте це обмеження не є суттєвим, так як завжди при голосуванні можна провести поділ на округи.

За рівнем складності це є завдання Р-типу. Час розв’язку даної задачі становить t0=a0+a1x+… +anxn й залежить від кількості груп виборців та кількості кандидатів.

Знаходження переможця за правилами Копленда й Борда є найпростішими за своєю структурою, оптимальні за Парето, анонімні, нейтральні (якщо не вказувати, що робити при рівності очок). Крім того, правило Борда иакож задовольняє аксіомі участі й поповнення (смердоті будуть розглянуті у наступному розділі).

Оптимальність за Парето:

Якщо кандидат a для всіх кращий від кандидата b, то b не може бути обраний.

Анонімність:

Імена виборців не мають значення — якщо два виборці поміняються голосами, то результат виборів не зміниться.

Нейтральність:

Імена кандидатів не мають значення. Якщо ми поміняємо місцями кандидатів, а й b у перевазі шкірного виборця, то результат голосування зміниться відповідно (якщо раніш вибирався бо тепер якщо вибиратися b й навпаки; якщо вибирався деякий x, відмінний від, а й b, те й якщо обраний).

Монотонність:

Припустимо, що, а вибирається (серед переможців) при даному профілі й профіль змінюється лише так, що положення, а поліпшується, а відносне порівняння парі будь-яких інших кандидатів для будь-якого виборця залишається незмінним. Тоді а як й раніше якщо обраний (знову серед переможців) для створення нового профілю.

ФОРМАЛЬНА ПОСТАНОВКА ЗАДАЧІ.

Приведемо ще раз завдання даної курсової роботи: використовуючи профіль переваг виборців, визначити єдиного переможця із множини заданих. Повинна існувати можливість перевірки коректності задання профілю. Обмеженнями на завдання є відсутність байдужості та ранжування кандидатів у суворому порядку.

Опишемо методи голосування, котрі можуть використовуватись для розв’язання даної задачі й наведемо ряд основних визначень й теорем.

Правило відносної більшості. Кожний виборець віддає свої голос найкращому для собі кандидату. Обирається кандидат, згаданий у найбільшій кількості бюлетенів. Це правило може суперечити думці більшості (див. 1, приклад 9.1).

Визначення 2.1. Правило Борда. Кожний виборець повідомляє свої переваги, ранжуючи р кандидатів від кращого до гіршого (байдужність забороняється). Кандидат не одержує очок за останнє місце, одержує одне очко за передостаннє й так далі, одержує р-1 очок за перше місце. Перемагає кандидат з найбільшою сумою очок. Він називається переможцем за Борда.

Ми не уточнюємо, що робити при рівності очок.

Визначення 2.2. Для заданого профілю переваг переможцем за Кондорсе називається кандидат, а (з необхідністю Єдиний), що перемагає будь-якого іншого кандидата при парному порівнянні за правилом більшості:

будь-кого b? а виборців, що вважають, а кращим за b, більше, ніж тихий, хто вважає, що b кращим за а.

Заможне за Кондорсе правило вибирає переможця за Кондорсе, якщо такий існує.

Відсутність переможця за Кондорсе є знаменитим «парадоксом голосування». як часто може спостерігатися парадокс голосування? У загальному випадку ймовірність ?(p, n) того, що переможця за Кондорсе не існує при р кандидатів й п виборцях, зростає по р й зростає за кількістю виборців від п до n+2. Це може бути перевірене на основі обчислення ?(п, р) для малих значень п й р, але й в загальному випадку це твердження залишається недоведеним припущенням.

Парадокс голосування стає майже достовірною подією, коли число кандидатів стає достатньо великим при фіксованому п. Якщо число виборців стає достатньо великим при фіксованому р, то гранична ймовірність ?(p) може бути оцінена за Фішберн [1984]:

Яка справедлива із точністю до половини відсотка при р?50.

Визначення 2.3. Правила голосування із підрахунком очок.

Фіксуємо послідовність дійсних чисел, що не спадає.

s0?s1???sp-1 при s0.

Виборці ранжують кандидатів, причому s0 очок дається за останнє місце, s1 — за передостаннє й так далі. Обирається кандидат з максимальною сумою очок.

Визначення 2.4. Правило Копленда. Порівняємо кандидата, а із будь-яким іншим кандидатом x. Нарахуємо йому +1, якщо для більшості а краще за x, -1, якщо для більшості x краще за а, й 0 при рівності. Сумуючи загальну кількість очок по усім x, х? а, одержуємо оцінку Копленда для а. Обирається кандидат, назв переможцем за Коплендом, з найвищою із таких оцінок.

Визначення 2.5. Правило Сімпсона. Розглянемо кандидата а, будь-якого іншого кандидата x й позначимо через N (a, x) число виборців, для яких, а краще за x. Оцінкою Сімпсона для, а називається мінімальне із чисел N (a, x) по усім x, х? а. Обирається кандидат, назв переможцем за Сімпсоном, з найвищою такою оцінкою.

Обидва ці правила заможні за Кондорсе.

Оптимальність за Парето. Якщо кандидат, а всіх кращий від кандидата b, то b не може бути обраним.

Анонімність. Імена виборців не мають значення: якщо два вибореці поміняються голосами, то результат виборів не зміниться.

Нейтральність. Імена кандидатів не мають значення. Якщо ми поміняємо місцями кандидатів, а й b у перевазі шкірного виборця, то результат голосування зміниться відповідно (якщо раніш вибирався бо тепер якщо вибиратися b й навпаки; якщо вибирався деякий x, відмінний від, а й b, те й якщо обраний).

Правила Копленда й Сімпсона оптимальні за Парето, анонімні й нейтральні, якщо ми розглядаємо їхні як відображення, що ставлять у відповідність кожному профілю переваг підмножину переможців. Анонімність й нейтральність очевидні. Перевірити, що множини переможців за Борда (Коплендом, Сімпсоном) містять лише оптимальні за Парето результати, достатньо просто. Так, оцінка Сімпсона кандидату, що домінується за Парето, дорівнює нулю, а оптимального за Парето кандидата вона позитивна.

Монотонність. Припустимо, що, а вибирається (серед переможців) при даному профілі й профіль змінюється лише так, що положення, а поліпшується, а відносне порівняння парі будь-яких інших кандидатів для будь-якого виборця залишається незмінним. Тоді а як й раніше якщо обраний (знову серед переможців) для створення нового профілю.

Всі правила підрахунку очок, а також правила Копленда й Сімпсона є монотонними.

Відносна більшість з вибуванням. У першому раунді кожний виборець подає вони одностайно за одного кандидата. Якщо кандидат набирає сувору більшість голосів, то він й обирається. У огидного випадку в іншому турі проводитися голосування за правилом більшості із двома кандидатами, що набрали найбільшу кількість голосів у першому турі.

Прихильники цого методу підтверджують, що він майже так саме простий, як й правило відносної більшості (виборцям не потрібно повідомляти повне ранжування кандидатів), й виключає марнотратні вибори. При звичайному правилі відносної більшості, якщо я голосую за кандидата, що одержує маленьку підтримку, то мой голос якщо марним. Проте при вибуванні в мене є ще один шанс вплинути на результат. Проте цей метод не є монотонним, як показують такі два профілі із 17 виборцями:

Профіль А.

Профіль B.

При профілі На другий тур проходять, а й b й виграє а (11 голосів проти 6). Профіль У такий по одним винятком. У двох виборців перевага b>a>с змінюється на перевагу а>b>с, тобто їм тепер, а краще за b. Тепер у другий тур проходять і з, причому виграє з (9 голосів проти 8). Таким чином, поліпшення позиції кандидата, а призводить до його поразки!

Метод альтернативних голосів. Виключимо спочатку тихий, хто здобувши найменшу кількість голосів. Потім порахуємо голоси для кандидатів, що залишилися, й знову виключимо невдах. Будемо повторювати цю операцію доти, поки чимало кандидат (чи множина кандидатів з рівним числом голосів).

Тут головна увага приділяється тому, щоб не загубити ніякі голоси й кожному дати шанс підтримати кандидата, який подобається найбільше. У цьому підході повторно використовуються методи підрахунку очок для винятку кандидатів-невдах. На шкода, будь-яке правило, засноване на послідовному виключенні за методом підрахунку очок, повинне порушувати властивість монотонності для деяких профілів.

Поповнення (однозначні правила голосування). Дві групи виборців N1, N2, що не перетинаються, мають справу із тією ж множиною, А кандидатів. Нехай виборці N1 й N2 вибирають саме його кандидата а. Тоді виборці N1? N2 також оберуть, а із А.

Ця властивість є дуже обгрунтованою, коли Єдиний виборчий орган розбитий на велику кількість підмножин, як у випадку регіональних асамблей й підкомітетів.

Поповнення (відображення голосування). Дві групи виборців N1, N2, що не перетинаються, мають справу із тією ж множиною, А кандидатів. Нехай виборці Ni обирають підмножину Вi із При i=1,2. Якщо В1 й B2 перетинаються, то виборці N1? N2 оберуть В1? B2 як множину найкращих для собі результатів.

Теорему 2.1 (Янг [1975]).

(a) Всі відображення голосування, засновані на підрахунку очок (підмножини кандидатів, що вибирають, з найбільшою сумарною кількістю очок), задовольняють аксіомі поповнення. Якщо при рівності очок вибір проводитися на основі фіксованого порядку на Бо відповідні правила голосування також задовольняють аксіомі поповнення.

(b) Не існує заможного за Кондорсе правила голосування (чи відображення голосування), яку б задовольняло аксіомі поповнення.

Аксіома участі. Нехай кандидат, а вибирається із множини, А виборцями із N. Розглянемо далі виборця і поза N. Тоді виборці із N?{i} повинні зверни чи а, чи кандидата, що для агента і суворо краще а.

Це означає, що якщо додатковий голос дійсно змінює результат виборів, то це може бути лише вигідна «ключовому» виборцю.

Теорему 2.2 (Мулен [1986с]).

(a) Для всіх правил голосування із підрахунком очок, коли при рівності очок вибір здійснюється за допомогою заданого порядку на А, виконується аксіома участі.

(b) Якщо, А складається хоча б з чотирьох кандидатів, то жодне заможне за Кондорсе правило голосування не задовольняє аксіомі участі.

Безперервність. Нехай виборці із N1 обирають кандидата, а із A, а група N2, що не пересікається із N1, обирає іншого кандидата b. Тоді існує достатньо велике число m дублів групи виборців N1, таке що комбінована група виборців (mN1)?N2 обере а.

Теорему 2.3 (Янг [1975]). Відображення голосування засноване на методі підрахунку очок (визначення 2.3 без фіксації правила для випадку рівності очок) тоді й лише тоді, коли воно та задовольняє таким чотирьом властивостям:

анонімність, нейтральність,.

аксіома поповнення й безперервність.

Голосування із послідовним винятком. Спочатку за правилом більшості виключається чи а, чи b, потім за правилом більшості проводитися порівняння переможця Першого раунду й з й так далі. У випадку рівності програє нижній кандидат.

У цьому процесі поправок нехай, а — поправка, b — поправка до поправки, з — вихідна пропозиція, d — status quo.

Цей метод задовольняє аксіомі спроможністі за Кондорсе: якщо, а — переможець за Кондорсе, то він виграє. Направду спроможність при порівняннях за правилом більшості справедлива в ширшому змісті.

Спроможність за Смітом. Якщо множина, А кандидатів розбивається на дві підмножини В1, B2, що не перетинаються, й кожний кандидат b1? В1 виграє (за суворою більшістю) у будь-якого кандидата b2? В2, то повинний бути обраний результат з В1.

З іншого боці, голосування при послідовному винятку очевидно не є нейтральним. Порядок виключень, звичайно, впливає на результат.

Правило рівнобіжного виключення. Спочатку за правилом більшості дорівнюються парі а із b й з із d. Переможці зустрічаються у фіналі, де порівнюються за правилом більшості. У випадку рівності вибирається кандидат, що йде раніше за алфавітом.

Це — знову заможний за Кондорсе метод. Більш того, для обрання кожному кандидату x потрібно перемогти в двох порівняннях за правилом більшості. Припустимо спочатку, що рівності при порівнянні із цими двома кандидатами немає (x виграє для суворої більшості). Тоді x не може домінуватися за Парето деяким кандидатом у, інакше b був бі переможцем за Кондорсе. Отже, метод рівнобіжного виключення вибирає оптимальний за Парето результат у (найбільше поширеному) випадку, коли при бінарних виборах немає рівностей. Проте якщо рівності можливі, то оптимальність за Парето може порушуватися.

Бінарним деревом на, А є таке кінцеве дерево, у котрому кожній нефінальній вершині (включаючи початкову) відповідають рівно дві наступні, а кожній фінальній вершині (у котрої немає наступних) приписаний кандидат (елемент з A), причому кожний кандидат із «являється принаймні в одній фінальній вершині.

Серед бінарних дерев найпростішими є тих, у яких кожний кандидат приписаний рівно одній вершині. Назвемо їхні деревами без повторних виключень.

Лема 2.1.

(а) Якщо, А складається із трьох кандидатів, то дерево после послідовного виключення є єдиним безповторним деревом. Відповідне правило голосування оптимальне за Парето (при нашій умові, що усі порівняння по більшості суворі).

(b) Якщо, А складається із чотирьох кандидатів, тобто лише два безповторних дерева: послідовне виключення й рівнобіжне виключення. Перше із них порушує оптимальність за Парето, а останнє - ні.

(з) Якщо, А містить п «ять чи понад кандидатів, то будь-яке виключення по безповторному дереву призводить до обрання кандидата для деяких профілі, в що домінується за Парето.

Існує бінарне дерево, визначене для довільної кількості учасників, що дозволяє уникнути обох цих небезпек. Відповідні послідовні виключення породжують оптимальне за Парето, анонімне й монотонне правило голосування. Це дерево називається деревом багатоетапного виключення.

Для шкірного конкретного упорядкування кандидатів існує за одним такому дереву. Позначимо через Гp (1,2,…, р) дерево, що відповідає порядку A={1,2,…, р}. Визначимо його індуктивно за розміром А:

Так, для трьох й чотирьох кандидатів одержуємо:

При р кандидатів утворюються 2p-l фінальні вершини; кандидат 1 приписаний 2p-2 фінальним вершин, а кандидат р лише однієї. Тім задля обрання навіть кандидату р потрібно перемогти в р-1 дуелях (хоча йому можливо прийдеться по декілька разів зіткнутися із тім самим опонентом).

Хоча дерево багатоетапного виключення велике, його рішення (тобто обчислення кандидата, що виграє) може бути отримане за допомогою дуже простого алгоритму.

Теорему 2.4 (Шепсл й Вейнгаст [1984]).

Задані дерево багатоетапного виключення Гp (1,2,…, р) й профіль переваги, що відповідає мажоритарному турніру Т. Кандидат а* може бути знайдений за таким алгоритмом:

(12).

Наслідок теореми 2.4. Кандидат а, що вибирається з дерева багатоетапного виключення із турніром Т, задовольняє умові:

для будь-якого b? А, b? а:

{аТb} і/або {для деякого з, аТс й сTb}. (14).

В частности, а оптимальний за Парето. Більш того, дерево багатоетапного виключення породжує монотонний метод голосування.

Серед заможних за Кондорсе правил голосування ми виявили три методи, що задовольняють основним вимогам оптимальності за Парето, анонімності й монотонності: множина переможців за Коплендом, множина переможців за Сімпсоном й дерево багатоетапного виключення. Перші два нейтральні, але й можуть виділяти декількох переможців (додаткове правило при рівності очок порушити нейтральність). Зауважимо, що переможець при багатоетапному виключенні знаходиться швидше, оскільки алгоритм (12) у середньому потребує порівняння не понад половини від всіх p (p-l) пар. У тієї ж годину для визначення переможців за Коплендом й Сімпсоном потрібно провести весь турнір порівнянь за правилом більшості.

МАТЕМАТИЧНІ МЕТОДИ РОЗВ’ЯЗКУ.

У попередньому розділі були описані методи підрахунку очок й основні вимоги перед тим. Порівняємо ці методи.

як було б зазначено, найлегшим серед них, але й і найгіршим, є правило відносної більшості. Можна переконатись, що на самом деле воно та суперечить думці більшості. Тому воно та не може бути вибране для комп’ютерної реалізації.

як Борда, то й Кондорсе зауважили, що правило відносної більшості може призводити до обрання поганого кандидата, точніше такого кандидата, що у парному порівнянні за правилом більшості програє будь-якому іншому кандидату.

А щоб перебороти цю хибу, Кондорсе й Борда запропонували відмовитися від правила відносної більшості, причому кожний з них запропонував своє правило замість даного. Кондорсе запропонував вибирати кандидата, що перемагає будь-якого іншого кандидати парному порівнянні, якщо такий переможець за Кондорсе існує. Борда запропонував приписати очко кожному кандидату, який лінійно зростає у залежності від його рангу в перевазі виборця. Потім він запропонував зверни кандидата, що здобувши найбільшу сумарну кількість очок в всіх виборців. Ці дві ідеї породжують два найбільше важливих сімейств правил голосування.

Результати цих правил голосування можуть сильно відрізнятися за властивостями. Однією з таких властивостей є аксіома монотонності. Правило голосування називається монотонним, якщо кандидат залишається обраним при посиленні його підтримки (тобто коли відносна позиція даного кандидата у чиїхось перевагах поліпшується, а відносні позиції інших кандидатів не змінюються). Всі методи підрахунку очок є монотонними, але й деякі відомі методи, що виникають з підрахунку очок, не є такими. Прикладами таких правил служать дуже популярне правило відносної більшості із вибуванням й метод альтернативних голосів.

Є дві аксіоми, що призводять до критики заможних за Кондорсе правил (оскільки дані правила порушують ці аксіоми). З іншого боці, на цих аксіомах заснована характеризація методу підрахунку очок. Ці аксіоми порівнюють кандидатів, обраних різноманітними групами виборців. Вони називаються властивостями поповнення і участі. Поповнення означає, що якщо дві групи виборців, що не перетинаються, (наприклад, сенат й палата представників) обирають саме його кандидата бо про «єднання цих двох виборчих органів підтвердить обрання а. Доля означає, що виборець не може виграти, утримуючись від голосування, у порівнянні із можливістю брати доля в голосуванні й висловити свої переваги. Будь-яке заможне за Кондорсе правило порушує обидві ці аксіоми. На противагу цьому правила підрахунку очок характеризуються властивістю поповнення (теорема Янга) й задовольняють аксіомі участі. Теорему Янга в даний годину є найістотнішим доказом у підтримку методів підрахунку очок, зокрема системи очок Борда.

Заможні за Кондорсе правила голосування усе ж надзвичайно популярні, зокрема, завдяки простоті доведення парного порівняння за правилом більшості. Відповідний клас заможних за Кондорсе методів заснований на послідовних порівняннях за правилом більшості. Законопроект й численні поправки до нього в конгресі США голосуються саме у такий спосіб. Відомий метод послідовного винятку може порушувати умову оптимальності за Парето. Інші методи, засновані на бінарних деревах парних порівнянь за правилом більшості, суперечать аксіомі монотонності. Найпростіше правило, що засноване на послідовному порівнянні й є оптимальним за Парето й монотонним, називається багатоетапним методом винятку. При використанні цого методу потрібно менше парних порівнянь, ніж в інших, концептуально более простих методах, наприклад у правилі Копленда. За останнім правилом обирається тієї, хто виграє більшість парних дуелей. Таким чином, голосування, засноване на послідовних парних порівняннях, може задовольняти найбільше важливим аксіоматичним вимогам, але й лише до того випадку, якщо ми акуратно виберемо цю послідовність.

Правила Борда, відносної більшості та антибільшості являють собою приклади правил голосування із підрахунком очок. Проте правило антибільшості року є монотонне, а правило відносної більшості - несправедливе.

Переможець Борда не може бути найгіршим за Кондорсе, так як він є кандидатом, що має найвищий середній бал. За цим правилом завжди знаходяться оптимальний за Парето переможець чи їхні множина. Прикладами заможних за Кондорсе правил є правила Копленда та Сімпсона. Так саме, як й правило Борда чи будь-який інший метод підрахунку очок, ці правила вибирають для шкірного профілю підмножину переможців, котра може складатись із декількох кандидатів, що здобули однакову оцінку.

як уже було б зазначено, правила голосування повинні бути монотонні, оптимальні за Парето, антонімні й нейтральні. Всі правила голосування із підрахунком очок, крім правила антибільшості, є оптимальні за Парето, монотонні, анонімні й нейтральні, якщо ми не вказуємо, що робити при рівності очок. Крім того, правила голосування повинні задовольняти аксіомі участі та поповнення. Метод Борда відноситься до цих правил (це було б показано у попередньому розділі).

Правила Борда й Копленда, як зазначає Мулен, спираючись на практику, не дуже частини призводять до рівності очок [1, ст. 299], тому у цьому ракурсі є найкращими. Проте методи Кондорсе, до які відноситься й правило Копленда, для деяких профілів може не задовольняти аксіомі участі.

Наступною групою правил є правила, засновані на послідовному виключенні за методом підрахунку очок (відносна більшість із вибуванням, метод альтернативних голосів). Проте ці правила, як й будь-які інші методи із вибуванням кандидатів, порушують властивість монотонності для деяких профілів.

Метод рівнобіжного виключення вибирає оптимальний за Парето результат у (найбільше поширеному) випадку, коли при бінарних виборах немає рівностей. Проте якщо рівності можливі, то оптимальність за Парето може порушуватися.

Незважаючи на вище перераховані труднощі, спроможність за Кондорсе, широко відома у якості демократичного принципу, у тому годину як правило Борда «приховує» справжні симпатії виборців за математичною формулою.

До заможних до Кондорсе правил відносять також наступні методи голосування:

а) голосування із послідовним винятком. За очевидних причин це правило, не є нейтральним й оптимальним за Парето, так як порядок виключень впливає на результат голосування. Визначаючи порядок денний, голова фактично контролює процес виборів. Проте це правило досить широко використовується Конгресом США;

б) правило рівнобіжного виключення. Воно породжує дерево без повторних виключень й вимагає проведення цілої низькі мажоритарних турнірів. як було б доведено в попередньому розділі, бінарне дерево може дати оптимальне за Парето правило голосування лише у складнішому випадку, ніж безповторне дерево. Також може порушуватись монотонність;

в) дерево багатоетапних виключень. Цей метод забезпечує проведення наполовину меншої кількості мажоритарних турнірів, ніж метод Копленда. Воно має великий розмір. Кандидатам, можливо, потрібно брати доля в дуелях із тім самим опонентом по декілька разів. Проте його алгоритм є досить вибачимо. Дерево багатоетапного виключення породжує оптимальний за Парето й монотонний метод голосування. Завжди знаходиться Єдиний переможець, а чи не множина. Проте цей метод породжує усі труднощі, котрі пов’язані із використанням бінарних дерев.

Таким чином, було б проведено порівняльну характеристику всіх методів голосування більшістю голосів з виключенням випадків байдужості й подання неправдивої інформації.

Серед заможних за Кондорсе правил голосування ми виявили три методи, що задовольняють основним вимогам оптимальності за Парето, анонімності й монотонності: множина переможців за Коплендом, множина переможців за Сімпсоном й дерево багатоетапного виключення. Серед методів підрахунку очок найкращим виявився метод визначення переможця за Борда. Заможні за Кондорсе правила застосовані на парному порівнянні кандидатів за правилом відносної більшості. Для пересічну виборця смердоті є найбільш зрозумілими.

Правило Борда задовольняє аксіомі участі та поповнення, але й приховує за математичною формулою справжні переваги виборців.

Для програмної реалізації виберемо один із методів Копленда як найпростіший й для порівняння визначимо переможця за Борда.

Приведемо ще раз правила Копленда й Борда у тому, щоб перейти до формулювання алгоритму програми.

Правило Борда. Кожний виборець повідомляє свої переваги, ранджуючи р кандидатів від кращого до гіршого (байдужність забороняється). Кандидат не одержує очок за останнє місце, одержує одне очко за передостаннє й так далі, одержує р-1 очок за перше місце. Перемагає кандидат з найбільшою сумою очок. Він називається переможцем за Борда.

Правило Копленда. Порівняємо кандидата, а із будь-яким іншим кандидатом x. Нарахуємо йому +1, якщо для більшості а краще за x, -1, якщо для більшості x краще за а, й 0 при рівності. Сумуючи загальну кількість очок по усім x, х? а, одержуємо оцінку Копленда для а. Обирається кандидат, назв переможцем за Коплендом, з найвищою із таких оцінок.

Вважаємо, що вхідними даними задачі є уже згрупована інформація: сформовані групи виборців із однаковими у кожній групі рангами переваг. Проте допускається й занесення інформації кожним виборцем окремо.

ОПИС АЛГОРИТМУ.

У даному розділі наводяться алгоритми для знаходження переможців виборів.

Для визначення переможців Борда та Копленда скористаємося безпосередньо наведеними вище правилами, тобто реалізуємо їхнього програмно.

Складність алгоритмів, описаних нижче, прямо пропорційна кількості груп виборців та кількості кандидатів, що ще раз підтверджує приналежність даної задачі до Р-типу.

4.1 ВИЗНАЧЕННЯ ПЕРЕМОЖЦЯ БОРДА.

Для знаходження оцінок Борда кандидати ранджуються, тобто за кожне місце у шкалі виборців кандидат отримує певну кількість балів. Далі ці бали сумуються.

Введемо наступні змінні.

Нехай М — кількість кандидатів;

P.S — кількість груп виборців;

Nаme[M] - масив імен виборців;

Rаng[1.M, 1. S] - профіль переваг;

Many[S] - кількість виборців у кожній групі;

Bord[M] - масив оцінок кандидатів.

Розглядаємо окремо кожну групу виборців. Для цієї групи кандидат отримує оцінку [кількість виборців many[i]]*([кількість кандидатів M] - [поточне значення лічильника j]). Знайдена оцінка додається до попередньої. Алгоритм продовжує роботу до тихий пір, поки не будуть розглянуті усі групи виборців (i=S).

За правилом Борда отримуємо наступний алгоритм для знаходження оцінок Борда.

Рис. 4.1 Алгоритм знаходження оцінок Борда.

4.2 ЗНАХОДЖЕННЯ ОЦІНКИ КОПЛЕНДА.

Для знаходження оцінки Копленда крім вище наведених використаємо наступні змінні:

Kopl[M] - масив оцінок Копленда;

Vybor1, vybor2 — допоміжні змінні; використовуються для перегляду імен кандидатів із масиву імен name.

Порівняння проходити наступним чином.

Змінній vybor1 присвоюємо значення імені Першого кандидата із множини імен name (contrl=1), а vybor2 — наступне (k=contrl+1). Якщо vybor1 знаходиться вище, ніж vybor2, у перевагах виборців всіх груп, то до оцінки Копленда (kopl[contrl]) кандидата vybor1 додається очко, а vybor2 (kopl[k]) — віднімається й навпаки. Далі змінній vybor2 присвоюється наступне значення із масиву імен (k=k+1), й процедура порівняння знову повторюється. Цикл продовжується до тихий пір, поки не вичерпаються імена у списку кандидатів.

Після цого змінній vybor1 присвоюється одному ім'я з списку кандидатів (contrl=contrl+1), а vybor2 — третя. Знову проходити цикл по змінній vybor2. Цикл по змінній vybor1 закінчується тоді, коли якщо переглянуто всіх кандидатів.

Отримуємо наступний алгоритм знаходження оцінки Копленда.

Рис. 4.2 Алгоритм знаходження оцінок Копленда (початок).

Рис. 4.3 Алгоритм знаходження оцінок Копленда (закінчення).

4.3 АЛГОРИТМ ВИЗНАЧЕННЯ ПЕРЕМОЖЦЯ ЗА ПРАВИЛАМИ БОРДА ЧИ КОПЛЕНДА.

як можна було б побачити, переможцем за Борда (Коплендом) є кандидат із найвищою сумою очок. Тому процес його визначення є однаковим для обох випадків, й я його об'єднала одним алгоритмом.

як відомо, правила Копленда й Борда породжують множину розв’язків.

Для знаходження переможця використаємо наступні змінні:

K — кількість переможців;

Max — оцінка переможців;

Hl[M] - масив номерів переможців.

Спочатку масив номерів переможців заповнюємо нулями.

Масиви оцінок Копленда й Борда (kopl і bord) замінимо формальним масивом v[M].

Після того, як ми знайшли оцінки для кандидатів (масиви kopl і bord), серед них шукаємо максимальну (max). Далі відбираємо кандидатів, оцінка які дорівнює max (їхні номери із масиву name заносяться у масив hl), й рахуємо кількість переможців (k).

Переглядаємо заповнений масив hl. Якщо у ньому лише перше значення є відмінне від нуля, то це означає, що ми знайшли єдиного переможця, й, отже, зберегли умову нейтральності.

У іншому випадку проглядаємо тих значення імен кандидатів (масив name), номери які зустрічаються у масиві hl. Відібрані імена кандидатів впорядковуємо за списком. Переможцем стає тієї, ім'я якого знаходиться першим у даному списку.

У даному випадку умова нейтральності не зберігається.

Отже, ми отримали наступний алгоритм.

Рис. 4.4 Алгоритм визначення переможця (початок).

Рис. 4.5. Алгоритм визначення переможця (закінчення).

ОПИС ПРОГРАМИ.

5.1 ВИБІР ТЕХНОЛОГІЇ ПРОГРАМУВАННЯ.

Найбільш поширеними парадигмами програмування, котрі доти ж можуть бути використані у даній курсовій роботі, є парадигми процедурного та об'єктно-орієнтованого програмування.

Парадигма процедурного програмування найбільше широко поширена серед існуючих мов програмування (наприклад, Сі й Паскаль). Тут явно виділяють два види різноманітних сутностей:

1) процедури, що виконують активну роль, тобто є тім, що задає поведінку (функціонування) програми;

2) дані, що виконують пасивну роль, тобто являють тім, що опрацьовується засобом, продиктованим процедурами. Спроможність складати процедури із команд (операторів) й викликати їхні є ключем даної парадигми. Особливістю цієї парадигми є «бічні ефекти », що виникають у тихий випадках, коли різноманітні процедури, що використовують загальні дані, незалежно їхні змінюють.

У процедурній парадигмі активна роль організації поведінки приділяється процедурам, а чи не даним; причому процедура активізується викликом. Подібні засоби заподіяння поведінки зручні для описів детермінованої послідовності дій чи одного процесу, чи декількох, але й суворо взаємозалежних процесів.

При використанні програмування, орієнтованого на дані, активну роль відіграють дані, а чи не процедури. Тут з структурами активних даних зв «язують деякі дії (процедури), що активізуються тоді, коли здійснюється доступ до цим даним. Деякі спеціалісти називають цей засіб активації дій «демонами ». Програмування, орієнтоване на дані, дозволяє організувати поведінку мало залежних процесів, що важко реалізувати в процедурній парадигмі. Мала залежність процесів означає, що смердоті можуть розглядатися й програмуватися окремо. Проте при використанні парадигми, керованої даними, ці незалежно запрограмовані процеси можуть взаємодіяти між собою без їхньої зміни (тобто без перепрограмування).

Парадигма про «єктного програмування на відміну від процедурної парадигми не розділяє програму на процедури й дані. Тут програма організується навколо сутностей, названих про «єктами, що включають локальні процедури (методи) й локальні дані (змінні). Поведінка (функціонування) у цій парадигмі організується шляхом пересилки повідомлень між про «єктами. Про «єкт, отримавши повідомлення, здійснює його локальну інтепретацію, базуючись на локальних процедурах й даних. Такий підхід дозволяє описувати складні системи найбільш природним чином. Особливо він зручний для інтегрованих ІС.

Про «єктно-орієнтоване програмування (ОВП) базується на абстракціях даних. У основі цого методу лежить представлення предметної області у вигляді сукупності об'єктів, котрі взаємодіють між собою через передачу повідомлень. Модель абстракції даних полягає в інкапсуляції даних та операцій з них в окремий класовий тип. Доступ до даних можлива лише за допомогою інкапсульованих операцій. Класовий тип є автономно завершеним й дозволяє повне чи часткове наслідування для інших класів. ОВП концентрується на суті задачі, для якої розробляється програма. Завдання будується як сукупність про «єктів, котрі взаємодіють між собою за допомогою повідомлень. Елементи програми розробляються у відповідності із про «єктами в описі задачі. Суть ОВП полягає у визначенні найбільш вдалих про «єктових типів. Про «єктовий тип служити модулем, який може бути використаним для розв «язку інших подібних завдань. Такий підхід не потребує спеціальної обчислювальної техніки, але й суттєво відрізняється характером мислення виконавців у порівнянні із процедурними мовами програмування.

Через очевидну простоту алгоритму для реалізації задачі найкраще вибрати процедурну парадигму програмування й мови Паскаль чи Сі. Звичайно, для написання гарного інтерфейсу можна взяти об'єктно-орієнтовані мови З Builder чи Delphi. Проте, як можна було б побачити із розгляду алгоритму задачі, побудова інтерфейсу зводилася б до послідовного виведення вікон. Ще одним аргументом на користь мов Паскаль чи Сі є розміри програми, котрі б при використанні З Builder чи Delphi були набагото більшими.

Серед двох мов — Паскаль й Сі, — я оберу Паскаль як более звичну для себе.

5.2 СТРУКТУРА ПРОГРАМИ.

Структурно дану програму можна поділити на блоки. Кожен блок може бути віднесений до однієї із функціональних груп:

1. Побудова інтерфейсу;

2. Реалізація алгоритмів, представлених у розділі 4.

Отже, програма має наступну структуру:

Рис. 5.1 Структура програми.

Процедура victory — це реалізація алгоритму визначення переможця, описаного у попередньому розділі. Під годину виклику даної процедури задається масив оцінок Борда чи Копленда, а також текст для виведення результатів (ним служать слова «Копленда» та «Борда»). У попередньому розділі уже було б обгрунтовано, чому для визначення переможця за різними правилами використано Єдиний алгоритм.

Процедура help виводить список імен кандидатів у нижньому рядку екрану. Вона введена для полегшення введення інформації користувачем.

Процедура example містить дані контрольного приклада. Вона введена для полегшення перевірки правильності роботи програми й носити демонстраційний характер.

Процедура right призначена для перевірки правильності введення символу. Вона використовується при виборі внесення інформації (демонстрація контрольного приклада чи самостійне внесення профілю) й виборі способу занесення даних (окремими виборцями чи працівниками виборчого комітету).

Перейдемо до розгляду основної програми.

Перш на у ній проходити виклик й взаємозв'язок описаних вище процедур.

Процедури побудови інтерфейсу викликаються на початку роботи програми. Вони призначені для полегшення внесення даних.

Процедура victory визначає переможця й виводить результат голосування за певним правилом. Тому її виклик відбувається вкінці основної програми.

Опишемо змінні, котрі використовуються в основній програмі.

N: к-ть виборців;

M: к-ть кандидатів;

p.s: к-ть груп;

rang: профіль переваг;

a, b: для визначення оцінки Копленда (використовується у бінарних порівняннях);

kopl: масив оцінок Копленда;

vybor1, vybor2: змінні зовнішніх циклів при визначенні оцінки Копленда;

bord: масив оцінок Борда;

name: масив імен кандидатів;

k, і, j, l, r: допоміжні змінні;

many: масив груп виборців.

Опишемо структуру програми.

Спочатку програма просити внести усю потрібну інформацію. Користувач винен вказати кількість виборців та кандидатів й спосіб занесення інформації (чи свої переваги якщо вносити кожен виборець окремо, чи це якщо проводити комісія, оперуючи згрупованими даними). Далі йде внесення профілю переваг й перевірка на його коректність. Профіль є некоректним, якщо у ньому зустрічається ім'я особини, Яка не є вище вказаним кандидатом, чи ж імена кандидатів повторюються.

У програмі використовуються алгоритми правил Борда та Копленда, вказані у попередньому розділі. Згідно отриманих оцінок визначається переможець за допомогою процедури victory, й проходити виведення результату.

Слід зауважити, що отримані переможці Копленда та Борда можуть не співпадати, що ще раз свідчить про недосконалість правил голосування більшістю голосів. Результати роботи алгоритму будуть показані у відповідному розділі.

Складність програми (у даному випадку розуміється годину, затрачений на виконання), прямо пропорційно залежить від величини кількості виборців та кандидатів.

Так як дана програма носити более демонстраційний характер, то я запровадила між для кількості виборців й кандидатів у тому, щоб обмежити годину виконання — 200 та 50 відповідно. У загальному воно та не є суттєвим, так як завжди можна розбити виборчий округ на менший із умовою того, щоб виконувалось дане обмеження.

5.3 ІНСТРУКЦІЯ КОРИСТУВАЧЕВІ.

Дана програма призначена для визначення переможця виборів за правилами Копленда й Борда й порівняння отриманих результатів.

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

Спочатку працівники виборчого органу вносять загальну інформацію: кількість виборців у даному окрузі та кількість кандидатів. Далі заносяться імена кандидатів й вказується спосіб занесення профілів переваг: кожним виборцем окремо чи працівниками виборчого округу. У останньому випадку інформація є згрупована (аналогічно до контрольного прикладу).

Унизу екрана виводяться імена всіх кандидатів. Кожен виборець (чи працівник виборчого округу) вносити профіль переваг, розташовуючи кандидатів у суворо визначеному порядку.

Для шкірного виборця не допускається випадків байдужості; крім того, кандидати повинні бути суворо ранджовані (тобто кожен із них займає своє місце у перевазі виборця, й на одному рівні не можуть знаходитись два кандидати). Імена кандидатів, котрі заносяться виборцями, повинні співпадати із іменами, вказаними на початку заповнення інформації.

Після занесення всіх цих даних видається результат роботи програми.

Спочатку виводиться переможець Копленда й вказується, чи він визначений з збереженням нейтральності. Для переможця вказується його оцінка. У огидного випадку виводиться множина переможців (кандидатів, сума очок які дорівнює максимальній оцінці).

Аналогічно визначається переможець Борда.

як якщо показано у контрольному прикладі, оцінки кандидатів, отриманих за правилами Борда й Копленда, можуть ранджуватись у протилежному порядку.

КОНТРОЛЬНИЙ ПРИКЛАД.

Нехай дано наступний профіль для 9 виборців й 5-ти кандидатів:

1 4 1 3.

e c.

a e.

з e.

У кожному стовпці кандидати розташовані у порядку зменшення їхнього значущості для кожної групи виборців. Тобто, для Першого стовпця можна визначити переваги наступним чином: група виборців, що складається із однієї особини, вважає кандидата a найкращим. На іншому місці смердоті ставлять кандидата b, на третьому місці з й т.д.

Продемонструємо розв’язок контрольного приклада за правилом Копленда. Визначаємо оцінку Копленда.

Кандидат a є кращим за b для 1+1+3 виборців, а 4-х виборців кандидат b є кращим за a. Визначимо такі переваги для шкірного кандидата, порівняємо його із усіма іншими.

ab — 5.

ac — 5.

ad — 5.

ae — 1.

ba — 4.

ca — 4.

da — 4.

ea — 8.

bc — 5.

bd — 4.

de — 5.

cb — 4.

db — 5.

eb — 4.

cd — 5.

ce — 5.

dc — 4.

ec — 4.

de — 5.

ed — 4.

Визначимо оцінку Копленда для шкірного кандидата. Кандидат a є кращим за b (додаємо +1); він також є кращим за з та d (додаємо два рази +1) й гіршим за e (додаємо -1). Отже, оцінка Копленда для a рівна 2.

Знайдемо оцінку для інших кандидатів.

a=+1+1+1−1=2.

b=-1+1−1+1=0.

c=-1−1+1+=0.

d=-1+1−1+1=0.

e=+1−1-1−1=-2.

Серед отриманих оцінок визначаємо максимальну. як бачимо, вон дорівнює 2 й належить кандидату a. Отже, a — переможець Копленда.

Якби ми отрималось два кандидати із максимальною оцінкою, наприклад b та f, ми б обрали кандидата b, так як він розташований ближче за алфавітом.

Для цого ж профілю знайдемо переможця Борда.

Отже, отримуємо такі оцінки:

a=1*4+4*0+1*3+3*3=16.

b=3*1+2*4+1*1+2*3=18.

c=2*1+4*4+0+0=18.

d=1*1+4*3+2*1+1*3=18.

e=1*4+1*4+3*4+0=20.

Переможцем за Борда є кандидат е.

як бачимо, оцінки Борда ранджують кандидатів у порядку, протилежному доти, який отримується за оцінками Копленда.

ВИСНОВКИ.

Дана курсова робота був присвячена огляду методів голосування більшістю голосів. Було проведено порівняльну характеристику шкірного із методів й із їхні множини обрано найкращі. До них відносяться.

1. заможні за Кондорсе правила Копленла й Сімпсона, дерево багатоетапного виключення;

2. один із методів підрахунку очок — правило Борда.

Всі ці правила задовольняють умовам оптимальності за Парето, монотонності та анонімності. Крім того, правило Борда задовольняє також аксіомі участі та поповнення.

Для програмної реалізації було б обрано методи Копленда й Борда.

Результати роботи програми продемонстровано на контрольному прикладі.

СПИСОК ЛІТЕРАТУРИ.

1. Мулен Еге. «Кооперативний прийняття рішень: Аксіоми і моделі» — Москва, Світ, 1991.

2. Миркин Б. Проблема групового вибору. — Москва, Наука, 1974.

ДОДАТКИ.

ПРОГРАМА.

uses wincrt;

label y, z;

type mas = string[6];

type ball =array[1.10] of shortint;

var N: byte; {к-ть виборцiв}.

M: byte; {к-ть кандидатiв}.

p.s: byte; {к-ть груп}.

rang: array[1.10,1.100] of mas; {профiль переваг}.

k, i, j, l, r, contrl: byte;

a, b: byte;{для проведення парних порiвнянь}.

kopl: ball; {масив оцiнок Копленда}.

vybor1, vybor2: mas;

bord: ball;{масив оцiнок Борда}.

name: array[1.10] of mas; {масив iмен кандидатiв}.

many: array[1.100] of byte; {масив груп виборцiв}.

n1: array[1.10] of mas;

з: char;

{дані контрольного прикладу}.

{—————————————-}.

procedure example;

var і, j: byte;

begin.

clrscr; M:=5; n:=9; s:=4;

name[1]: = «a »; name[2]: = «b »; name[3]: = «з »; name[4]: = «d »; name[5]: = «e » ;

many[1]: =1; many[2]: =4; many[3]: =1; many[4]: =3;

rang[1,1]: = «a »; rang[1,2]: = «з »; rang[1,3]: = «e »; rang[1,4]: = «e » ;

rang[2,1]: = «b »; rang[2,2]: = «d »; rang[2,3]: = «a »; rang[2,4]: = «a » ;

rang[3,1]: = «з »; rang[3,2]: = «b »; rang[3,3]: = «d »; rang[3,4]: = «b » ;

rang[4,1]: = «d »; rang[4,2]: = «e »; rang[4,3]: = «b »; rang[4,4]: = «d » ;

rang[5,1]: = «e »; rang[5,2]: = «a »; rang[5,3]: = «з »; rang[5,4]: = «з » ;

gotoXY (15,1);

writeln («Завдання контрольного приклада »);

writeln; writeln («Кількість виборців: », N);

writeln («Кількість кандидатів: », M);

writeln («Профіль переваг: »);

for i:=1 to 40 do.

write («- «);

writeln; write («Кількість виборців »);

gotoXY (19,7);

for i:=1 to p. s do.

write (many[i], «»);

writeln; gotoXY (19,9);

for i:=1 to M do.

begin.

for j:=1 to p. s do.

write (rang[i, j], «»);

gotoXY (19, 9+i);

end;

gotoXY (1,15);

end;

{—————————————-}.

{перевіряє правильність введення варіанту вибору}.

procedure right;

label l;

begin.

l: readln (c);

if (з «0 ») and (з «1 ») then.

begin.

write («Повторіть спробу: »);

goto l;

end;

{—————————————-}.

{виводить список імен кандидатів}.

procedure help;

var x, y, i: byte;

begin.

x:=WhereX;

y:=WhereY;

gotoXY (1,24);

write («Імена кандидатів: »);

for i:=1 to M do.

if iM then write (name[i], «, «).

else write (name[i]);

gotoXY (x, y);

end;

{—————————————-}.

{визначення переможця виборів}.

procedure victory (v: ball; p. s: string);

var max, t: shortint;

hl: array[1.10] of byte;

begin.

{визначення максимальної оцiнки}.

help;

max:=v[1];

for i:=1 to M do.

if max.

max:=v[i];

t:=1;

{визначення кандидатiв із максимальною оцiнкою}.

for i:=1 to M do.

if (v[i]-max)=0 then.

begin.

hl[t]: =i;

t:=t+1;

end;

if (t-1)=1 then.

begin.

write («Переможець за », p. s, «iз збереженням нейтральностi: »);

writeln (name[hl[1]]); writeln («Сума очок — «, max);

end.

else.

begin.

vybor1:=name[hl[1]];

for i:=2 to t-1 do.

if name[hl[i]].

vybor1:=name[hl[i]];

write («Переможець за », p. s, «без збереження нейтральностi: »);

writeln (vybor1); writeln («Сума очок — «, max);

writeln («обраний із множини найкращих: »);

for i:=1 to t-1 do.

writeln (name[hl[i]]);

end;

{—————————————-}.

{основна програма}.

begin.

gotoXY (21,1); writeln («Визначення переможця виборів »);

writeln; writeln («Запуск контрольного приклада — 1; Самостійне внесення профілю — 0 »);

right;

if з= «1 «then.

begin.

example;

help;

goto z;

end.

else clrscr;

write («Введiть кiлькiсть кандидатiв: »);

readln (M);

write («Введiть кiлькiсть виборцiв: »);

readln (N);

writeln («Введiть iмена кандидатiв »);

for i:=1 to M do.

begin.

write («Кандидат », і, «: »);

readln (name[i]);

end;

writeln («як якщо здiйснюватись занесення iнформацiї? »);

write («1- окремими виборцями, 0- комiтетом: »);

right;

if з= «1 «then.

for i:=1 to N do.

many[i]: =1;

clrscr; writeln («Введiть профiль переваг »);

s:=1; contrl:=0;

while contrlN do.

begin.

if з= «1 «then writeln («Виборець », s).

else writeln («Група », s);

for i:=1 to m do.

n1[i]: = «» ;

help;

for j:=1 to M do.

begin.

y:readln (vybor1);

{перевірка на коректність введеного профілю}.

r:=0; a:=0; b:=0;

n1[j]: =vybor1;

for l:=1 to M do.

begin.

if vybor1=name[l] then.

begin.

b:=1;

for a:=1 to M do.

{таке ім «я уже було б введено у даному профілі}.

if (vybor1=n1[a]) and ((a-j)0) then r:=1;

end;

{ім «я введеного кандидата не співпадає з жодним з списку}.

if (vybor1name[l]) and (l=M) and (b1)then r:=1;

end;

if r=1 then.

begin.

n1[j]: = «» ;

writeln («Уважно вводьте імена кандидатів »);

goto y;

end.

else rang[j, s]: =vybor1; {профіль коректний}.

end;

if з= «0 «then.

begin.

writeln («Кiлькiсть виборцiв у групi », s);

readln (many[s]);

contrl:=contrl+many[s];

end.

else.

contrl:=contrl+1;

s:=s+1;

clrscr;

end; {while}.

{Визначення оцiнок Копленда}.

z: contrl:=1;

while contrl.

begin.

k:=contrl+1;

vybor1:=name[contrl]; vybor2:=name[k];

while k.

begin.

i:=1; a:=0; b:=0;

while i.

begin.

for j:=1 to M do.

if rang[j, i]=vybor1 then l:=j.

else.

if rang[j, i]=vybor2 then r:=j;

if l.

else.

if l>r then b:=b+many[i];

i:=i+1;

end;

if a>b then.

begin.

kopl[contrl]: =kopl[contrl]+1;

kopl[k]: =kopl[k]-1;

end.

else.

if a.

begin.

kopl[k]: =kopl[k]+1;.

kopl[contrl]: =kopl[contrl]-1;.

end;.

k:=k+1;.

vybor2:=name[k];.

end; {while по k}.

contrl:=contrl+1;.

end; {while по contrl}.

{визначення оцiнок Борда}.

for i:=1 to p. s do.

for j:=1 to M do.

begin.

for k:=1 to M do.

if rang[j, i]=name[k] then r:=k;.

bord[r]: =many[i]*(M-j)+bord[r];.

end;.

victory (kopl, «Коплендом »);.

writeln («Натисніть будь-яку клавішу »);.

readkey; writeln;.

victory (bord, «Борда »);.

end..

Результати роботи програми.

Самостійне внесення профілю.

Введіть кількість кандидатів: 5.

Введіть кількість виборців: 9.

Введіть імена кандидатів.

Кандидат 1: а.

Кандидат 2: b.

Кандидат 3: c.

Кандидат 4: d.

Кандидат 5: е.

як якщо здійснюватись занесення інформації?.

1-окремими виборцями, 0 — комітетом: 0.

Введіть профіль переваг.

Група 1.

Кількість виборців у групі 1: 1.

Група 2.

Кількість виборців у групі 2: 4.

Група 3.

Кількість виборців у групі 3: 1.

Група 4.

Кількість виборців у групі 4: 3.

Переможець за Коплендом з збереженням нейтральності - а.

Сума очок — 2.

Переможець за Борда з збереженням нейтральності - е.

Сума очок — 20.

Демонстрація роботи контрольного прикладу.

Показати весь текст

Заповнити форму поточною роботою