Základní pojmy. Úvod do programování. Základní pojmy. Zápis algoritmu. Výraz. Základní pojmy

2. pˇrednáška

Základní pojmy ˇ Rídící struktury Datové typy Lineární datové struktury

2. pˇrednáška


Základní pojmy Procesor Procesorem je objekt, který vykonává algoritmem popisovanou ˇ cˇ innost (muže ˚ jím být stroj (poˇcítaˇc) nebo cˇ lovek). Formulace algoritmu souvisí s tím, pro jaký typ procesoru se bude vytváˇret.

Úvod do programování

Etapy rˇešení problému

Michal Krátký1 , Jiˇrí Dvorský1

specifikace (definice) problému – vstupy a požadavky na výstupy,

1 Katedra

informatiky VŠB–Technická univerzita Ostrava

analýza problému – volba vhodné metody ˇrešení, sestavení algoritmu – posloupnost na sebe navazujících kroku˚ (ˇrídící struktury),

Úvod do programování, 2004/2005

kódování – zápis algoritmu v jazyce procesoru, ˇ rení správnosti navrženého algoritmu. testování – oveˇ c 2005

Michal Krátký, Jiˇrí Dvorský

2. pˇrednáška


c 2005

1/34



2. pˇrednáška

Zápis algoritmu


2/34


Základní pojmy Datový typ Urˇcuje jakých hodnot muže ˚ nabývat objekt daného datového typu a množinu pˇrípustných operací nad tímto datovým typem. ˇ Datovým objektem rozumíme konstantu, promennou, výraz a funkci.

pˇrirozený jazyk (slovní popis), ˇ (napˇr. vývojový diagram), grafické znázornení

Identifikátory Identifikátory jsou jména, která dáváme napˇr. konstantám, ˇ promenným, funkcím. Tato jména mohou být tvoˇrena písmeny anglické abecedy, cˇ íslicemi a znakem podtržítko.

speciální jazyk (pseudojazyk), programovací jazyk.

Pˇríklad: int cislo; float fcislo; Point bod; bod.SetCoordinate(0, 0.5); c 2005


2. pˇrednáška




4/34


Výraz

Konstanta ˇ hodnotu behem ˇ ˇrešení problému. Použití: Nemení pˇrímé – 63, 10−2 , ’ABC’, pojmenování – oznaˇcení identifikátorem. Pˇríklad: final double pi = 3.14; // Java const double pi = 3.14; // C++ pi = 4.8; // error

Výraz je tvoˇren operátory, operandy a speciálními znaky. Operandem muže ˚ být: konstanta, ˇ promenná, výraz, volání funkce, operátor a pˇríslušné operandy, popˇrípadeˇ závorky. Pˇríklad:

ˇ Promenná ˇ hodnotu behem ˇ ˇrešení problému. Veliˇcina, která muže ˚ menit ˇ Promenná se zavádí definicí. Pˇríklad: int cislo = 2; cislo += 3; Michal Krátký, Jiˇrí Dvorský


2. pˇrednáška

Základní pojmy

c 2005

c 2005

3/34


12 b (a+b)/2

5/34

c 2005

"abc" sin(0.5) a>=c

a 12+9*3 ((a + b) * (c / d)) / 3



6/34

2. pˇrednáška


2. pˇrednáška

ˇ Rídící struktury

Strukturované ˇrídící struktury - sekvence, posloupnost

Posloupnost je tvoˇrena posloupností jednoho nebo více ˇ v pevneˇ daném poˇradí. Pˇríkaz se pˇríkazu, ˚ které se provádejí ˇ až po ukonˇcení pˇredchozího pˇríkazu. zaˇcne provádet

Pˇríkazy (ˇrídící struktury) popisují jednotlivé kroky algoritmu a jejich návaznosti. Rozlišujeme jednoduché a strukturované pˇríkazy. Celý algoritmus lze chápat jako jeden pˇríkaz. (Pozn. ˇ pro zápis algoritmu v nekterém programovacím jazyce zpravidla platí, že z výrazu se stane pˇríkaz teprve tehdy, až za ˇ vložíme stˇredník.) nej

