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

Web Güvenliği Günleri - 1

anonim

OWASP-Türkiye ve Web Güvenliği Topluluğu olarak devamını getirmeyi düşündüğümüz etkinliklerimizin birincisinin detaylarını sizinle paylaşmaktan mutluluk duyarız.

Web Güvenliği Günleri'nde yoğun ve teknik şekilde web uygulaması atakları, savunma, güvenli kodlama ve benzer bir çok konulara değinilecektir. Bu birinci bir günlük etkinliğimizde daha çok orta ve ileri seviye web saldırına değineceğiz.

IV. Bilim Günleri: Matematiğin Milenyum Problemleri

FZ

Boğaziçi Üniversitesi Bilim Kulübü tarafından düzenlenen IV. Bilim Günleri etkinliği kapsamında 6 Nisan 2004, Salı günü Prof. Dr. Mete Soner konuşacak.

Dr. Soner'in konuşmasının başlığı: Matematiğin Milenyum Problemleri ve Akışkanlar Mekaniği.

Konuşma 15:00 - 17:00 saatleri arasında Öğrenci Faaliyetleri Binasında gerçekleşecek.

Fazlamesai.net Ankara´da!

anonim

Linux Kullanıcıları Derneği'nin 30 Mayıs'ta düzenlediği bir seminerde Fazlamesai.net tam kadro bulunacak. Fazlamesai.net projesinin gelişimi, uygulanması, çeşitli serbest yazılımlar vasıtasıyla hayata geçirilmesi anlatılacak. 18.30'da başlayacak olan seminer Ankara Üniversitesi Fen Fakültesi'nde.

YTÜ Açık Kaynak Kodu Günü 2008

coskung

Etkinlik sitesinden alıntı:

Yıldız Teknik Üniversitesi Bilişim Kulübü bünyesinde çalışmakta olan YTÜLinux Grubu'nun üyeleri olarak 19 Nisan 2008'de açık kaynak kodu günü düzenliyoruz. Bu etkinliği düzenlemekteki amaçlarımız: Açık kaynak kodu, unix, linux gibi konularda aktif olarak çalışan grupların başarılarını bu alanla ilgili insanlara anlatması ve tanıtması,

7D9 Demo Party - 19-20 Aralık 2009

Alcofribas

7D9 Demo Party; programlama, dijital sanat ve dijital müzik meraklılarını bir araya getiriyor. Her yıl düzenlenen 7DX Party serisinin sekizincisi 19-20 Aralık 2009 tarihlerinde Boğaziçi Üniversitesi’nde gerçekleşecek. Bilgisayarların sınırlarını zorlayan gösteri demolarına, demoscene’e, görsel programcılığa, dijital sanatlara ve dijital müziklere ilgi duyanlar bu organizasyonda bir araya gelecek. PC, Amiga, Commodore 64 gibi bilgisayarlar için programlama, grafik ve müzik alanında çok sayıda yarışma yapılacak.