Tudás és Specifikáció

Kurzus menete

1. Tudás és specifikáció 2. Számítógép architektúra, Alapfogalmak: adat, kifejezés 3. Alapfogalmak: utasítás, állapot OS Interpreter 4. Függvények, Lokális/Globális 5. Strukturális programozás, Git 6. Programozási paradigmák Összefoglalás 7. Algoritmusok Intro 8. Turing-gép, Halting problem, Internet architektúra, Scraping 9. Bonyolultságanalízis

Kurzus menete

1. Tudás és specifikáció 2. Számítógép architektúra, Alapfogalmak: adat, kifejezés 3. Alapfogalmak: utasítás, állapot OS Interpreter 4. Függvények, Lokális/Globális 5. Strukturális programozás, Git 6. Programozási paradigmák Összefoglalás 7. Algoritmusok Intro 8. Turing-gép, Halting problem, Internet architektúra, Scraping 9. Bonyolultságanalízis

Mit kellene tudni?

1. Megfogalmazni egy programozási problémát <!-- .element: class="fragment" --> 1. Számításelmélet értelmét elmagyarázni <!-- .element: class="fragment" --> 1. Lebontani egy komplex problémát egyszerűbbekre <!-- .element: class="fragment" --> 1. Megérteni egy leírt programot <!-- .element: class="fragment" --> 1. Megírni egy programot <!-- .element: class="fragment" --> 1. Találni érdeklődést és folytatást <!-- .element: class="fragment" --> <center><img src="https://pics.me.me/doctors-googling-stuff-online-does-not-make-you-a-doctor-61282088.png"></center> -->

Tudás típusai

Deklaratív tudás

A "mit?" kérdésre adott válasz egy probléma kapcsán

Imperatív tudás

A "hogyan" kérdésre adott válasz egy probléma kapcsán

- tervrajz - térképjelzés - anatómiai ábra - ...

- recept - IKEA útmutató - útvonalterv - ...

Mit adunk át a gépnek?

Egy probléma megoldására szeretnénk megtanítani/megkérni: tetszőleges $x$-re, számolja ki $ \sqrt{x} $-et úgy, hogy csak osztani, szorozni, meg összeadni tud

- deklaratív tudás: - $ \sqrt{x} = y \Leftrightarrow y^2=x $ - $ x < y^2 \Leftrightarrow \sqrt{x} < y $ - $ ( (y_1 < x \land y_2 < x) \lor (y_1 > x \land y_2 > x) ) \Rightarrow $ - $ \Rightarrow ( |x - y_1| < |x - y_2| \Leftrightarrow |x^2 - y_1^2| < |x^2 - y_2^2| ) $ - ... - imperatív tudás: - tippelünk egy kezdeti $ G $ -t, és ameddig nem elég jó, $ G' = \frac{G+\frac{x}{G}}{2} $ -vel közelítünk, így tetszőlegesen közel kerülünk az eredményhez (minden nemnegatív számok esetén)

Ember

okos, kreatív, tud következtetni, memóriája ködös, szeretné minél kevesebbet nyomkodni a számológépet - felhasznál csomó meglévő deklaratív tudást - összeállítja egy komplex tippelési folyamattá - tippek eredményéből továbbfejleszti a folyamatot - felhasznál olyan komplex fogalmakat mint nagyságrend, vagy előjelváltás

Gép

buta, nincs önálló gondolata, memóriája tökéletes másodpercenként töbmilliárd műveletet el tud végezni, - tippel egy nagyon rosszat, pl G = 1 - valaki megtanította neki hogy $G' = \frac{G+\frac{x}{G}}{2}$ közelít, szóval elkezdi - Megoldandó probléma: $ \sqrt{1366561} = ? $ - 1, 683281, 341641, 170822, 85415, 42715, 21373, 10718, 5423, 2837, 1659, 1241, 1171, 1169

Specifikáció

Egyfajta deklaratív leírása egy programnak Miből, mit? - állapottér - bemenő/kimenő adatok - előfeltétel - amit tudunk a bemenetről - utófeltétel - az eredmény kiszámítási szabálya (amit tudunk az eredményről) legyen **teljes** és **részletes**

Példa

Valós számok halmazán megoldható másodfokú egyneletet oldjon meg a program, ami $ax^2+bx+c=0$ formában van megadva - Á: $(a,b,c,x_1,x_2 \in \mathbb{R})$ <!-- .element: class="fragment" data-fragment-index="1" --> - Ef: $(a \neq 0 \land b^2-4ac \geq 0)$ <!-- .element: class="fragment" data-fragment-index="2" --> - Uf: $ (x_1 = \frac{-b + \sqrt{b^2-4ac}}{2a} \land x_2 = \frac{-b - \sqrt{b^2-4ac}}{2a})$ <!-- .element: class="fragment" data-fragment-index="3" -->

Valós számok halmazán megoldható másodfokú egyneletet oldjon meg a program, ami $ax^2+bx+c=0$ formában van megadva - Á: $(a,b,c,x_1,x_2 \in \mathbb{R})$ - Ef: $(a \neq 0 \land b^2-4ac \geq 0)$ - Uf: $ (\forall i (ax_i^2+bx_i+c=0) \land ( x_1 = x_2 \iff b^2-4ac = 0 ))$

Teljesség

Amit az előfeltétel megenged az állapottéren belül, azt az utófeltételnek kezelnie kell Pl: - Válassza ki két szám közül azt amelyiknek több prím osztója van - több különböző vagy több összesen? - mi van ha ugyanannyi? - Válassza ki egy számsorból azt az 5 számot ami legjobban eltér az átlagtól - mi van ha nincs 5 szám a számsorban? - mi van ha minden szám ugyanaz? - Sakktáblán szereplő állásról döntse el hogy matt-e. - mi van ha mindkét fél sakkban van? - lehet 11 királynő valakinél?

Részletesség

A program főzzön rántottát: - Á: (konyha) - Ef: ( ) - Uf: (ha a konyha alkalmas ennek elkészítésére, a konyhában legyen egy finom rántotta) vagy: - Á: (serpenyő, főzőlap, 3 tojás, olaj, só, fakanál, tányér) - Ef: (a serpenyő, tányér és fakanál tiszta, a tojás nem romlott, a főzőlap képes a serpenyőt 200 Celsius fokra felmelegíteni) - Uf: (a tojások összekeverve kerültek a 200 fokos serpenyőbe az olaj után, több mint 4 de kevesebb mint 10 percet töltöttek ott, ebből 20 másodpercnél többet nem álltak kavarás nélkül, végül megsózva kikerültek a tányérra)

Példa 2.

Két természetes szám legnagyobb közös osztójának megtalálása - Á: $(a,b,x \in \mathbb{N})$ <!-- .element: class="fragment" data-fragment-index="1" --> - Ef: $(a \neq 0 \land b \neq 0)$ <!-- .element: class="fragment" data-fragment-index="2" --> - Uf: $ (x|a \land x|b \land \nexists i(i|a \land i|b \land i > x))$ <!-- .element: class="fragment" data-fragment-index="3" -->