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.

Eskişehir'de Java Günü

anonim

Türkiye Bilişim Derneği Eskişehir Şubesi, Sun Microsystems, Java Teknolojileri Derneği, Osmangazi Üniversitesi Bilgisayar ve Bilişim Teknolojileri Kulübü işbirliğiyle Sun Microsystems ve Java Teknolojileri Derneği'nin düzenlemiş olduğu üniversite turlarının bu seferki durağı Eskişehir Osmangazi Üniversitesi. 8 Aralık 2005 günü Prof. Dr. Suat Mirza Konferans Salonunda düzenlenecek etkinliğe katılım Ücretsizdir !!!

Detaylar icin eskisehir.tbd.org.tr

Neden Kuantum Kriptografi?

FZ

İstanbul Bilgi Üniversitesi Bilgisayar Bilimleri bölümünce düzenlenen haftalık seminer dizisinin bu haftaki konuğu Aarhus Üniversitesi Bilgisayar Bilimleri bölümünden Thomas Pedersen.

Linux Semineri : Veritabanına Giriş

dfisek

Linux Kullanıcıları Derneği, Çarşamba günü Ankara Üniversitesi'nde linux semineri düzenliyor. Saat 18.30'da başlayacak seminerde; veritabanı tanımı, nerelerde ve hangi amaçlar icin kullanıldığı, önemli veritabani sunucuları ve hangi amaç için hangi sunucuların kullanılabileceği anlatılacak. - Ayrıntılı bilgi -

Linux Semineri : SuSe Linux Kurulumu

dfisek

Linux Kullanıcıları Derneği, Cumartesi günü Istanbul'da Linux'a sorunsuz ve kolay başlangıç yapmak isteyenlere yönelik bir linux semineri düzenliyor. Günümüzün popüler dağıtımlarından olan SuSe Linux'un kurulumunun, basit ayarlarının, YAST2 kullanımının anlatılacağı seminer boyunca Linux hakkında temel bilgiler verilecek, karşılaşılabilecek potansiyel problemlerden ve çözümlerinden bahsedilecek. Internet Teknolojileri Derneği'nin ev sahipliği yaptığı seminer saat 15.00'te başlıyor. - Ayrıntılı Bilgi -