Obsah 10. přednášky: Jak bude probíhat zkouška?! Podrobné informace:

Obsah 10. přednášky: Kódování dat - terminologie Rozdělení kódů Kódování čísel Kódování znaků Dynamické programování* Příklad řešení úlohy ACM* Úloha pro zájemce* – efektivita algoritmu

Tato tematika je zpracována v Záznamy přednášek: str. 221 – 235 + materiál: PrikladyZobrazeniCisel.pdf – viz portál

Jak bude probíhat zkouška?! Podrobné informace: Portál (1.termín) příští přednáška

Přednášky KIV/PPA1, A. Netrvalová, 2016

10. přednáška

Kódování dat - terminologie Data - informace, které jsou v průběhu výpočtu uloženy v paměti počítače nebo na vnějším mediu. Typy dat: čísla, texty, obrázky, zvuky atd.

Kódování - převod dat na posloupnost bytů (bitů) Kapacita kódu o n bitech - počet zobrazitelných hodnot Příklad: počet bytů

1

2

4

počet bitů

8

16

32

kapacita 256 65536 4294967296

Rozdělení kódů dle charakteru kódovaných dat – znakové – číselné – ostatní (formáty) ~ grafické, zvukové, ...

Znakové kódy - každý znak zvolené abecedy reprezentován nezáporným celým číslem. – ASCII: 7 bitový kód pro anglickou abecedu – Unicode: 16 bitový mezinárodní kód (Java) – Windows 1250: 8-bitový kód Microsoft (CZ) – ISO/IEC 8859-2: 8-bitový standardizovaný kód (CZ) používaný v OS Linux Strana 2 (celkem 25)

Číselné kódy – celočíselné ◦ bez znaménka ◦ znaménkové  přímý  inverzní  doplňkový  s posunutou nulou – reálné ◦ jednoduchá přesnost ◦ dvojnásobná přesnost

Kódování čísel Poznámka - výklad celočíselných kódů na 8 bitech

Celočíselné kódy Kód bez znaménka (nezáporná čísla) binární zápis čísla (užití: zobrazení logické hodnoty) Př.: 0001 0111 = 23

Znaménkové kódy Přímý kód nezáporná čísla + znaménkový bit (Most Significant Bit) Nevýhoda: dvojí zobrazení nuly (kladná a záporná) Užití: zobrazení mantisy reálných čísel Př.: 1001 0111 = -23 1000 0000 = 0000 0000 = 0 Strana 3 (celkem 25)

Inverzní kód (tzv. jedničkový doplněk) kladná čísla - binární zápis záporná čísla - binární zápis + změna 01 a 10 Nevýhoda: opět „dvojí“ nula Užití: bitové operace, při převodu na doplňkový kód Př.: 0001 0111 = 23 1110 1000 = -23 1111 1111 = 0000 0000 = 0

Doplňkový kód (tzv. dvojkový doplněk) kladná - binární zápis záporná - inverze binárního zápisu + 1 Výhody: ◦ zobrazení nuly: 0000 0000 ◦ odečítání: přičítáním záporného čísla Nevýhody: ◦ nesymetrický rozsah: -128 až 127 ◦ vznik tzv. přetečení: 127+1= -128 (častá chyba!!!) Užití – zobrazení znaménkových čísel Př.: 0001 0111 = 23 1110 1000 = -23 postup: 0001 01111110 1000 +11110 1001 Př.: jednodušší způsob převodu 0001 1110 = 30 1110 0010 = -30 Př.: 1111 1111(doplňkový kód) = 1111 1111 -1  1111 1110 + inverze  0000 0001 = -1(10) Ale: 0111 1111(doplňkový kód) = 127(10) Strana 4 (celkem 25)

Kód s posunutou nulou - základem je lineární posun nuly, nula je uprostřed rozsahu 2n-1-1 (ilustrace na n=8) 0000 0000: největší záporné číslo 0111 1111: 0 1111 1111: největší kladné číslo Nevýhoda: kladná čísla odlišná od binární reprezentace Použití: zobrazení exponentu reálných čísel Př.: převod: číslo +27-1 27-1+23 27-1-23 1001 0110 = 23 0110 1000 = -23 Př.: 1001 0111(kód s posunutou 0) = -27+1+1001 0111 -1000 0000 + 1001 1000 = 0001 1000 = 24(10)

