This HTML5 document contains 63 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

Prefix	IRI
dcterms	http://purl.org/dc/terms/
dbo	http://dbpedia.org/ontology/
foaf	http://xmlns.com/foaf/0.1/
n4	http://dbpedia.org/resource/File:
n11	https://global.dbpedia.org/id/
dbpedia-ru	http://ru.dbpedia.org/resource/
dbt	http://dbpedia.org/resource/Template:
rdfs	http://www.w3.org/2000/01/rdf-schema#
n5	http://www.sephlietz.com/gale-shapley/
dbpedia-pl	http://pl.dbpedia.org/resource/
n8	http://commons.wikimedia.org/wiki/Special:FilePath/
rdf	http://www.w3.org/1999/02/22-rdf-syntax-ns#
owl	http://www.w3.org/2002/07/owl#
wikipedia-en	http://en.wikipedia.org/wiki/
dbpedia-fr	http://fr.dbpedia.org/resource/
dbc	http://dbpedia.org/resource/Category:
dbp	http://dbpedia.org/property/
prov	http://www.w3.org/ns/prov#
xsdh	http://www.w3.org/2001/XMLSchema#
wikidata	http://www.wikidata.org/entity/
dbr	http://dbpedia.org/resource/

Statements

Subject Item

dbr:Gale–Shapley_algorithm

rdfs:label

Algorithme de Gale et Shapley Gale–Shapley algorithm Алгоритм Гэйла — Шепли Algorytm odroczonej akceptacji

rdfs:comment

L'algorithme de Gale et Shapley est un algorithme qui résout le problème des mariages stables. In mathematics, economics, and computer science, the Gale–Shapley 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. Алгоритм Гэйла — Шепли находит стабильное паросочетание.Время выполнения линейно зависит от размера входных данных алгоритма.В зависимости от того, как он используется, он может найти либо решение, оптимальное для участников с одной стороны сопоставления, либо для участников с другой стороны.Алгоритм обеспечивает честный механизм с точки зрения участников, поэтому предоставление участником неверных данных может только ухудшить его результат. Алгоритм назван в честь Дэвида Гэйла и Ллойда Шепли. Algorytm odroczonej akceptacji (inaczej zwany algorytmem Gale’a-Shapleya) jest algorytmem, którego celem jest znalezienie rozwiązania dla problemu trwałego małżeństwa. Algorytm ten prowadzi do utworzenia stabilnych par. W zależności od sposobu użycia algorytm pozwala on znaleźć optymalne rozwiązania dla jednej z dwóch grup uczestników. W 1962 roku David Gale i Lloyd Shapley udowodnili, że dla dowolnej, ale takiej samej liczby mężczyzn i kobiet jest zawsze możliwe znalezienie takiego rozwiązania dla problemu trwałego małżeństwa, aby sprawić, że wszystkie małżeństwa będą trwałe, stabilne.

foaf:depiction

n8:Gale-Shapley.gif n8:DA-men-optimality.png

dcterms:subject

dbc:Stable_matching dbc:Algorithms dbc:Lloyd_Shapley

dbo:wikiPageID

26978338

dbo:wikiPageRevisionID

1100670229

dbo:wikiPageWikiLink

dbr:Deferred-acceptance_auction n4:DA-men-optimality.png dbr:Algorithm dbc:Lloyd_Shapley dbr:David_Gale dbr:Lattice_of_stable_matchings dbr:RStudio dbr:Iteration dbr:Hospital_resident dbr:Computer_science dbr:United_States_Naval_Research_Laboratory dbr:Nobel_Memorial_Prize_in_Economic_Sciences dbc:Stable_matching dbr:Application_programming_interface dbr:Stable_matching_problem dbr:R_(programming_language) dbr:Linear_time dbr:Alvin_E._Roth dbr:Mathematics dbr:National_Resident_Matching_Program dbr:Economics dbr:MATLAB dbr:Lloyd_Shapley dbr:Truthful_mechanism n4:Gale-Shapley.gif dbr:Python_(programming_language) dbc:Algorithms dbr:Polynomial_time dbr:Market_design

dbo:wikiPageExternalLink

n5:

owl:sameAs

n11:9yzdd dbpedia-pl:Algorytm_odroczonej_akceptacji dbpedia-fr:Algorithme_de_Gale_et_Shapley wikidata:Q65123731 dbpedia-ru:Алгоритм_Гэйла_—_Шепли

dbp:wikiPageUsesTemplate

dbt:Ordered_list dbt:Reflist dbt:Mvar dbt:Main dbt:Short_description

dbo:thumbnail

n8:Gale-Shapley.gif?width=300

dbo:abstract