Pˇríklad: int cislo = 1; cislo += 1; System.out.println(cislo); // Java printf("%d\n", cislo); // C/C++

Jednoduché pˇríkazy Mezi jednoduché pˇríkazy patˇrí prázdný pˇríkaz a volání funkce.

c 2005


2. pˇrednáška


7/34

bool flag = true; int cislo = 10; if (!flag) { cislo = 100; }


2. pˇrednáška


8/34


Strukturované ˇrídící struktury - Switch

int cislo = 2; if (cislo == 1) { pˇ ríkaz1 } else { pˇ ríkaz2 }



2. pˇrednáška

ˇ podmínky, tedy Provedení dalšího pˇríkazu závisí na splnení ˇ pˇríkaz urˇcí, který z pˇríkazu˚ bude vykonán v podmínený ˇ cˇ i nesplnení ˇ podmínky. závislosti na splnení

c 2005

c 2005


ˇ Strukturované ˇrídící struktury - Vetvení

if (výraz) { pˇ ríkaz1 } else { pˇ ríkaz2 }


9/34

switch (integral-selector) { case integral-value1: statement; break; case integral-value2: statement; break; ... default: statement; }

c 2005



2. pˇrednáška

Strukturované ˇrídící struktury - Cyklus

int b = 1; switch (b) { case 1: statement; break; default: statement; }


10/34


Strukturované ˇrídící struktury - Cyklus Druhy cyklu˚ ˇ cyklu cyklus s podmínkou pˇred vykonáním tela while(výraz) { pˇ ríkaz } ˇ cyklu se tedy nemusí vykonat ani jednou. Telo ˇ cyklus s podmínkou za telem cyklu do { pˇ ríkaz } while(výraz) ˇ cyklu se provede minimálneˇ jednou. Telo

ˇ Cyklus je cˇ ást algoritmu, která je opakovaneˇ provádena za ˇ rˇídící podmínky. Opakující se pˇríkaz (pˇríkazy) splnení ˇ cyklu. nazýváme telo Rozlišujeme dva typy cyklu: ˚ indukˇcní - ˇrídící podmínka cyklu urˇcuje, zda bude ˇ cyklu, nebo provedena posloupnost pˇríkazu, ˚ která tvoˇrí telo ˇ cyklu, dojde k pˇredání ˇrízení za telo ˇ cyklu závisí na hodnoteˇ iteraˇcní - poˇcet opakování tela ˇrídící promenné. ˇ

c 2005



11/34

c 2005



12/34

2. pˇrednáška


2. pˇrednáška

Strukturované ˇrídící struktury - Cyklus cyklus s pevným poˇctem opakování for (výraz1; výraz2; výraz3) { pˇ ríkaz }

Algebraické struktury 1/2

Abstrakce datových typu˚ – množina a operace. for ( ; ; ) { pˇ ríkaz }

Grupoid (G, ◦) G = G, ◦G je grupoid, pokud množina H ⊆ G je uzavˇrená (vzhledem k operaci ◦G ):

for (int i=0,c=3 ; i < 10 ; i++) { System.out.println(i+" "+c); }

c 2005


2. pˇrednáška

∀a, b ∈ H : ◦G b ∈ H Pˇríklad: ({1, 2, 3}, +)


13/34


Deklarací urˇcujeme typ objektu. Informace o typu je pˇrekladaˇcem používána pˇri typové kontrole, typových konverzích, atd. V místeˇ definice definujeme hodnotu ˇ promenné cˇ i posloupnost pˇríkazu˚ funkce.

inverzní prvek : ∀g ∈ G ∃g −1 ∈ G tak, že g −1 ◦ g = n grupa komutativita: ∀a, b ∈ G : a ◦ b = b ◦ a komutativní grupa

Pˇríklad: int cislo; cislo = 5; int value = cislo + 10;

Pˇríklad: (Z, +), (Q, +), (R, +) a (C, +) – komutativní grupy. (Z, ·) není grupa. Úvod do programování

15/34

c 2005



