. . . . . . "L'algorithme de Gale et Shapley est un algorithme qui r\u00E9sout le probl\u00E8me des mariages stables."@fr . "1100670229"^^ . "Algorytm odroczonej akceptacji (inaczej zwany algorytmem Gale\u2019a-Shapleya) jest algorytmem, kt\u00F3rego celem jest znalezienie rozwi\u0105zania dla problemu trwa\u0142ego ma\u0142\u017Ce\u0144stwa. Algorytm ten prowadzi do utworzenia stabilnych par. W zale\u017Cno\u015Bci od sposobu u\u017Cycia algorytm pozwala on znale\u017A\u0107 optymalne rozwi\u0105zania dla jednej z dw\u00F3ch grup uczestnik\u00F3w. W 1962 roku David Gale i Lloyd Shapley udowodnili, \u017Ce dla dowolnej, ale takiej samej liczby m\u0119\u017Cczyzn i kobiet jest zawsze mo\u017Cliwe znalezienie takiego rozwi\u0105zania dla problemu trwa\u0142ego ma\u0142\u017Ce\u0144stwa, aby sprawi\u0107, \u017Ce wszystkie ma\u0142\u017Ce\u0144stwa b\u0119d\u0105 trwa\u0142e, stabilne. Algorytm w spos\u00F3b uproszczony zosta\u0142 przedstawiony poni\u017Cej: 1. Ka\u017Cdy z m\u0119\u017Cczyzn prosi o r\u0119k\u0119 t\u0119 kobiet\u0119, kt\u00F3r\u0105 preferuje wzgl\u0119dem innych. 2. Ka\u017Cda kobieta notuje otrzymane propozycje w swoim karnecie. 3. W momencie, gdy ka\u017Cdy m\u0119\u017Cczyzna z\u0142o\u017Cy\u0142 propozycje swoim faworytkom, wszystkie kobiety odmawiaj\u0105 wszystkim m\u0119\u017Cczyznom, od kt\u00F3rych dosta\u0142y propozycj\u0119, poza jednym, kt\u00F3rego preferuj\u0105 ponad innych (nie jest to jednak jeszcze r\u00F3wnoznaczne z akceptacj\u0105 przez kobiet\u0119 tego preferowanego m\u0119\u017Cczyzny \u2013 chyba \u017Ce jest to tak\u017Ce zalotnik najwy\u017Cej w jej rankingu wszystkich potencjalnych kandydat\u00F3w). 4. Niewybrani m\u0119\u017Cczy\u017Ani o\u015Bwiadczaj\u0105 si\u0119 nast\u0119pnej kobiecie w ich rankingu. 5. Powr\u00F3t do punktu numer 2 lub koniec algorytmu, je\u017Celi ka\u017Cda kobieta odnalaz\u0142a swojego preferowanego, przysz\u0142ego m\u0119\u017Ca. Algorytm zawsze prowadzi do powstania stabilnych par. Aby to udowodni\u0107 za\u0142\u00F3\u017Cmy, \u017Ce \u2013 przeciwnie do stwierdzenia zawartego w poprzednim zdaniu \u2013 jeden m\u0119\u017Cczyzna, preferuje inn\u0105 kobiet\u0119 wzgl\u0119dem swojej obecnej partnerki. W takim przypadku o\u015Bwiadczy\u0142 si\u0119 jej przed poproszeniem o r\u0119k\u0119 swojej obecnej narzeczonej. Jednak\u017Ce gdyby ta kobieta r\u00F3wnie\u017C preferowa\u0142aby go wzgl\u0119dem swojego obecnego partnera, to nie przyj\u0119\u0142aby wcze\u015Bniej o\u015Bwiadczyn swojego obecnego narzeczonego. Wynikiem algorytmu odroczonej akceptacji s\u0105 zawsze najlepsze mo\u017Cliwe stabilne pary z punktu widzenia m\u0119\u017Cczyzn. Oznacza to, \u017Ce \u017Caden m\u0119\u017Cczyzna nie zmieni\u0142by swojej pary wzgl\u0119dem jakiegokolwiek innego stabilnego dopasowania. Odwr\u00F3cenie r\u00F3l m\u0119\u017Cczyzn i kobiet doprowadzi\u0142oby do powstania stabilnego dopasowania, kt\u00F3re by\u0142oby preferowane przez kobiety. Algorytm zapewnia, \u017Ce: \n* Ka\u017Cdy we\u017Amie \u015Blub Ostatecznie nie mo\u017Ce zaistnie\u0107 taka sytuacja, \u017Ce zar\u00F3wno m\u0119\u017Cczyzna, jak i kobieta nie s\u0105 zar\u0119czeni, poniewa\u017C w pewnym momencie ten m\u0119\u017Cczyzna musia\u0142 si\u0119 o\u015Bwiadczy\u0107 tej kobiecie (ostatecznie m\u0119\u017Cczyzna musia\u0142 si\u0119 o\u015Bwiadczy\u0107 ka\u017Cdej kobiecie, je\u015Bli by\u0142o to konieczne), wi\u0119c ostatecznie musia\u0142a ona przyj\u0105\u0107 jego o\u015Bwiadczyny. \n* Ma\u0142\u017Ce\u0144stwo b\u0119dzie trwa\u0142e Niech kobieta A i m\u0119\u017Cczyzna B b\u0119d\u0105 zar\u0119czeni, ale nie ze sob\u0105 nawzajem. Od zako\u0144czenia algorytmu nie jest mo\u017Cliwe, \u017Ceby A i B preferowali siebie nawzajem wzgl\u0119dem swoich obecnych partner\u00F3w. Je\u015Bli B wola\u0142by A wzgl\u0119dem swojej aktualnej partnerki, to musia\u0142by o\u015Bwiadczy\u0107 si\u0119 A przed poproszeniem o r\u0119k\u0119 swojej obecnej partnerki. Je\u015Bli A przyj\u0119\u0142a jego o\u015Bwiadczyny, a ostatecznie nie jest z nim zar\u0119czona, to musia\u0142a z nim zerwa\u0107 na rzecz kogo\u015B, kogo woli, a tym samym preferuje swojego obecnego partnera od m\u0119\u017Cczyzny B. Je\u015Bli A odrzuci\u0142a o\u015Bwiadczyny B, to znaczy, \u017Ce ju\u017C by\u0142a zar\u0119czona z kim\u015B, kogo woli od B. Algorytm ma zastosowanie w rekrutacji do szk\u00F3\u0142 w Nowym Jorku oraz Bostonie, przy przydziale sta\u017Cyst\u00F3w do szpitali w USA, a nawet do kojarzenia dawc\u00F3w organ\u00F3w z biorcami przeszczep\u00F3w."@pl . . . . "In mathematics, economics, and computer science, the Gale\u2013Shapley algorithm (also known as the deferred acceptance algorithm or propose-and-reject algorithm) is an algorithm for finding a solution to the stable matching problem, named for David Gale and Lloyd Shapley who had described it as solving both the college admission problem and the stable marriage problem.It takes polynomial time, and the time is linear in the size of the input to the algorithm. It is a truthful mechanism from the point of view of the proposing participants, for whom the solution will always be optimal."@en . . "\u0410\u043B\u0433\u043E\u0440\u0438\u0442\u043C \u0413\u044D\u0439\u043B\u0430 \u2014 \u0428\u0435\u043F\u043B\u0438 \u043D\u0430\u0445\u043E\u0434\u0438\u0442 \u0441\u0442\u0430\u0431\u0438\u043B\u044C\u043D\u043E\u0435 \u043F\u0430\u0440\u043E\u0441\u043E\u0447\u0435\u0442\u0430\u043D\u0438\u0435.\u0412\u0440\u0435\u043C\u044F \u0432\u044B\u043F\u043E\u043B\u043D\u0435\u043D\u0438\u044F \u043B\u0438\u043D\u0435\u0439\u043D\u043E \u0437\u0430\u0432\u0438\u0441\u0438\u0442 \u043E\u0442 \u0440\u0430\u0437\u043C\u0435\u0440\u0430 \u0432\u0445\u043E\u0434\u043D\u044B\u0445 \u0434\u0430\u043D\u043D\u044B\u0445 \u0430\u043B\u0433\u043E\u0440\u0438\u0442\u043C\u0430.\u0412 \u0437\u0430\u0432\u0438\u0441\u0438\u043C\u043E\u0441\u0442\u0438 \u043E\u0442 \u0442\u043E\u0433\u043E, \u043A\u0430\u043A \u043E\u043D \u0438\u0441\u043F\u043E\u043B\u044C\u0437\u0443\u0435\u0442\u0441\u044F, \u043E\u043D \u043C\u043E\u0436\u0435\u0442 \u043D\u0430\u0439\u0442\u0438 \u043B\u0438\u0431\u043E \u0440\u0435\u0448\u0435\u043D\u0438\u0435, \u043E\u043F\u0442\u0438\u043C\u0430\u043B\u044C\u043D\u043E\u0435 \u0434\u043B\u044F \u0443\u0447\u0430\u0441\u0442\u043D\u0438\u043A\u043E\u0432 \u0441 \u043E\u0434\u043D\u043E\u0439 \u0441\u0442\u043E\u0440\u043E\u043D\u044B \u0441\u043E\u043F\u043E\u0441\u0442\u0430\u0432\u043B\u0435\u043D\u0438\u044F, \u043B\u0438\u0431\u043E \u0434\u043B\u044F \u0443\u0447\u0430\u0441\u0442\u043D\u0438\u043A\u043E\u0432 \u0441 \u0434\u0440\u0443\u0433\u043E\u0439 \u0441\u0442\u043E\u0440\u043E\u043D\u044B.\u0410\u043B\u0433\u043E\u0440\u0438\u0442\u043C \u043E\u0431\u0435\u0441\u043F\u0435\u0447\u0438\u0432\u0430\u0435\u0442 \u0447\u0435\u0441\u0442\u043D\u044B\u0439 \u043C\u0435\u0445\u0430\u043D\u0438\u0437\u043C \u0441 \u0442\u043E\u0447\u043A\u0438 \u0437\u0440\u0435\u043D\u0438\u044F \u0443\u0447\u0430\u0441\u0442\u043D\u0438\u043A\u043E\u0432, \u043F\u043E\u044D\u0442\u043E\u043C\u0443 \u043F\u0440\u0435\u0434\u043E\u0441\u0442\u0430\u0432\u043B\u0435\u043D\u0438\u0435 \u0443\u0447\u0430\u0441\u0442\u043D\u0438\u043A\u043E\u043C \u043D\u0435\u0432\u0435\u0440\u043D\u044B\u0445 \u0434\u0430\u043D\u043D\u044B\u0445 \u043C\u043E\u0436\u0435\u0442 \u0442\u043E\u043B\u044C\u043A\u043E \u0443\u0445\u0443\u0434\u0448\u0438\u0442\u044C \u0435\u0433\u043E \u0440\u0435\u0437\u0443\u043B\u044C\u0442\u0430\u0442. \u0410\u043B\u0433\u043E\u0440\u0438\u0442\u043C \u043D\u0430\u0437\u0432\u0430\u043D \u0432 \u0447\u0435\u0441\u0442\u044C \u0414\u044D\u0432\u0438\u0434\u0430 \u0413\u044D\u0439\u043B\u0430 \u0438 \u041B\u043B\u043E\u0439\u0434\u0430 \u0428\u0435\u043F\u043B\u0438."@ru . . . . . "Algorithme de Gale et Shapley"@fr . . . . . . . "\u0410\u043B\u0433\u043E\u0440\u0438\u0442\u043C \u0413\u044D\u0439\u043B\u0430 \u2014 \u0428\u0435\u043F\u043B\u0438 \u043D\u0430\u0445\u043E\u0434\u0438\u0442 \u0441\u0442\u0430\u0431\u0438\u043B\u044C\u043D\u043E\u0435 \u043F\u0430\u0440\u043E\u0441\u043E\u0447\u0435\u0442\u0430\u043D\u0438\u0435.\u0412\u0440\u0435\u043C\u044F \u0432\u044B\u043F\u043E\u043B\u043D\u0435\u043D\u0438\u044F \u043B\u0438\u043D\u0435\u0439\u043D\u043E \u0437\u0430\u0432\u0438\u0441\u0438\u0442 \u043E\u0442 \u0440\u0430\u0437\u043C\u0435\u0440\u0430 \u0432\u0445\u043E\u0434\u043D\u044B\u0445 \u0434\u0430\u043D\u043D\u044B\u0445 \u0430\u043B\u0433\u043E\u0440\u0438\u0442\u043C\u0430.\u0412 \u0437\u0430\u0432\u0438\u0441\u0438\u043C\u043E\u0441\u0442\u0438 \u043E\u0442 \u0442\u043E\u0433\u043E, \u043A\u0430\u043A \u043E\u043D \u0438\u0441\u043F\u043E\u043B\u044C\u0437\u0443\u0435\u0442\u0441\u044F, \u043E\u043D \u043C\u043E\u0436\u0435\u0442 \u043D\u0430\u0439\u0442\u0438 \u043B\u0438\u0431\u043E \u0440\u0435\u0448\u0435\u043D\u0438\u0435, \u043E\u043F\u0442\u0438\u043C\u0430\u043B\u044C\u043D\u043E\u0435 \u0434\u043B\u044F \u0443\u0447\u0430\u0441\u0442\u043D\u0438\u043A\u043E\u0432 \u0441 \u043E\u0434\u043D\u043E\u0439 \u0441\u0442\u043E\u0440\u043E\u043D\u044B \u0441\u043E\u043F\u043E\u0441\u0442\u0430\u0432\u043B\u0435\u043D\u0438\u044F, \u043B\u0438\u0431\u043E \u0434\u043B\u044F \u0443\u0447\u0430\u0441\u0442\u043D\u0438\u043A\u043E\u0432 \u0441 \u0434\u0440\u0443\u0433\u043E\u0439 \u0441\u0442\u043E\u0440\u043E\u043D\u044B.\u0410\u043B\u0433\u043E\u0440\u0438\u0442\u043C \u043E\u0431\u0435\u0441\u043F\u0435\u0447\u0438\u0432\u0430\u0435\u0442 \u0447\u0435\u0441\u0442\u043D\u044B\u0439 \u043C\u0435\u0445\u0430\u043D\u0438\u0437\u043C \u0441 \u0442\u043E\u0447\u043A\u0438 \u0437\u0440\u0435\u043D\u0438\u044F \u0443\u0447\u0430\u0441\u0442\u043D\u0438\u043A\u043E\u0432, \u043F\u043E\u044D\u0442\u043E\u043C\u0443 \u043F\u0440\u0435\u0434\u043E\u0441\u0442\u0430\u0432\u043B\u0435\u043D\u0438\u0435 \u0443\u0447\u0430\u0441\u0442\u043D\u0438\u043A\u043E\u043C \u043D\u0435\u0432\u0435\u0440\u043D\u044B\u0445 \u0434\u0430\u043D\u043D\u044B\u0445 \u043C\u043E\u0436\u0435\u0442 \u0442\u043E\u043B\u044C\u043A\u043E \u0443\u0445\u0443\u0434\u0448\u0438\u0442\u044C \u0435\u0433\u043E \u0440\u0435\u0437\u0443\u043B\u044C\u0442\u0430\u0442. \u0410\u043B\u0433\u043E\u0440\u0438\u0442\u043C \u043D\u0430\u0437\u0432\u0430\u043D \u0432 \u0447\u0435\u0441\u0442\u044C \u0414\u044D\u0432\u0438\u0434\u0430 \u0413\u044D\u0439\u043B\u0430 \u0438 \u041B\u043B\u043E\u0439\u0434\u0430 \u0428\u0435\u043F\u043B\u0438."@ru . . . . . "26978338"^^ . "Algorytm odroczonej akceptacji (inaczej zwany algorytmem Gale\u2019a-Shapleya) jest algorytmem, kt\u00F3rego celem jest znalezienie rozwi\u0105zania dla problemu trwa\u0142ego ma\u0142\u017Ce\u0144stwa. Algorytm ten prowadzi do utworzenia stabilnych par. W zale\u017Cno\u015Bci od sposobu u\u017Cycia algorytm pozwala on znale\u017A\u0107 optymalne rozwi\u0105zania dla jednej z dw\u00F3ch grup uczestnik\u00F3w. W 1962 roku David Gale i Lloyd Shapley udowodnili, \u017Ce dla dowolnej, ale takiej samej liczby m\u0119\u017Cczyzn i kobiet jest zawsze mo\u017Cliwe znalezienie takiego rozwi\u0105zania dla problemu trwa\u0142ego ma\u0142\u017Ce\u0144stwa, aby sprawi\u0107, \u017Ce wszystkie ma\u0142\u017Ce\u0144stwa b\u0119d\u0105 trwa\u0142e, stabilne."@pl . . . "14205"^^ . . "L'algorithme de Gale et Shapley est un algorithme qui r\u00E9sout le probl\u00E8me des mariages stables."@fr . . . . . . "Gale\u2013Shapley algorithm"@en . . . "\u0410\u043B\u0433\u043E\u0440\u0438\u0442\u043C \u0413\u044D\u0439\u043B\u0430 \u2014 \u0428\u0435\u043F\u043B\u0438"@ru . . "In mathematics, economics, and computer science, the Gale\u2013Shapley algorithm (also known as the deferred acceptance algorithm or propose-and-reject algorithm) is an algorithm for finding a solution to the stable matching problem, named for David Gale and Lloyd Shapley who had described it as solving both the college admission problem and the stable marriage problem.It takes polynomial time, and the time is linear in the size of the input to the algorithm. It is a truthful mechanism from the point of view of the proposing participants, for whom the solution will always be optimal."@en . . . . "Algorytm odroczonej akceptacji"@pl . . . . . . . . . . .