Kódování reálných čísel - aproximace reálného čísla - tzv. zobrazení v pohyblivé řádové čárce - formát IEEE 754 - jednoduchá přesnost (4 byty) - dvojnásobná přesnost (8bytů)

4 byty: 1 bit znaménko (mant.), 8 bitů exponent, 23 bitů mantisa Strana 5 (celkem 25)

Znaménkový bit mantisy 0 – kladná, 1- záporná Mantisa – přímý kód (binární) - normalizace mantisy: 1 mantisa  základ - určuje přesnost (numerické chyby při výpočtech!) - první bit mantisy=1, ale nezobrazuje se (skrytý), reprezentuje jedničku před desetinnou čárkou Exponent – v kódu s posunutou nulou - určuje rozsah Formát - kompromis mezi přesností a rozsahem -45 - rozsah ~ | 10  1038| - přesnost 6 - 7 desetinných míst 00000000 00000000 00000000 00000000 reálná 0 Hodnota čísla x = (-1)znaménko  2exp-127  1,mantisa Příklad 1: Zobrazte v IEEE (na 4 bytech) číslo: -258,125

258(10) = 100000010(2) ( 256 +2 ) 0,125 · 2 = 0,25 0 0,125(10)= 0,001(2) 0,25 · 2 = 0,5 0 0,5 · 2 = 1,0 1 258,125(10)= 100000010,001(2) normovaný tvar: 1,00000010001*28 exp.: 27-1+8 =27+7=10000000 +111=10000111

Strana 6 (celkem 25)

-258,125(10) = 1100 0011 1000 0001 0001 0000 0000 0000 (2) =

C

3

8

1

1

0

0

0 (16)

Příklad 2: Zobrazte v IEEE (na 4 bytech) číslo: +0,5 0,5(10) = 0,1(2) 1,0 *2-1 27-1-1 = 0111 1110 = 0011 1111 0000 0000 0000 0000 0000 0000 (2) = 3 F 0 0 0 0 0 0 (16) Příklad 3: BF800000(16) = 1011 1111 10000 0 0 0 0 0(2) = 01111111 27-1+27-1= 0  1.0 = -1.0(10) Poznámka (viz dříve): Problematika přetečení - příliš malá čísla (<MIN) – zaokrouhlení na 0 - příliš velká čísla (>MAX) – zaokrouhlení na  Operace s reálnými čísly – nutná obezřetnost - sčítání řádově velmi odlišných čísel - násobení (exp se sčítají, mantisy násobí) - nepoužívat == (porovnání na rovnost)

Kódování logických hodnot pouze 2 hodnoty (true, false) - celočíselný kód bez znaménka Strana 7 (celkem 25)

Kódování znaků – pro zájemce velice podrobné informace v Záznamech přednášek (str. 221-235), zde jen přehled kódů

Úvodní poznámka - týká se všech datových typů Datový typ má více bytů a záleží na pořadí jejich ukládání do paměti - 2 možnosti: - big-endian (BE) - vyšší řády na nižší adrese - little-endian (LE) - vyšší řády na vyšší adrese Příklad: celé číslo: 01A2B3C4(16) (27440068(10)) ukládáme do paměti od adresy 1000 BE: 01 A2 B3 C4 LE: C4 B3 A2 01 Často oba systémy na témže PC, způsob uložení závisí na: - procesoru - OS - programovacím jazyku

Terminologie – nejednotná (dále terminologie z Unicode – Character Encoding Model)

Znaková sada – množina kódovaných znaků US ASCII, ISO8859-1,Unicode,…

Kódovací schéma (charset) Strana 8 (celkem 25)

US-ASCII -

sedmibitový charset nemůže zobrazit akcenty anglické dokumenty, zdrojové kódy programů

ISO-8859-2 8-bitový charset pro východní Evropu

Windows-1250 8-bitový charset Microsoft od předchozího se liší znaky: š, Š, ž, Ž, ť, Ť

IBM852 – MS-DOS Latin-2 8-bitový charset IBM používaný v MS DOS a konzolovém okénku Win

