Efsane Bilgisayar Bilimci Prof. Rusins Freivalds'ın Boğaziçi'ndeki Semineri

0
FZ
Boğaziçi Üniversitesi Bilgisayar Mühendisliği bölümünden Prof. Cem Say bildiriyor:

"Letonya Bilimler Akademisi üyesi ünlü TCS'cı Rusins Freivalds (1975'te olasılıksal algoritmaların deterministik olanlara bir üstünlüğü olduğunun ilk ispatını yaptı, 1981'de sonlu bellekli ve "az hatalı" olasılıksal makinelerin sonlu bellekli deterministik makinelerden daha güçlü olduğunu ispatladı, state sayısı avantajının boyutunu da daha yeni ispatlamış görünüyor,) 17 Kasım Pazartesi günü bölümümüzü ziyaret edecek, sanırım saat 14'te de bir seminer verecek (özet aşağıda). Davetlisiniz."
Nonconstructive methods in finite automata

Rusins Freivalds
(University of Latvia)

A.Ambainis and R.Freivalds proved in 1998 that for recognition of some languages quantum finite automata can have smaller number of states than deterministic ones, and this difference can even be exponential. The proof contained a slight non-constructiveness, and the exponent was not shown explicitly. For probabilistic finite automata, the exponentiality of such a distinction was not yet proved. The best (smaller) gap was proved by Ambainis in 1996. The languages considered by Ambainis/Freivalds were presented explicitly, but the exponent was not. In a very recent paper by R.Freivalds the non-constructiveness is modified, and an explicit (and seemingly much better) exponent is obtained at the expense of having only non-constructive description of the languages used.

Moreover, the best estimate proved in this paper is proved under assumption of the well-known Artin's Conjecture (1927) in Number Theory. The paper contains also a theorem that does not depend on any open conjectures but the estimate is worse, and the description of the languages used is even less constructive. This seems to be the first result in finite automata depending on open conjectures in Number Theory.

Görüşler

0
oetzi_
Seminer saati ve yerini kesinleştirebilir misiniz.
Görüş belirtmek için giriş yapın...

İlgili Yazılar

İstanbul ve Kayseri´de Linux Seminerleri

dfisek

Linux Kullanıcıları Derneği 24 Mayıs Cumartesi günü İstanbul Marmara Üniversitesi'nde, 30 Mayıs Cuma günü de Kayseri Erciyes Üniversitesi'nde Linux seminerleri düzenliyor.

Seminerler her zaman olduğu gibi herkesin katılımına açık ve ücretsiz.

Yeni Yıla İlk Selam!

anonim

Linux Kullanıcıları Derneği tarafından düzenlenen "LKD Yeni Yıl Partisi" 18 Aralık 2004 Cumartesi günü saat 21:30'da İstanbul Beşiktaş'taki Elma Cafe'de gerçekleşecektir. Tanışmak, hasret gidermek, kaynaşmak ve kaynaşırken kaynatmak amaçlı düzenlenen partiye tüm özgür yazılımcılar davetlidir.

Ayrıntılı bilgi ve partiye kayıt için: tıklayın

Linux Semineri : Linux nedir? Ne sunar?

dfisek

Linux Kullanıcıları Derneği, Çarşamba günü Ankara Üniversitesi'nde saat 18.30'da linux semineri düzenliyor. Linux ile tanışmak isteyen ya da yeni başlayan kullanıcıları hedefleyen seminerde linux'un ne olduğu ne tür işlerde kullanılabileceği anlatılacak. - Ayrıntılı bilgi -

5 Ocak Penguenler Buluşuyor

penguencg

5 Ocak Cumartesi günü Ankara EMO (Elektrik Mühendisleri Odası) eğitim salonunda[1] 13.00'da buluşalım diyoruz. Yeni yılın başında hevesli penguenlerle buluşmak, dernekte yeni yılda neler yapacağımızdan bahsetmek ve katkı vermek isteyenlerle bir araya gelmek istiyoruz. Eğer siz de bu buluşmaya katılmak istiyorsanız bize iletişim bilgilerinizi (telefon numarası) göndererek[2] haber verebilirsiniz.

Bursa'da Linux Seminerleri

anonim

Linux Kullanıcıları Derneği, 27 Haziran Cuma günü Bursa'da linux seminerleri düzenliyor. Bir gün boyunca Bursa'daki penguenleri bir araya toplamayı hedefleyen etkinlikte özellikle kurumlara yönelik linux uygulamaları anlatılacak. -Ayrıntılı Bilgi-