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

Linux Semineri : Ecartis E-Posta Liste Yöneticisi

dfisek

Linux Kullanıcıları Derneği, Çarşamba günü Ankara'da linux semineri düzenliyor. 18.30'da başlayacak seminerde, ecartis (eski adıyla listar) yazılımının tanıtımı, nasıl kurulduğu, nasıl yapılandırıldığı, son olarak da liste arşivinin tutulması ve webden yayınlanması anlatılacak. - Ayrıntılı bilgi -

30 Eylül ''İzmir'de şenlik yapsak nasıl olur?'' toplantısı

penguencg

İzmirdeki Linux kullanıcıları olarak toplanıyoruz. Bu ayın 30'u Pazar günü hemen herkese uygun gözüktü ve biz de bu tarihte ikinci bir toplantı ile hem birbirimizi tanıyalım, hem İzmir'deki insan gücünü biraz harekete geçirelim, hem de bu seneki şenlik fikrilerini alalım diye toplanalım diyoruz. Toplantı gündeminde ağırlıklı olarak bu seneki şenlik, yeri, İzmir'de yapalım mı yaparsak nasıl yapalım gibi konular olacaktır. Bunun yanında fikirleri olanlar, şikayetleri olanlar, abicim İzmir'de Linux kullanıcısı var mı, nerede veya benim fikrim geldi diyenler için tanışma kaynaşma ortamı doğacaktır. Çekinmeden, LKD üyesi veya değil, Linux meraklısı herkesin gelmesini istiyoruz.

Bizbize, eğlenceli bir toplantı yapmak istiyoruz.

7. Linux ve Özgür Yazılım Şenliği

oguzy

Her yıl geleneksel hale gelen Linux ve Özgür Yazılım Şenliği bu sene "şenlik" tadında İzmir'de gerçekleşecek. Tüm Linux severler ve ilgililer davetlidir.

Ankara Penguen Pikniği

penguencg

Merhaba arkadaşlar,

Baharın gelişiyle beraber penguenlerin kendilerini çimenlere atması için pikniğe gidiyoruz. Şehrin gürültüsünden ve kalabalığından uzak sohbeti, eğlencesi bol güzel bir gün geçirmek için sizi de penguen pikniğine bekliyoruz.

Özgür Yazılım ve Açık Kaynak Günleri 2006'nın ardından

tongucyumruk

Soru: Özgür Yazılım ve Açık Kaynak Günleri'nin en kötü yanı nedir?
Cevap: Bitmesi

Evet, Türkiye'nin ve dünyanın dört bir yanından gelen konukları dinlediğimiz, sadece dinlemekle kalmayıp gerektiğinde tartıştığımız, sanal alemden tanıdığımız insanlarla yüzyüze görüşme fırsatı bulduğumuz, eski dostlarla hasret giderme, yeni insanlarla tanışma şansı yakaladığımız bir Özgür Yazılım ve Açık Kaynak Günleri daha sona erdi. Gidenler zaten orada dinledi, tartıştı, eğlendi. Geriye de gitmeyenleri kıskandırmak, gelecek yıl gelmelerini garanti etmek için olan bitenleri yazmak kaldı.