Mechatronika, Optika és Gépészeti Informatika Tanszék Kovács Endre tud. Mts.
• A Számítástudomány alapjai Szemelvények az Elméleti Számítástudomány területérıl
• A Számítógépek felépítése, mőködési módjai Mikroprocesszoros Rendszerek Felépítése – Architektúra – Utasítás végrehajtás – Speciális folyamatok (Interrupt, Direct Memory Access = közvetlen memória hozzáférés
• A Számítógépek hardverelemei Korszerő perifériák és rendszercsatolásuk – Grafikus megjelenítı egységek
Számítógépek •Analóg számítógépek Differenciálegyenlet megoldása, mechanikai rendszerek dinamikus vizsgálata, szimuláció.
Pld: Az analóg számítógéppel történı differenciálegyenlet megoldás lépései •kezdeti feltételek beállítása •számítás (futtatás) •tartás (mérhetıség biztosítása)
Számítógépek •Digitális számítógépek EDSAC (Electronic Delay Storage Automatic Calculator)
ENIAC (Electronic Numerical Integrator and Computer)
A Neumann-elvek: - teljesen elektronikus számítógép; - kettes számrendszer alkalmazása; - aritmetikai egység alkalmazása (univerzális Turing-gép); - központi vezérlıegység alkalmazása; - belsı program- és adattárolás.
Számítógépek •Digitális számítógépek
Számítógépek •Digitális számítógépek
A megjelenés, méret nem tükrözi a felépítést
Elektronikai technológiai fejlıdés
Fogalmak: • Digitális Diszkrét értékeket tároló, Számjegyvezérléső
• Bináris Kettes számrendszert alkalmazó
• Mikroprocesszor Egy digitális számítógép központi vezérlı és arithmetikai egységének szerepét ellátni képes (egy vagy több chipen létrehozott) áramkör együttes.
• Mikroprocesszoros rendszer = (mikro)Számítógép Egy programvégrehajtásra alkalmas, mikroprocesszort, mint CPU-t tartalmazó, Operatív tárral, I/O egységekkel ellátott rendszer.
Mechatronika, Optika és Gépészeti Informatika Tanszék Kovács Endre tud. Mts.
A Számítástudomány alapjai Szemelvények az Elméleti Számítástudomány területérıl
Fogalmak: • Számítástechnika Realizáció, technológia
• Elméleti számítástudomány Matematikai elméleti tudományág
Kurt Gödel (1906-1978) egy cseh származású (Brünn) amerikai matematikus volt, többek között logikával foglalkozott. Híres "eldönthetetlenségi elmélete" - mely szerint minden szigorúan logikus matematikai rendszerben vannak olyan állítások, amelyeknek az igaz vagy hamis volta nem igazolható a rendszer axiómái alapján.
Alonzo Church (1903-1995.) amerikai matematikus és logikus, a számítástudomány (computer science) egyik megalapozója. (lambda-kalkulus, számítási modellek)
Alan Mathison Turing (1912-1954) brit matematikus, a modern számítógép-tudomány egyik atyja.
(Turing gép, megállási probléma)
Turing koncepciója, a Turing gép megfogalmazása • • • • • •
Külsı adat és tárolóterület: végtelen szalag, amelynek egymás után cellái vannak, amelyek vagy üresek, vagy jelöltek. A gép egyszere egy cellával foglalkozik (Az író/olvasó feje egy cellán áll). A szalagon tud jobbra-balra lépni, tud jelet olvasni, törölni és írni. A bevitel, a számítás és a kivitel minden konkrét esetben véges marad, ezen túl a szalag üres.(0) A gép belsı állapotait számozzuk meg 0,1,2,... A gép mőködését megadja egy explicit helyettesítési táblázat. Állapot, bemenet --> Állapot, kimenet, fejmozgás
Church - Turing tétel Ha egy algoritmus elég mechanikus és világos, akkor bizonyára található olyan Turing-gép, amely azt végrehajtja. A Turing gép definiálja mindazt, amit matematikailag algoritmikus eljárás alatt értünk. Minden más algoritmikus eljárást végrehajtó rendszer ekvivalens valamely Turing-géppel.
Algoritmus Köznyelvben: Egy véges utasítássorozat (pl. telefonfülke, telefonálás tevékenység) Véges utasítássorozat, amely bármely input esetén véges lépésszám után megáll, eredményt ad. (A végrehajtó automata stabil állapotba kerül.)
„Algoritmus jelölt” Szg. Program írható
Kiszámíthatóság Eljárás Emberi szóval megfogalmazott feladat Az Algoritmus fogalmára formális definíciónk nincs!
???
NEM minden eljárás algoritmus !!
Algoritmus
Church - tézise Maga a Turing gép matematikai leírása az algoritmus fogalmának formális definíciója.
Automata elmélet Pld: determinisztikus véges állapotú automata (DFA deterministic finite state machine)
0 1 S1
S2
S1
S2
S1
S2
M automata bemenete: 0,1-bıl álló string Feladata, meghatározni, hogy a bemeneti stringben páros számú 0 karakter van-e. M = (S, Σ, T, s, A), ahol •Σ = {0, 1}, •S = {S1, S2}, •s = S1, •A = {S1}, és •A T átmeneti függvényt a következı állapot átmeneti tábla határozza meg:
Turing gép „Minden digitális számítógép İS ÖREGANYJA”
A
C
9
E
Író-olvasó fej Központi vezérlı egység
Verem automata, Véges utasításkészlet
Belsı állapottér (regiszterek)
Turing gép megállási problémája: Nem tudjuk, hogy adott programmal megáll-e ! Van-e arra bizonyítási módszerünk, hogy egy eljárás biztosan algoritmus-e? NINCS !!
Példa nem algoritmizálható problémára: (Nem kiszámítható feladat)
Dominópélda Dominó (egy példány) Dominó típus (megszámlálhatóan végtelen példány) Dominó készlet (definíciója: 3, 2,4,9,5, 1,6,2,7, 4,5,3,1) Kérdés: A definiált dominókészlettel lefedhetı-e a teljes sík: Válasz: IGEN vagy NEM ?????
Komplexitás (Algoritmusok bonyolultsága) Komplexitás vizsgálata, ha már tudjuk, hogy az adott problémára létezik algoritmus, azaz a probléma kiszámítható. •Idı komplexitás •Tárkomplexitás Exponenciális bonyolultság
Idı komplexitás
Polinomiális bonyolultság
(lépésszám) Lineáris bonyolultság Konstans bonyolultság
Bemenetek bonyolultsága
