Predmet:     Algoritmizácia a programovanie 2202  FEI

Odbor:           všetky 

Ročník:            1.ročník

Rozsah:            3/2 ZS

 

Prednášajúci: Jiří Pospíchal

 

Informácie o skúške sú dole na stránke

 

Anotácia Predmetu:

 

Úvod do algoritmizácie . Základne vlastnosti algoritmov. Vybrané algoritmy usporiadania a vyhľadávania. Úvod do programovacích paradigiem. Cieľom predmetu je zvládnutie tvorby jednoduchých algoritmov a tvorba jednoduchých programov v jazyku C. Zoznámiť sa s základnými údajovými typmi a štruktúrami, naučiť sa ich používať. Naučiť sa používať vybrané algoritmy usporiadania a vyhľadávania. Získať prehľad o súčasných programovacích paradigmách.

 

 

Kľúčové slová:

   Program, algoritmus, usporiadanie, vyhľadanie, rekurzia, rekurzívne algoritmy, programovacie jazyky.

 

Osnova prednášok:

 

1.                  Úvod do softvérového inžinierstva, úvod do  algoritmizácie , algoritmus, programovanie, program.

      Životný cyklus programu.

      Algoritmus – charakteristiky a vlastnosti,  hromadnosť, konečnosť, jednoznačnosť,

      algoritmus a program, spôsoby  (formy) zápisu algoritmu    (pomocou grafických alebo

      iných prostriedkov). Základy zložitosti algoritmov.

 

prednáška (PDF, DOC) – históriu môžte zvačša pre účely písomky ignorovať, ale algoritmy

a ich zápis a zásady dokumentácie nie!

Pre zaujímavosť, texty k histórii počítania môžte náisť na adresách doc a pdf

a k histórii algoritmov na doc a pdf

 

2.                  Klasifikácia algoritmov. Vybrané lineárne algoritmy násobenia (a la russe, rozdeluj a panuj, násobenie sčítaním....). Zložitosť algoritmov.

      Úvod do programovacieho jazyka C.

      Ukážkový príklad v programovacom jazyku C.  Vysvetlenie jednotlivých konštrukcii jazyka.

prednáška (PDF, DOC)

 

Spustenie Borland C++ 3.1 v učebni Dl03

Alebo Ako na Borland C pri počítači v učebni Dl03

 

3.                  Programovací jazyk C: Tvorba ďalších  algoritmov ( delenie, umocnenie...).

            Cykly, polia.

prednáška (PDF, DOC)

 

4.                  Typová konverzia. Preprocesor. Budovanie ďalších algoritmov (NSD, Fibonacci a rekurzia).
Tvorba a používanie podprogramov. Odovzdávanie parametrov. Funkcie v jazyku C.

prednáška (PDF, DOC)

 

5.                  Algoritmy s reálnou aritmetikou (výpočet radu, iteračné metódy riešenia rovníc..)

Algoritmy na hľadanie prvočísel. Inicializácia polí, vstup a výstup zo súboru.

prednáška (PDF, DOC)

 

 

6.                  Údajové konštrukcie: reťazce. Princípy usporiadania, vybrané algoritmy usporiadania. 
Porovnanie jednotlivých metód.

       Implementácia v jazyku C.

prednáška (PDF, DOC)

 

Vizualizácia algoritmov usporiadania (Bc. práca Z. Halanovej, vedúca projektu RNDr. A.B. Ezzeddine)

Vizualizácia algoritmov usporiadania (Bc. práca T. Molnára, vedúca projektu RNDr. A.B. Ezzeddine)

  

7.                  Práca s dynamickým prideľovaním pamäti (smerníky, referencie v jazyku C).

            Polia ako parametre podprogramov.
prednáška (PDF, DOC)

 

8.                       Štrukturované typy, špecifikácia štrukturovaného typu, implementácia, deklarácia, polia.
      Údajové konštrukcie:

-                     abstraktné dátové typy, špecifikácia

-                     lineárny zoznam, zásobník, rad, množina, strom,  tabuľka.

prednáška (PDF, DOC)

 

9.                  Vybrané algoritmy vyhľadávania: sekvenčné, v nezoradenom a  zoradenom poli,

      binárne vyhľadávanie,  binárny vyhľadávací strom, vyvážený strom, prehľadávanie do šírky a do hĺbky