Algorytm odroczonej akceptacji (inaczej zwany algorytmem Gale’a-Shapleya) jest algorytmem, którego celem jest znalezienie rozwiązania dla problemu trwałego małżeństwa. Algorytm ten prowadzi do utworzenia stabilnych par. W zależności od sposobu użycia algorytm pozwala on znaleźć optymalne rozwiązania dla jednej z dwóch grup uczestników. W 1962 roku David Gale i Lloyd Shapley udowodnili, że dla dowolnej, ale takiej samej liczby mężczyzn i kobiet jest zawsze możliwe znalezienie takiego rozwiązania dla problemu trwałego małżeństwa, aby sprawić, że wszystkie małżeństwa będą trwałe, stabilne. Algorytm w sposób uproszczony został przedstawiony poniżej: 1. Każdy z mężczyzn prosi o rękę tę kobietę, którą preferuje względem innych. 2. Każda kobieta notuje otrzymane propozycje w swoim karnecie. 3. W momencie, gdy każdy mężczyzna złożył propozycje swoim faworytkom, wszystkie kobiety odmawiają wszystkim mężczyznom, od których dostały propozycję, poza jednym, którego preferują ponad innych (nie jest to jednak jeszcze równoznaczne z akceptacją przez kobietę tego preferowanego mężczyzny – chyba że jest to także zalotnik najwyżej w jej rankingu wszystkich potencjalnych kandydatów). 4. Niewybrani mężczyźni oświadczają się następnej kobiecie w ich rankingu. 5. Powrót do punktu numer 2 lub koniec algorytmu, jeżeli każda kobieta odnalazła swojego preferowanego, przyszłego męża. Algorytm zawsze prowadzi do powstania stabilnych par. Aby to udowodnić załóżmy, że – przeciwnie do stwierdzenia zawartego w poprzednim zdaniu – jeden mężczyzna, preferuje inną kobietę względem swojej obecnej partnerki. W takim przypadku oświadczył się jej przed poproszeniem o rękę swojej obecnej narzeczonej. Jednakże gdyby ta kobieta również preferowałaby go względem swojego obecnego partnera, to nie przyjęłaby wcześniej oświadczyn swojego obecnego narzeczonego. Wynikiem algorytmu odroczonej akceptacji są zawsze najlepsze możliwe stabilne pary z punktu widzenia mężczyzn. Oznacza to, że żaden mężczyzna nie zmieniłby swojej pary względem jakiegokolwiek innego stabilnego dopasowania. Odwrócenie ról mężczyzn i kobiet doprowadziłoby do powstania stabilnego dopasowania, które byłoby preferowane przez kobiety. Algorytm zapewnia, że: * Każdy weźmie ślub Ostatecznie nie może zaistnieć taka sytuacja, że zarówno mężczyzna, jak i kobieta nie są zaręczeni, ponieważ w pewnym momencie ten mężczyzna musiał się oświadczyć tej kobiecie (ostatecznie mężczyzna musiał się oświadczyć każdej kobiecie, jeśli było to konieczne), więc ostatecznie musiała ona przyjąć jego oświadczyny. * Małżeństwo będzie trwałe Niech kobieta A i mężczyzna B będą zaręczeni, ale nie ze sobą nawzajem. Od zakończenia algorytmu nie jest możliwe, żeby A i B preferowali siebie nawzajem względem swoich obecnych partnerów. Jeśli B wolałby A względem swojej aktualnej partnerki, to musiałby oświadczyć się A przed poproszeniem o rękę swojej obecnej partnerki. Jeśli A przyjęła jego oświadczyny, a ostatecznie nie jest z nim zaręczona, to musiała z nim zerwać na rzecz kogoś, kogo woli, a tym samym preferuje swojego obecnego partnera od mężczyzny B. Jeśli A odrzuciła oświadczyny B, to znaczy, że już była zaręczona z kimś, kogo woli od B. Algorytm ma zastosowanie w rekrutacji do szkół w Nowym Jorku oraz Bostonie, przy przydziale stażystów do szpitali w USA, a nawet do kojarzenia dawców organów z biorcami przeszczepów. Алгоритм Гэйла — Шепли находит стабильное паросочетание.Время выполнения линейно зависит от размера входных данных алгоритма.В зависимости от того, как он используется, он может найти либо решение, оптимальное для участников с одной стороны сопоставления, либо для участников с другой стороны.Алгоритм обеспечивает честный механизм с точки зрения участников, поэтому предоставление участником неверных данных может только ухудшить его результат. Алгоритм назван в честь Дэвида Гэйла и Ллойда Шепли. L'algorithme de Gale et Shapley est un algorithme qui résout le problème des mariages stables. In mathematics, economics, and computer science, the Gale–Shapley 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.

prov:wasDerivedFrom

wikipedia-en:Gale–Shapley_algorithm?oldid=1100670229&ns=0

dbo:wikiPageLength

14205

foaf:isPrimaryTopicOf

wikipedia-en:Gale–Shapley_algorithm