Návrat na detail prednášky / Stiahnuť prednášku / Technická Univerzita Košice / Fakulta Elektrotechniky a Informatiky / Počítače a algoritmizácia

prednáška 1 (1_pr.doc)

1.2 Hardwarská architektúra

● počítače s HA majú oddelený adresový priestor pre program a pre údaje

►situácia, aby program prepísal sám seba nemôže nastať.

● táto architektúra sa v súčastnosti využíva pri niektorých jednočipových mikropočítačoch.(jednočipový mikropočítač → všetky štruktúrne prvky – procesor + pamäť + I/O obvody → sú integrované na jedinom polovodičovom čipe)

● Procesor používa na adresáciu obidvoch pamätí a na prenos údajov a inštrukcií spoločné adresové a údajové vodiče.

Rozlíšenie medzi prístupom k pamäti programu a k pamäti údajov → aktiváciou odlišných riadiacich signálov.

1.3Počítače riadené tokom údajov (data-flow systémy)

●tieto počítače nevykonávajú inštrukcie postupne za sebou, tak ako sú uložené v pamäti, vykoná sa tá inštrukcia, kt. má pripr. údaje

● ak má viac inštrukcií pripravené údaje vykonávajú sa paralelne ► ide o paralelné viacprocesorové počítače.

2Postup riešenia úlohy na počítači

Hlavné etapy postupu riešenia

1.Formulácia úlohy a definícia problému

2.Analýza úlohy a návrh riešenia

3.Nájdenie algoritmu výpočtu a zostavenie algoritmu.

4.Overenie správnosti algoritmu

5.Kódovanie programu a preklad

6.Overenie správnosti programu a ladenie programu

Pozn. Etapy 1÷4 → cvičenia dodržia daný postup

→ príkl. na samostatné riešenie

→ príkl. na zadania počas semestra

→ príkl. na skúšku pís. časť

1.Formulácia úlohy a definícia problému

→ definovať, čo máme riešiť → podľa zložitosti problému môže byť definícia problému, slovná alebo s využitím formálneho aparátu.

→ formulácia úlohy, kt. chceme riešiť na počítači → je jej úprava na taký tvaj, kt. je pre ten PC vhodný.

Formulácia má spĺňať nasledujúce podmienky:

1. diskrétnosť údajov a operácii (+,-,*,/)
2. konečnosť údajov a operácii (počet operácii je konečný)
3. obmedzenia dané PC

2.Analýza úlohy a návrh riešenia

→ vykonať dôkladný rozbor úlohy (problému)

→ špecifikovať vstupy (štruktúra, formát, množina prípustných hodnôt)

→ špecifikovať výstupy (štruktúra, formát, funkčná závislosť na vstupných hodnotách)

→ návrh riešenia obsahuje výber metódy, dekompozícia úlohy na čiastkové problémy

3.Nájdenie algoritmu výpočtu a zostavenie algoritmu.

Realizácia úlohy na počítači predpokladá poznať presný postup výpočtu a algoritmus.

Algoritmus → je presný predpis definujúci výpočtový proces, kt. vedie ????? údajov až k správnym odpovediam

- skladá sa z jednotlivých výpočtových krokov, kt. sú zapísané v presne určenom poradí, ich počet musí byť konečný

Každý algoritmus má tri základné vlastnosti:

● hromadnosť – algoritm. definuje výpočet celej triedy úloh rovnakého typu, pričom sa nav. líšia vstupmi

● determinovanosť – t.j. algoritmus je presný a jednoznačný → vždy je určený nasledujúci krok jednoznačným spôsobom. Výpočet sa dá vždy opakovať → pre rovnaké vstupné údaje dostaneme vždy rovnaký výsledok.

● rezultatívnosť – udáva, že pre prípustné vstupné hodnoty získame výsledok po konečnom počte výpočtových krokov. Nájdenie algoritmu riešiaceho daný problém nazývame Algoritmizácia – pri nej sa vyžaduje schopnosť logického myslenia.

Pozn. Pojem algoritmus pochádza od arabského matematika M. M. Abdallah al Charezzmiho (8/9 st. n. l) → Uzbekistan „Traktát o výpočtoch v decimálnej pozičnej sústave“.

Vstup pojmu algoritmus do novodobej kriminológii zaznamenala monografia ruského matematika MARKOVA.

Teória algoritmov

Neformálne vymedzenie pojmu algoritmus:

→ 1. máš problém, kt. chceme riešiť

● presne definovaný

● v priebehu riešenia nemenný

● rozpoznateľné riešenie

→ 2. mať nástroj na riešenie problému

● hmotný – počítač

● nehmotný – matematický aparát

Prikl.

1. Navrhnite algoritmus pre výpočet aritmetického priemeru z daných troch čísel a overte jeho správnosť.
2. Vstupné premenné: A1- prvé číslo

        A2- druhé číslo

        A3- tretie číslo

Vstupné premenné: PR- aritmetický priemer (Výsledok)

Pomocná premenná: C

3. zostavenie algoritmu [Slovný popis algoritmu]

K1. načítanie prvého čísla → (čítaj A1)

K2. odpamätaj prvé číslo do premennej C → (C←A1)

K3. načítanie druhého čísla → (čítaj A2)

K4. vykonaj súčet prvého a druhého čísla a ulož do premennej C → (C←A2)

K5. načítanie tretieho čísla → (čítaj A3)

K6. pričítanie tretieho čísla k výsledku (súčtu prvých dvoch čísel) a odpamätajúc do C → (C←C+A3)

K7. Výpočet aritmetického priemeru  → (pr←C/3)

K8. koniec

4. overenie správnosti algoritmu

-spočíva v otestovaní algoritmu na vhodnej množine vstupných údajov (A1=1, A2=-4, A3=0)

Vhodným prostriedkom pre testovanie je simulačná tabuľka (viď cvičenia)

K1. čítaj A1        A1=1        

K2. C←A1        C=1

K3. čítaj A2        A2=-4

K4. C←C+A2        C=1-4= -3

K5. čítaj A3        A3=0

K6. C←C+A3        C=-3+0

K7. PR←C/3        PR=-3/3=-1

K8. Koniec

5. Kódovanie programu a preklad → predstavuje prepis algoritmu do programovacieho jazyka (C jazyk).

→ Program v príslušnom jazyku nazývame zdrojový program; kt. tvorí vstup pre prekladač (kompilátor)

→ kompilátor – súbor programov pre počítač, kt. prijíma ako vstupné dáta program v problemovoorientovanom jazyku a ako výstup vytvára počítačovo orientovaný kód.

(lexikálna analýza, syntaktická analýza) odstránenie formálnych chýb

Algoritmus versus program

● program = postupnosť príkazov ► výpis programu

● algoritmus = postup práce výpis zápis algoritmu ► dá sa patentovať

Program realizuje algoritmus (Algoritmy), algoritmus je jeho nutnou súčasťou

6. Overenie správnosti programu a algoritmu

→ spočíva v testovaní programu na vhodnej množine vstupných údajov, pre kt. poznáme výsledky.

Ladenie programu – odstránenie logických chýb → ladiace prostriedky (debugov) → umožňujú sledovať priebeh výpočtu s medzivýsledkami.

6

5

Začiatok

Definícia probl.

Návrh riešenia

Zostavenie algoritmu

Testovanie algoritmu

Alg. vyhovuje

Kódovanie programu

Ladenie programu

Výskyt log. chyby

Prac. program

-

+

3

4

2

1

+

-