prednáška (PDF, DOC)

 

Vizualizácia algoritmov vyhľadávania (Bc. práca M. Šoltisa, vedúca projektu RNDr. A.B. Ezzeddine)

     

10.              Heuristické a nedeterministické algoritmy.
      Rekurzia, rekurzívne algoritmy. Prepis do nerekurzívnych algoritmov.

prednáška (PDF, DOC)

 

11.              Programovacie paradigmy - základné princípy:

       procedurálne programovanie, funkcionálne , logické programovanie, objektovo  

       orientované programovanie. Heuristické optimalizačné metódy - evolučné algoritmy

prednáška časť A (PDF, DOC) časť B (PDF, DOC)

 

12.              Umelý život, prednáška časť A (PDF, DOC)

            Chaos, celulárne automaty, fraktály časť B (PDF, DOC)

 

LITERATÚRA:

 

1. Wirth, N.: Algoritmy a štruktúry údajov. Bratislava, Alfa 1990.

2. Brassard, G., Bratley, P.: Fundamentals of Algorithmics. Pretince-Hall, Inc. 1996.

3. Herout P.: Učebnice jazyka C . KOPP, České Budejovice, 1994

      4. http://www.manualy.sk/saloun/obsah.htm      

      5. http://www.tuke.sk/podlubny/C/     

 

Bratislava     zima 2004-2005

 

 

Klasifikačná stupnica

Študent získa kredity za predmet iba vtedy, ak jeho výsledky boli ohodnotené niekto­rým z klasifikačných stupňov od A až po E.

 

Známka

 

 

(klasifikačný stupeň, ktorý sa zapisuje do indexu

a do skúšobného hárku)

 

Číselná hodnota známky

 

(využíva sa pri výpočte váženého študijného priemeru)

 

Definícia stupňa hodnotenia

 

 

 

 

 

Interval  bodov

 

potrebných na získanie

príslušnej

známky

A

 

1,0

výborne - vynikajúce výsledky len s minimálnymi chybami

 

<96 –100>

 

B

 

1,5

veľmi dobre – nadpriemerné výsledky s menšími chybami

 

<85-96)

 

C

 

2,0

dobre – vcelku dobré, priemerné výsledky

 

<72-85)

 

D

 

2,5

uspokojivo – dobré výsledky, ale vyskytujú sa významné chyby

 

<61-72)

 

E

 

3,0

dostatočne – výsledky vyhovujú minimálnym kritériam

 

<56-61)

 

FX*

 

 

4,0

nedostatočne – absolvovanie predmetu si vyžaduje vynaložiť ešte značné úsilie a množstvo práce zo strany študenta

 

 

<0-56)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Poznámka: Známka „FX“ sa zapisuje iba do skušobného hárku (elektronická forma) ale nie do indexu.

 

Klasifikačná stupnica pre študentov 1. ročníka bakalárskeho štúdia na FEI .

 

Skúška sa bude konať

11.1.2005 od 13.30 do 15.00 hod.

(opravný termín 31.1. od 13.30 do 15.00 hod.)

v miestnostiach AB300, BC300, DE300, BC150, DE150.

Každý študent pôjde na skúšku iba do miestnosti,

pri ktorej bude uvedený na zozname pri dverách.

 

Skúška je písomná, je potrebné si doniesť pero a 

preukaz totožnosti.

Preukaz totožnosti pri písomke študent položí

pred seba a dozorujúci pedagóg študenta nechá

podpísať na zoznam vedľa študentovho mena.

 

Do pravého horného rohu písomky majú študenti napísať

tlačeným písmom meno, priezvisko, svoje študentské číslo.

 

Nečitateľné texty nemusia byť uznané.

Študent, ktorý vzdá písomku, musí odovzdať aspoň

(polo)prázdny papier so svojím menom a číslom.

 

Ak je študent vyhodený zo skúšky pre neregulárne správanie,

písomka sa mu odoberie a dozorujúci pedagóg na ňu zreteľne

napíše, o aký incident išlo, a podpíše sa.

Ak študent odovzdá viac papierov, na každom musí byť

jeho meno a číslo, na prvý papier dozor napíše počet

