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

Ruby on Rails Semineri..

anonim

Linux Kullanıcıları Derneği, EMO'nun desteği ile 12 Kasım 2005 tarihinde İstanbul Elektrik Mühendisleri Odası'nda "Ruby on Rails" semineri düzenliyor. Hüseyin Gömleksizoğlu'nun vereceği seminer saati 13:30. Seminer, önceki LKD seminerleri gibi herkesin katılımına açık ve ücretsiz. Herkesi bekliyoruz!

Ayrıntılı bilgi için: http://seminer.linux.org.tr/

İNETD Pardus 2007'nin Yenilikleri Semineri (Uygulamalı)

adervis

İNETD Seminerleri başlıyor!

Yılın ilk semineri; Pardus 2007'nin Yenilikleri

İnternet Teknolojileri Derneği tarafından, 13 Ocak 2007 tarihinde "Pardus 2007'nin Yenilikleri" konulu seminer düzenlenecek.

İNETD Semineri: Web Uygulama Güvenliği

adervis

IBM Linux Merkezi'nde yapılan İnternet Teknolojileri Derneği Seminerleri, 10 Şubat 2007 saat 14:00'da Fırat OKAY'ın "Web Uygulama Güvenliği" konulu semineri ile devam ediyor.
Seminerler herzaman olduğu gibi herkese açık ve ücretsiz.

II. Bilgisayar Mühendisleri Buluşması

mkis

EMO İzmir Şubesi Bilgisayar Mühendisliği Meslek Dalı Komisyonu, Bilgisayar Mühendislerine yönelik olarak, mesleki sorunların tartışılması ve meslek alanının düzenlenmesi, hakların korunması gibi konular üzerine çalışan BM-MDK’nın tanıtımını hedef alan bir forum düzenliyor: II. BİLGİSAYAR MÜHENDİSLERİ BULUŞMASI

17-18 Nisan Etkinlik Programı

butch

Bildiğiniz gibi bu yıl Özgür Yazılım ve Açık Kaynak Günleri ve Linux ve Özgür Yazılım Şenliği etkinlikleri birlikte düzenleniyor. Ortak etkinliğin bugün duyurulan programına bu adresten ulaşabilirsiniz.