2. pˇrednáška

Jednoduché datové typy


16/34


Strukturované datové typy Pole – posloupnost prvku˚ stejného DT. int []array = new int[100]; ˇ Struktura – je tvoˇrena nekolika položkami. typedef struct // C++ { double x; double y; } Point2D; Uživatelem definované datové typy – napˇr. tˇrídy v OO programovacích jazycích. ˇ obsahující hodnotu Ukazatel (pointer) – adresa v pameti ˇ nejakého datového typu. Point point = new Point(); // Java Point point; Point* ppoint = &point; // C++

Logický typ (Boolean) – hodnoty: true, false. Operace: negace, konjunkce, disjunkce. boolean flag = true; ˇ Císelné datové typy – celé cˇ íslo, reálné cˇ íslo (rozsah, pˇresnost). Operace: +,-,/,. . . . short value = 32; double realv = 0.5; Znak – každému znaku je pˇriˇrazena celoˇcíselná hodnota, tzv. kód znaku (ASCII, Unicode, . . . ). char ch = ’A’; Pˇríklad: System.out.println("cislo: Michal Krátký, Jiˇrí Dvorský

14/34

Datový typ (DT) urˇcuje množinu hodnot, kterých muže ˚ nabýt ˇ konstanta, promenná, funkce nebo výraz a množinu operací ˇ nad temito hodnotami.

neutrální prvek : ∃n ∈ G tak, že ∀a ∈ G : n ◦ a = a monoid

c 2005


Datové typy

asociativita: ∀a, b, c ∈ G : a ◦ (b ◦ c) = (a ◦ b) ◦ c pologrupa

2. pˇrednáška


2. pˇrednáška

Klasifikace:


c 2005


Algebraické struktury 2/2

c 2005


" + value);


17/34

c 2005



18/34

2. pˇrednáška


2. pˇrednáška

Množiny

Uspoˇrádané množiny

Množina – skupina objektu. ˚ Množinu budeme považovat za urˇcenou, je-li možno o každém objektu rozhodnout, zda do množiny patˇrí cˇ i nikoliv, tj. zda je cˇ i není jejím prvkem, x ∈ M. Operace s množinami: ∪, ∩, . . ..

Množina M se nazývá uspoˇrádaná množina, jestliže je na ní definována binární relace ≤: ∀x : x ≤ x ∀x, y : je-li x ≤ y a y ≤ x potom x = y

n-ární Relace Libovolná podmnožina kartézského souˇcinu množin A1 , A2 , . . . , An .

∀x, y , z : x ≤ y a y ≤ z potom x ≤ z Jestliže pro každé x, y ∈ A platí x ≤ y nebo y ≤ x potom uspoˇrádání ≤ nazýváme lineární uspoˇrádání.

R ⊆ A1 × A2 × . . . × An Binární relace: R ⊆ A × A, R ⊆ An

Pˇríklad: A = {1, 2, 3}, ≤= {1, 1 1, 2 , 1, 3 , 2, 2 . . .}

Pˇríklad: A = {a, b}, A × A = {a, a a, b , b, a , b, b } c 2005



2. pˇrednáška


19/34

c 2005



2. pˇrednáška

Datové struktury


20/34


Lineární datové struktury

Datová struktura - implementace množiny, cˇ asto dynamická. lineární (pole, zásobník, ...), nelineární (stromy).

Pole Zásobník

Algoritmy pracují s množinami pomocí ruzných ˚ operací.

Fronta

Aplikace

Seznam

Vyhledávací algoritmy. ˇ Relaˇcní model SRBD. Vyhledávání multimediálních dat (texty, obrázky, . . . ).

c 2005


2. pˇrednáška


21/34

c 2005



2. pˇrednáška


22/34


ˇ Pole – vyhledávání v nesetˇrídeném poli 1/3

Pole

Sekvenˇcní pruchod. ˚ O(n). public class Array { int mData[];

Pole (array) patˇrí k nejjednodušším datovým strukturám. Pˇrístup k prvkum ˚ pole je urˇcen udáním hodnoty indexu a není závislý na pˇrístupu k jinému prvku. Proto ˇríkáme, že pole je strukturou s pˇrímým nebo náhodným pˇrístupem. Pole statické/dynamické.

c 2005



public Array(int size) { mData = new int[size]; for (int i = 0 ; i < mData.length ; i++) { mData[i] = (int)(Math.random() * size); } } 23/34

c 2005



24/34

2. pˇrednáška


2. pˇrednáška

ˇ Pole – vyhledávání v nesetˇrídeném poli 2/3

ˇ Pole – vyhledávání v nesetˇrídeném poli 3/3 public static void main(String[] args) { Array pole = new Array(100); int order = pole.Find(25); System.out.println(order); }

public int Find(int value) { for (int i = 0 ; i < mData.length ; i++) { if (mData[i] == value) { return i; } } return -1; }

} Algoritmus potˇrebuje v nejhorším pˇrípadeˇ n porovnání. ˇ Prum ˚ erný poˇcet porovnání za pˇredpokladu, že ˇ pravdepodobnost výskytu libovolného prvku množiny je stejná. Cavg = (1 + 2 + · · · + n)

c 2005


2. pˇrednáška


25/34

c 2005



2. pˇrednáška

Pole – problémy

1 1 1 (1 + n) = (1 + n)n = n 2 n 2 Úvod do programování

26/34


Zásobník (Stack)

ˇ princip last-in, first out (LIFO). Tj. U zásobníku je uplatnen prvek, který byl vložen poslední, je jako první ze zásobníku vyzvednut. Ukazatel na aktuální prvek v zásobníku (posledneˇ vložený) se nazývá vrchol zásobníku (stack pointer ). Opakem je dno zásobníku.

Dynamické pole. ˇ Vyhledávání v setˇrídeném poli - složitost O(log n). Perzistentní pole.

c 2005



2. pˇrednáška


27/34

c 2005



2. pˇrednáška

Zásobník – operace


28/34


Zásobník – operace

Push – vložení prvku na vrchol zásobníku. Pop – vyjmutí prvku z vrcholu zásobníku. Empty – test prázdnosti zásobníku. Top – vrátí prvek z vrcholu zásobníku bez jeho vyjmutí. Pokud provedeme operaci Pop na prázdném zásobníku nastává tzv. podteˇcení (underflow). Pokud není možné pˇridat další prvek, nastává tzv. pˇreteˇcení (overflow). Operace mají konstantní cˇ asovou složitost.

c 2005



a) Push(15); Push(6); Push(2); Push(9); b) Push(17); Push(3); c) Pop(); 29/34