xMacCentralEurope – Macintosh Latin-2 8-bitový charset Macintosh

Unicode charsety: UTF-8, UTF-16, UTF-32 LE,BE – značka bytového pořadí UTF-8 (1992) – pro kódování znaků Unicode posloupností bytů - 1 byte pro znaky anglické abecedy (jako ASCII) - 2 byty pro akcentované znaky Výhoda - úsporné, Nevýhoda – znaky nestejné délky, nelze aplikovat přímý přístup

UTF-16 (1996) - rozšíření, znaky 2 byty, oproti předchozímu dvojnásobná velikost, použití - u iPhone pro SMS


UTF-32 (1999) - kód znaku 32 bitů (4 bajty) Výhoda - přímý přístup (indexovatelné) Nevýhoda - neefektivita při nakládání s pamětí, pořadí bytů je dané architekturou - možná nekompatibilita při zpracovaní textů v různých OS

Příklady kódování (znaky české abecedy A a š):


Dynamické programování* Příklad: Fibonacciho čísla – ještě jednou – využívá opakování problémů v průběhu rekurze – vede na mnohem rychlejší algoritmus. Algoritmus Fib(n) – klasická rekurze 1. Pokud n ≤ 1, vrátíme n. 2. Jinak vrátíme Fib(n - 1) + Fib(n - 2). Jaká je časová složitost? Sledujme strom rekurze:

Kořen - Fn, listy F0 a F1, uvnitř - výpočty Fk pro 2 ≤ k < n. Hodnota vnitřního vrcholu = součtu hodnot všech listů pod ním Fn ≈ 2n - exponenciální složitost

Ale: Fib(n) voláme pro 0→n => je-li O(2n), počítá se totéž vícekrát! (viz obrázek) Strana 11 (celkem 25)

Jak tomu zabránit? Fibonacciho čísla už spočtená → do tabulky. Při každém volání rekurze se podíváme nejprve do tabulky, je-li tam, jen ho vrátíme, jinak spočteme a uložíme do tabulky.

Algoritmus Fib2(n): 1. Je-li T[n] definováno, vrátíme T[n]. 2. Pokud n

1, pak T[n] ← n.

3. Jinak T[n] ← Fib2(n - 1) + Fib2(n - 2). 4. Vrátíme T[n]. Jak se změnila časová složitost? K rekurzi nyní dojde jedině tehdy, vyplňujeme-li políčko tabulky, v němž dosud nic nebylo. To se může stát nejvýše (n + 1)-krát, z toho dvakrát triviálně (pro F0 a F1), takže strom rekurze má nejvýše n vnitřních vrcholů. Pod každým vrcholem leží nejvýše 2 listy, takže celkově má strom nanejvýš 3n vrcholů (s konstantním časem) → O(n).


A co dál? Uvědomíme si, že tabulku mezivýsledků není nutno vyplňovat rekurzivně. Jelikož k výpočtu T[k] potřebujeme pouze T[k - 1] a T[k - 2], vyplníme v pořadí T[0], T[1], T[2], …

Algoritmus Fib3(n): iterace 1. T[0] ← 0, T[1] ← 1 2. Pro k = 2, … ,n: 3. T[k] ← T[k - 1] + T[k - 2] 4. Vrátíme T[n]. Fib3(n) lze samozřejmě vymyslet i přímo, bez úvah o rekurzi.

Předvedený postup ovšem funguje i v méně přímočarých případech!

Princip dynamického programování: 1. Začneme s rekurzivním algoritmem, který je exponenciálně pomalý. 2. Odhalíme opakované výpočty stejných podproblémů. 3. Vytvoříme tabulku a zapisujeme vyřešené podproblémy. Tím prořežeme strom rekurze a vznikne rychlejší algoritmus. Tomuto přístupu se říká kešování a tabulce keš (cache). 4. Uvědomíme si, že keš lze vyplňovat bez rekurze, zvolíme-li vhodné pořadí podproblémů. Tím získáme stejně rychlý, ale jednodušší algoritmus.


