Exaktní reálná aritmetika

Přednášející:

Petr Kůrka (gar.)

Cvičící:

Petr Kůrka (gar.)

Předmět zajišťuje:

katedra teoretické informatiky

Anotace:

Obecné vlastnosti císelnych soustav a príslusnych aritmetickych algoritmu, teorie algoritmu ve spojitych oborech a jejich vypocetní slozitost, algoritmy a datové struktury pro nekonecná slova.

Požadavky:

Osnova přednášek:

1.Cantoruv prostor a symbolická reprezentace kompaktních metrickych prostoru.

2.Symbolická dynamika: posuny a celulární automaty.

3.Císelné soustavy: pozicní soustavy, retezové zlomky, moebiovské soustavy.

4.Redundance, rychlost konvergence a aproximace v císelnych soustavách.

5.Konstruktivní analyza: konstruktivní (algoritmická) reálná císla a konstruktivní reálné funkce.

6.Slozitost reálnych funkcí, mocninné rady a Gaussovy retezové zlomky.

7.Teorie domén: usporádání a svazy, monotónní funkce a jejich pevné body, rekursivní definice

8.Aritmetické algoritmy: celocíselná aritmetika, intervalová aritmetika, algoritmy pro redundantní soustavy.

9.Paralelismus v aritmetickych algoritmech.

10.Vypocetní slozitost aritmetickych algoritmu.

11.Modulární a p-adická aritmetika.

Osnova cvičení:

Cíle studia:

Studijní materiály:

P.Kurka: Topological and symbolic dynamics, Société Mathématique de France, 2003, ISBN 2856291430.

M.B.Pour-El, J.I.Richards: Computability in analysis and physics, Springer-Verlag 1989, ISBN 0387500359.

Ker-I Ko: Complexity theory of real functions, Birkhauser 1991, ISBN 3764335866.

P.Kurka, A.Kazda: Moebius number systems based on interval covers, Nonlinearity 2010.

S.Abramsky, A.Jung: Domain theory, Handbook of Logic in Computer Science vol. 3, Clarendon Press 1994, ISBN 0198537816.

Poznámka:

Rozvrh na zimní semestr 2011/2012:

Rozvrh není připraven

Rozvrh na letní semestr 2011/2012:

Rozvrh není připraven

Předmět je součástí následujících studijních plánů:

• Informatika (VO)