Ce se mai intâmplã in informatica teoreticã: premiul Nobel pentru economie …

a fost acordat azi lui Lloyd Shapley şi Alvin Roth. Spun „informatica teoreticã” pentru cã parte din contribuţia lui Shapley care i-a adus premiul este una pur algoritmicã: problema „mariajelor stabile” este una de care aud mulţi studenţi informaticieni care iau cursul de algoritmicã (un motiv in plus de a o preda semestrul ãsta 🙂 ).

Shapley şi David Gale au inventat un algoritm care rezolvã aceastã problemã in timp polinomial (mai precis: O(n^2) worst-case, O(n\log (n)) in medie). Problema a inspirat mai multe direcţii de cercetare in teoria algoritmicã a jocurilor, direcţii despre care am auzit o mulţime de lucruri la şcoala de varã in domeniul teoriei jocurilor din Samos la care am participat in aceastã varã.

Sunt sigur cã premiul va fi indelung comentat pe blogurile de informaticã teoreticã/teoria jocurilor (reacţiile incep deja sã aparã: vezi de exemplu legãturile de pe blogul lui Noam Nisan). Voi reveni poate cu o prezentare de popularizare a unora din aspectele algoritmice ale problemelor de „cuplaj” (eng. matching). Pânã una-alta e o zi nu foarte rea pentru informatica teoreticã 🙂

Anunțuri
Acest articol a fost publicat în informaticã teoreticã, popularizarea_ştiinţei, teoria jocurilor, Uncategorized. Pune un semn de carte cu legătura permanentă.

Lasă un răspuns

Completează mai jos detaliile tale sau dă clic pe un icon pentru a te autentifica:

Logo WordPress.com

Comentezi folosind contul tău WordPress.com. Dezautentificare / Schimbă )

Poză Twitter

Comentezi folosind contul tău Twitter. Dezautentificare / Schimbă )

Fotografie Facebook

Comentezi folosind contul tău Facebook. Dezautentificare / Schimbă )

Fotografie Google+

Comentezi folosind contul tău Google+. Dezautentificare / Schimbă )

Conectare la %s