Příklad řešení úlohy ACM* Flip Sort Řazení je důležitá součást Computer Science. Téměř každý problém může být řešen efektivně, pokud jsou data seřazena. Existuje několik výborných řadících algoritmů, které už překonaly hranici O (N log2N). Dále se budeme zabývat následujícím řadícím postupem. V tomto postupu bude dostupná pouze jedna operace, tzv. „flip“, a tou je výměna dvou sousedních prvků. Budete-li chvíli přemýšlet, zjistíte, že takto je možné vždy seřadit množinu čísel.

Formulace problému Je dána množina celých čísel. Za použití výše uvedeného postupu je možno zadaná čísla vzestupně seřadit. Vaším úkolem je zjistit, jaký nejmenší počet „flip“ operací je k seřazení nutný. Například k seřazení „1 2 3“ nepotřebujeme žádnou „flip“ operaci, zatímco k seřazení „2 3 1“ potřebujeme nejméně 2 „flip“ operace.

Vstup Na vstupu bude několik testovaných případů. Pro každý případ bude zadáno celé kladné číslo N (N≤1000) a na následující řádce bude zadáno N celých čísel oddělených mezerami. Vstup bude ukončen koncem souboru.

Výstup Pro každou množinu čísel vypište „Minimum exchange operations: M“, kde M je minimum „flip“ operací potřebných k vykonání řazení. Pro každý testovaný případ použijte pro výpis samostatný řádek. Strana 14 (celkem 25)

Ukázka vstupu: 1 5 3 123 3 231 4 4321 Ukázka výstupu 0 0 2 6

Jak budeme řešit? Existuje více postupů, budeme sledovat složitost 1. Naprogramujeme nejprve podle zadání průchod a operaci „flip“


int flip=0; int i=0; while(i < pole.length-1) { if(pole[i] > pole[i+1]) { int pom = pole[i+1]; pole[i+1] = pole[i]; pole[i] = pom; flip++; i=0; // od zacatku } else { i++; // dalsi

// pruchod // flip - prohozeni

} }

2

Složitost? O(n ), záleží na míře seřazení dat

Počet porovnání -

pro nejlepší případ: n - 1

i i  1 pro nejhorší případ: n  1   2 i 2 n

-

Výhodné pro částečně seřazené posloupnosti


2. Co flip operace připomíná? Použijeme Bubble Sort a budeme počítat výměny public class Main { public static void main(String args []) { Scanner sc = new Scanner(System.in); int flip = 0; while(sc.hasNextInt()) { int pocetPrvku = sc.nextInt(); int [] pole = new int[pocetPrvku]; flip = 0; for(int i=0;i<pocetPrvku;i++) { pole[i] = sc.nextInt(); } for (int i=0; i<pole.length; i++){ for (int j=0; j<pole.length-1; j++){ if(pole[j]>pole[j+1]) { int pom = pole[j+1]; pole[j+1]=pole[j]; pole[j]=pom; flip++; } } } } } 2

Složitost O(n ), počet porovnání = n (n-1) nezáleží na míře „seřazení“ dat


3. Další zlepšení – ukončení po seřazení public class Main { public static void main(String args []) { Scanner sc = new Scanner(System.in); int flip = 0; while(sc.hasNextInt()) { int pocetPrvku = sc.nextInt(); int [] pole = new int[pocetPrvku]; flip = 0; for(int i=0;i<pocetPrvku;i++) { pole[i] = sc.nextInt(); } for (int i=0; i<pole.length; i++){ boolean hotovo = true; for (int j=0; j<pole.length-1; j++){ if(pole[j]>pole[j+1]) { int pom = pole[j+1]; pole[j+1]=pole[j]; pole[j]=pom; hotovo = false; flip++; } }

if (hotovo){ break; } } }}}

Jak algoritmus ještě dále zlepšit? } }


4. Protože zadání po nás nepožaduje pole seřadit, nešlo by spočítat výměny bez řazení? Jak? Musíme zjistit, kolik prvků je menších než daný prvek a tudíž je nutno je prohodit. Pole procházíme zleva doprava a pro každý prvek hledáme, kolik je od něj napravo menších prvků. Počty těchto prvků sečteme. Příklad: Mějme v poli prvky: 9, 1, 2, 8, 6, 5, 3, 4 Pro prvek 9 je napravo od něj 7 menších prvků, pro 1 a 2 není žádný, pro 8 jsou 4, pro 6 jsou 3, pro 5 jsou 2, pro 3 a 4 není žádný takový prvek. Sečteme tučně vytištěná čísla (7+4+3+2=16) a tak získáme počet výměn. Složitost? (n-1) + (n-2) + (n-3) + ... + 2 + 1 = ((n-1)n)/2 = 2

