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

''Özgür Yazılım ve Açık Kaynak Günleri 2005'' Filmleri #1: Miguel de Icaza

butch

Özgür Yazılım ve Açık Kaynak Günleri 2005 sunum kayıtları yayınlanmaya başladı. Sizleri Miguel de Icaza'nın "The Linux Desktop & Mono Development Platform" sunumuyla başbaşa bırakıyoruz. Filmlere open.bilgi.edu.tr/freedays adresinden ulaşabilirsiniz. Diğer filmler de yolda.

Linux Semineri : Linux İşletim Sistemi

dfisek

Linux Kullanıcıları Derneği, Cumartesi günü İstanbul'da Internet Teknolojileri Derneği'nin ev sahipliği yaptığı bir linux semineri düzenliyor. Özellikle linux'a yeni başlamak isteyenlere hitap eden ve linux işletim sisteminin genel özellikleri ile kullanım alanlarının anlatılacağı seminer saat 15.00'te başlayacak. - Ayrıntılı Bilgi -

Özgür Yazılım Günleri ve Açık Kaynak Günleri Başlıyor.

vst

Bilgi Üniversitesi'nde 4 Mart Cuma ve 5 Mart Cumartesi günboyu sürecek olan "Özgür Yazılım ve Açık Kaynak Günleri/2005" başlıyor. Gnome ve Mono projelerinin kurucusu Miguel de Icaza, Avrupa Özgür Yazılım Vakfı Başkanı Georg Greve ve OpenOffice.org proje grubu yöneticisi Louis Suarez-Potts'un katılımlarıyla gerçekleşecek etkinliğe herkes davetli. Etkinliğin web sitesinden ayrıntılı bilgiye ve etkinlik programına ulaşabilirsiniz.

LKD - Özgür Yazılım, Linux, GNOME, Mono: Yakın Tarih Semineri

anonim

Linux Kullanıcıları Derneği, IBM İstanbul Linux Serbest Yazılım Merkezi'nde, 22 Eylül Perşembe günü, Saat 17:00'de Enver Altın tarafından sunulacak "Özgür Yazılım, Linux, GNOME, Mono: Yakın tarih" isimli semineri düzenleyecek.
Katılımın ücretsiz ve herkese açık olduğu seminere konuyla ilgilenen herkesi bekliyoruz.

Ayrıntılı bilgi: Seminer Çalışma Grubu web sayfası

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 -