odovzdaných listov.

 

Na tejto stránke budú oznámené neskôr bodové výsledky

a správne znenie riešenia písomky, a kedy a kde bude

možné si pozrieť opravené písomky a zapísať si známku.

Zápis do indexov a pozeranie opravených písomiek je nepovinné,

študent tiež môže poslať index po kolegovi na zápis.

 

Opravný termín sa bude konať

31.1. od 13.30 do 15.00 hod.

v miestnosti CD300

 

 

Výsledky 1. skúšky

odstránené z príkazu dekana kvôli ochrane osobných údajov

 

Zápis do indexov a pozeranie opravených písomiek je nepovinné,

študent tiež môže poslať index po kolegovi na zápis.

Pozrieť sa na opravnú písomku a zapísať si skúšku

si môžete prísť vo stredu 2.2.2005

10.30-11.30 do miestnosti D109.

 

Riešenie písomky

 

Písomka z predmetu Algoritmizácia a programovanie

odbor telekomunikácie, 1.r. FEI STU, zo dňa 11.1.2005

(každý príklad maximálne za 12 bodov)

 

1. Prepíšte dole uvedený výraz na príkaz typu do – while

for(n=1, k=0; n<END || k>MAX; k+=n*n, n++);

 

n=1;

k=0;

do {

    if(n<END || k>MAX) break;

    k+=n*n;

    n++;

while(1)

 

alebo iba s while

 

n=1;

k=0;

while (n<END || k>MAX)

{

  k+=n*n;

  n++;

}

 

2. Napíšte funkciu int suma(int *pole, int pocet);

ktorá spočíta prvky celočíselného poľa metódou rekurzie

(pokiaľ neviete pomocou rekurzie, môžete napísať aj normálnu funkciu, ale maximálne za polovičný počet bodov).

int suma(int *pole, int pocet)

{

  if(pocet<=0) return 0;

  else return (*pole + suma(pole+1, pocet-1));

}

 

3. Napíšte všetky stavy v poli desiatich čísel 1,9,8,3,7,2,9,5,6,7

pri jednoduchom triedení (usporiadaní, simple sort)

 

 1  8  9  3  7  2  9  5  6  7

 1  3  9  8  7  2  9  5  6  7

 1  2  9  8  7  3  9  5  6  7

 1  2  8  9  7  3  9  5  6  7

 1  2  7  9  8  3  9  5  6  7

 1  2  3  9  8  7  9  5  6  7

 1  2  3  8  9  7  9  5  6  7

 1  2  3  7  9  8  9  5  6  7

 1  2  3  5  9  8  9  7  6  7

 1  2  3  5  8  9  9  7  6  7

 1  2  3  5  7  9  9  8  6  7

 1  2  3  5  6  9  9  8  7  7

 1  2  3  5  6  8  9  9  7  7

 1  2  3  5  6  7  9  9  8  7

 1  2  3  5  6  7  8  9  9  7

 1  2  3  5  6  7  7  9  9  8

 1  2  3  5  6  7  7  8  9  9

 

 

4. Napíšte funkciu, ktorej vstupom je pointer na reťazec znakov (s dopredu neznámou dĺžkou) a ktorá vypíše na obrazovku tento reťazec znakov v opačnom poradí znakov.

 

void vypis(char* retazec)

{

 int i, dlzka;

 dlzka=strlen(retazec);

 for(i= dlzka-1;i>=0;i--)

  printf("%c",retazec[i])

}

alebo

void vypis(char* retazec)

{

 char *pomocny=retazec;

 while(*pomocny++!='\0');

 pomocny--;

 while(--pomocny!=retazec-1)

  printf("%c",*pomocny);

}

 

5. Napíšte program, ktorý jeho používateľovi umožní postupne sčítavať N celých čísiel zadaných klávesnicou a kontroluje, aby čísla boli iba z rastúcej postupnosti čísel.

 

#include <stdio.h>

 

void main(void)

{

 int N, a, b, i;

 scanf("%d",&N)

 if(N<=0) return;

 scanf("%d",&a)

 for(i=2;i<=N;i++)

 {

  scanf("%d",&b);

  if(a>=b) { printf(„Ne je rastuca postupnost“); return; }

  else a=b;

 }

}