= (n -n)/2


import java.io.*; import java.util.*; /** * Flip sort * ACM - example * @author netrvalo * @version 3 - 30.12.2010 */ public class Main { private static Scanner sc = new Scanner(System.in); public static void main(String args []) { while(sc.hasNextInt()) { int pocetPrvku = sc.nextInt(); int [] pole = new int[pocetPrvku]; int flip = 0; for(int i=0;i<pocetPrvku;i++) { pole[i] = sc.nextInt(); } // pocet "flipu" - pro rychlejsi vypocet se prvky v poli neprohazuji

for(int k = 0;k<pole.length-1;k++) { for(int j = k+1;j<pole.length;j++) { //kdyz je prvek s vetsim indexem mensi, zvetsime citac flip o 1

if(pole[k]>pole[j]) { flip++; } } } //vypiseme vysledek

System.out.println("Minimum exchange operations: "+flip); } }

} Strana 20 (celkem 25)

Úloha pro zájemce* Je dána posloupnost celých čísel a1, a2, ... an. Nalezněte celistvý úsek posloupnosti ai až aj, takový, aby součet hodnot těchto prvků byl maximální. Nezapomeňte, že indexy i, j představují pořadí prvků, tj. i, j > 0. Ilustrační příklady: {-2, 11, -4, 13, -5, 2}

i = 2, j = 4, s = 20

{1, -3, 4, -2, -1, 6}

i = 3, j = 6, s = 7

{-1, -3, -5, -7, -2}

i = 0, j = 0, s = 0

Pro řešení tohoto problému lze napsat odlišné, více či méně efektivní algoritmy:



Řešení hrubou silou



Řešení s kvadratickou složitostí



Řešení s lineární složitostí


1. Řešení hrubou silou Nejjednodušší (a nejméně efektivní) je algoritmus, který postupně projde všechny možné úseky, zjistí součet jejich prvků a vybere ten, který má největší součet. static int maxSoucet(int[] a) { int maxSum = 0; for (int i=0; imaxSum) { maxSum = sum; prvni = i; posledni = j; //první, poslední = nelokalni promenne } } } return maxSum; }

Časová složitost algoritmu je O (n3), tj. kubická


2. Řešení s kvadratickou složitostí Vnitřní cyklus počítající součet Si,j = a[i]+...+a[j] je zbytečný: známe-li součet Si,j-1 = a[i]+...+a[j-1], pak Si,j = Si,j-1+ a[j] static int maxSoucet(int[] a) { int maxSum = 0; for (int i=0; imaxSum) { maxSum = sum; prvni = i; posledni = j; } } } return maxSum; }

Časová složitost algoritmu je O (n2), tj. kvadratická


3. Řešení s lineární složitostí Řešení lze sestavit s použitím jediného cyklu s řídicí proměnnou j, která udává index posledního prvku úseku. Proměnná i udávající index prvního prvku úseku se bude měnit takto: – počáteční hodnota i = 0 – postupně zvětšujeme j a je-li součet úseku od i do j (sum) větší, než doposud největší součet (sumMax), uložíme: prvni=i, posledni=j, sumMax=sum – vznikne-li však zvětšením j úsek, jehož součet je záporný, pak žádný další úsek začínající indexem i a končící indexem j větším, nemůže mít součet větší, než je uložen – hodnotu proměnné i je proto možno nastavit na j+1 a sum na 0.


static int maxSoucet(int[] a) { int maxSum = 0; int sum = 0, i = 0; for (int j=0; jmaxSum) { maxSum = sum; prvni = i; posledni = j; } else if (sum<0) { i = j + 1; sum = 0; } } return maxSum; }

Časová složitost algoritmu je O (n), tj. lineární


Obsah 10. přednášky: Jak bude probíhat zkouška?! Podrobné informace:

Recommend Documents