c 2005



30/34

2. pˇrednáška


2. pˇrednáška

Zásobník – implementace pomocí pole 1/3


public class Stack { int mData[]; int mStackPointer; public Stack(int capacity) { mData = new int[capacity]; mStackPointer = -1; }

c 2005


2. pˇrednáška


31/34

c 2005



2. pˇrednáška


32/34


Zásobník

Stack stack = new Stack(10); for (int i = 0 ; i < 12 ; i++) { System.out.print(stack.Push(i) + ", "); } System.out.println(); for (int i = 0 ; i < 12 ; i++) { System.out.print(stack.Pop() + ", "); } System.out.println(); Výstup: true, true, true, true, true, true, true, true, true, true, false, false, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, -1, -1, Michal Krátký, Jiˇrí Dvorský

public boolean Push(int value) { boolean ret = false; if (mStackPointer < mData.length-1) { mData[++mStackPointer] = value; ret = true; } return ret; } public int Pop() { if (mStackPointer >= 0) { return mData[mStackPointer--]; } return -1; }



c 2005


Problémy Implementace pomocí seznamu a fronty. Dynamický zásobník. Perzistentní zásobník. Aplikace Pˇrekladaˇce (závorkované výrazy, zásobníkové automaty). Uložení parametru˚ volaných funkcí.

33/34

c 2005



34/34

Základní pojmy. Úvod do programování. Základní pojmy. Zápis algoritmu. Výraz. Základní pojmy

Recommend Documents