Generátor řídkých matic. Kamil Šnajdr

České vysoké učení technické v Praze Fakulta elektrotechnická Katedra počítačů

Bakalářská práce

Generátor řídkých matic Kamil Šnajdr

Vedoucí práce: Ing. Ivan Šimeček, Ph.D.

Studijní program: Elektrotechnika a informatika, strukturovaný, Bakalářský Obor: Výpočetní technika 5. ledna 2011

iv

v

Poděkování Chtěl bych poděkovat panu Ing. Ivanu Šimečkovi, Ph.D., vedoucímu mé bakalářské práce, za jeho ochotu, kdykoliv jsem se na něj s něčím obrátil a za veškerou pomoc, kterou mi při tvorbě této práce poskytl.

vi

vii

Prohlášení Prohlašuji, že jsem práci vypracoval samostatně a použil jsem pouze podklady uvedené v přiloženém seznamu. Nemám závažný důvod proti užití tohoto školního díla ve smyslu §60 Zákona č. 121/2000 Sb., o právu autorském, o právech souvisejících s právem autorským a o změně některých zákonů (autorský zákon).

V Praze dne 5. 1. 2011

.............................................................

viii

Abstract This work describes the design and implementation of a sparse matrix generator. One of the goals was to provide a simple user interface and many possible settings of matrix parameters, including the generation of various types of matrices (symmetric, regular, singular, band). The matrices can also be viewed and edited in a visual form. The final outcome of the work is this document, describing the structure of the application and used algorithms, as well as the attached CD, which contains the complete program and its source codes.

Abstrakt Tato práce se zabývá návrhem a implementací generátoru řídkých matic. Cílem bylo vytvořit program, který bude poskytovat jednoduché uživatelské rozhraní a široké možnosti nastavení parametrů matic, včetně generování různých typů matic (symetrické, singulární, regulární, pásové). Aplikace též umožňuje zobrazení a editaci matic v grafické podobě. Výsledkem práce je tento dokument, popisující strukturu aplikace a využívané algoritmy, stejně jako přiložené CD, které obsahuje kompletní program i jeho zdrojové kódy.

ix

x

Obsah 1 Úvod

1

2 Popis problému 2.1 Matice . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.1 Řádková matice . . . . . . . . . . . . . . . . . . 2.1.2 Sloupcová matice . . . . . . . . . . . . . . . . . 2.1.3 Čtvercová matice . . . . . . . . . . . . . . . . . 2.1.4 Transponovaná matice . . . . . . . . . . . . . . 2.1.5 Symetrická matice . . . . . . . . . . . . . . . . 2.1.6 Trojúhelníková matice . . . . . . . . . . . . . . 2.1.7 Pásová matice . . . . . . . . . . . . . . . . . . . 2.1.8 Regulární matice . . . . . . . . . . . . . . . . . 2.1.9 Singulární matice . . . . . . . . . . . . . . . . . 2.1.10 Řídká matice . . . . . . . . . . . . . . . . . . . 2.2 Formát Matrix Market pro ukládání maticových dat . 2.2.1 Coordinate Format pro řídké matice . . . . . . 2.2.2 Specifikace Matrix Market formátu pro matice

. . . . . . . . . . . . . .

3 3 4 4 4 4 4 5 5 5 6 6 6 7 7

. . . . . . . . . . .

9 9 9 10 11 11 11 11 11 12 13 14

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

3 Analýza a návrh řešení 3.1 Volba technologie . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Průběh činnosti programu . . . . . . . . . . . . . . . . . . . . 3.3 Struktura systému . . . . . . . . . . . . . . . . . . . . . . . . 3.3.1 GUI . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.2 MatrixGenerator . . . . . . . . . . . . . . . . . . . . . 3.3.3 MatrixMarketIO . . . . . . . . . . . . . . . . . . . . . 3.3.4 Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Popis GUI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4.1 Hlavní okno . . . . . . . . . . . . . . . . . . . . . . . . 3.4.2 Okno zobrazující matici jako tabulku . . . . . . . . . . 3.4.3 Okno zobrazující matici jako seznam nenulových prvků

. . . . . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . .

4 Popis implementace 17 4.1 Celkový úvod do implementace . . . . . . . . . . . . . . . . . . . . . . . . . . 17 4.2 Třídy tvořící aplikaci . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 4.3 Třída MainWindow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

xi

xii

OBSAH

4.4 4.5 4.6 4.7 4.8

Třída Třída Třída Třída Třída 4.8.1

4.8.2 4.8.3 4.8.4 4.8.5 4.9 Třída 4.10 Třída

MatrixTable . . . . . . . . . . . . . . . . . . . ElementEditor . . . . . . . . . . . . . . . . . MatrixTableModel . . . . . . . . . . . . . . . ElementTableModel . . . . . . . . . . . . . . . MatrixGenerator . . . . . . . . . . . . . . . . Generování singulárních matic . . . . . . . . . 4.8.1.1 Speciální případy singulárních matic Generování regulárních matic . . . . . . . . . Generování symetrických matic . . . . . . . . Generování ostatních typů matic . . . . . . . Optimalizování generovacích algoritmů . . . . MatrixMarketIO . . . . . . . . . . . . . . . . . Matrix . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

19 20 20 21 25 26 27 27 28 28 29 29 30

5 Závěr

31

A Vývojové diagramy

35

B Instalační a uživatelská příručka B.1 Instalační příručka . . . . . . . . . . . . . . . . . . . . . . . . . B.1.1 Instalace pro operační systém Microsoft Windows . . . . B.1.2 Kompilace programu pod ostatními operačními systémy B.2 Uživatelský manuál . . . . . . . . . . . . . . . . . . . . . . . . . B.2.1 Postup generování matice . . . . . . . . . . . . . . . . . B.2.2 Pokročilé nastavení generování . . . . . . . . . . . . . . B.2.3 Načítání matice . . . . . . . . . . . . . . . . . . . . . . . C Obsah přiloženého CD

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

41 41 41 41 42 42 42 43 45

Seznam obrázků 2.1 2.2 2.3 2.4 2.5 2.6

Ukázka matice . . . . . . . Dva různé zápisy matice . . Transponovaná matice . . . Symetrická matice . . . . . Dolní a horní trojúhelníková Pásová matice . . . . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

3 4 4 5 5 6

3.1 3.2 3.3 3.4

Hlavní okno programu - záložka Generování . . . . . . Hlavní okno programu - záložka Editace . . . . . . . . Zobrazení matice ve formě tabulky . . . . . . . . . . . Zobrazení matice ve formě seznamu nenulových prvků

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

12 13 14 15

A.1 A.2 A.3 A.4

Vývojový Vývojový Vývojový Vývojový

singulárních matic . regulárních matic . . symetrických matic . ostatních typů matic

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

36 37 38 39

diagram diagram diagram diagram

algoritmu algoritmu algoritmu algoritmu

. . . . . . . . . . . . . . . . matice . . . .

pro pro pro pro

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

generování generování generování generování

xiii

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

xiv

SEZNAM OBRÁZKŮ

Seznam tabulek 2.1 2.2 2.3

Možné hodnoty parametru format . . . . . . . . . . . . . . . . . . . . . . . . Možné hodnoty parametru field . . . . . . . . . . . . . . . . . . . . . . . . . . Možné hodnoty parametru symmetry . . . . . . . . . . . . . . . . . . . . . . .

xv

8 8 8

xvi

SEZNAM TABULEK

Kapitola 1

Úvod Cílem této práce bylo vytvoření generátoru řídkých matic. Matice jsou využívány v různých oblastech matematiky, fyziky a informatiky. Vývojáři, kteří vytvářejí algoritmy, které s maticemi pracují, často potřebují otestovat jeho funkci na různých typech matic s různými vlastnostmi. Jelikož by ruční vytváření mnoha matic bylo velice zdlouhavé, je příjemné mít možnost využít nějaký vhodný generátor, který tuto práci udělá za vás. Generátor by však neměl vytvářet matice zcela náhodně, nýbrž by měl umožňovat uživateli stanovit jejich kritéria podle potřeby. Výsledný generátor by tedy měl poskytovat široké možnosti nastavení parametrů výsledné matice, neboť je vhodné a potřebné testovat matice různého druhu, různé velikosti a s různým počtem prvků. Matice vytvořené takovýmto generátorem budou poté používány v rozličných aplikacích, nebylo by tedy vhodné, aby generátor ukládal matice v nějakém vlastním, nově vytvořeném formátu, ale místo toho by měl využívat některý široce rozšířený a pro tyto účely vytvořený formát. Z tohoto důvodu byl zvolen pro ukládání matic formát Matrix Market, který uvedená kritéria splňuje.

1

2

KAPITOLA 1. ÚVOD

Kapitola 2

Popis problému Jak bylo uvedeno v kapitole Úvod, generátor řídkých matic musí nabízet možnost stanovit parametry generovaných matic. Program nabízí jednoduché a přehledné grafické uživatelské rozhraní (GUI), kde může uživatel pomocí přepínačů a vstupních polí nastavit rozměry matice, typ hodnot prvků a také různé druhy generovaných matic. V této kapitole si vysvětlíme, co to vlastně matice jsou a čím se liší jednotlivé typy matic. Vygenerovaná matice je poté uložena ve formátu Matrix Market. Stejně tak může uživatel matici v tomto formátu načíst a pomocí programu ji upravit. Strukturu formátu Matrix Market si popíšeme také v této kapitole.

2.1

Matice

Matice je obdélníkové pole (tabulka) čísel. Horizontální a vertikální řady těchto hodnot jsou nazývány řádky, respektive sloupce. Čísla v matici jsou nazývány prvky nebo elementy. Matice s m řádky a n sloupci je označována jako matice typu m × n, kde m a n jsou dimenze matice. Prvek, který leží v i-tém řádku a j-tém sloupci matice A, je většinou označován jako aij . Příklad matice můžete vidět na obrázku 2.1.

a1,3

a2,1

a2,2

a2,3

a3,1

a3,2

a3,3

. . .

. . .

. . .

. . .

a1,2

. . .

a1,1

. . .

i c h a n g e s

j changes

n columns

.

m rows

..

ai,j

Obrázek 2.1: Ukázka matice (převzato z [5])

3

4

KAPITOLA 2. POPIS PROBLÉMU

Řádky a sloupce matice jsou standardně indexovány od čísla 1, což se liší od některých programovacích jazyků (např. C++), kde indexy polí začínají od 0. Matice bývají zapisovány jako tabulka čísel, uzavřená do kulatých závorek, používá se ale také zápis ve hranatých závorkách (viz obrázek 2.2).    9 13 6 9 13 6 1 11 7 1 11 7    A= 3 9 2 A = 3 9 2 6 0 7 6 0 7 

Obrázek 2.2: Dva možné zápisy matice — v kulatých a hranatých závorkách

2.1.1

Řádková matice

Matice typu 1 × n, to znamená, matice skládající se z jednoho řádku o n elementech.

2.1.2

Sloupcová matice

Matice typu m × 1, to znamená, matice skládající se z jednoho sloupce o m elementech.

2.1.3

Čtvercová matice

Čtvercová matice je taková matice, která má stejný počet řádek jako sloupců, tedy n = m. Matice n × n je označována jako čtvercová matice řádu n.

2.1.4

Transponovaná matice

Transponovaná matice AT je matice, která vznikla z matice A vzájemnou výměnou řádků a sloupců. T 1 2 3 4  = 1 3 5 2 4 6 5 6 

Obrázek 2.3: Příklad transponované matice (převzato z [6])

2.1.5

Symetrická matice

Symetrická matice je čtvercová matice, která je rovna své transponované matici, platí tedy A = AT . Prvky symetrické matice jsou symetrické podle hlavní diagonály, to znamená aij = aji . Příklad symetrické matice můžete vidět na obrázku 2.4.

2.1. MATICE

5



 1 2 3 2 4 −5 3 −5 6 Obrázek 2.4: Ukázka symetrické matice

2.1.6

Trojúhelníková matice

Trojúhelníková matice je taková matice, která má všechny prvky pod nebo nad hlavní diagonálou nulové. Matice s nulovými prvky nad hlavní diagonálou je nazývána dolní trojúhelníková matice, opačná matice se nazývá horní trojúhelníková matice. 

l1,1  l2,1 l2,2   .. . L=  l3,1 l3,2  .. .. . ..  . . ln,1 ln,2 · · ·

..

. ln,n−1





u1,1 u1,2 u1,3 · · ·   u2,2 u2,3 · · ·     .. ..  U = . .     . ..   0 ln,n 0

u1,n u2,n .. .



      un−1,n  un,n

Obrázek 2.5: Ukázka dolní (vlevo) a horní trojúhelníkové matice (převzato z [7])

2.1.7

Pásová matice

Pásová matice je taková řídká matice, jejíž nenulové prvky se nacházejí v diagonálním pásu, složeném z hlavní diagonály a několika (0 či více) diagonál na obou stranách. Je to tedy taková matice, jejíž všechny prvky jsou nulové mimo diagonálního pásu, jehož velikost je určena konstantami k1 a k2 : aij = 0 pokud j < i − k1 nebo j > i + k2 , kde k1 udává šířku poddiagonálního pásu, zatímco k2 šířku naddiagonálního pásu. Pásová matice s k1 = k2 = 0 je diagonální matice (matice s nenulovými prvky pouze na hlavní diagonále). Ukázku pásové matice můžete vidět na obrázku 2.6.

2.1.8

Regulární matice

Regulární matice je taková čtvercová matice, jejíž determinant je různý od nuly. Ekvivalentně lze též tvrdit, že její řádky a sloupce jsou lineárně nezávislé. Důležitou vlastností regulárních matic je možnost jednoznačně vypočítat inverzní matici.

6


  B11 B12 0 ··· ··· 0  ..  B21 B22 B23 . . . . . . .      . . . .  0 B32 B33 B34 . .     ..  . .  . . B43 B44 B45 0     ..  .. .. . . B54 B55 B56   . 0 ··· ··· 0 B65 B66 Obrázek 2.6: Ukázka pásové matice s k1 = k2 = 1 (převzato z [3])

2.1.9

Singulární matice

Singulární matice je opakem regulární matice, to znamená, že její determinant je nulový. Její řádky a sloupce jsou lineárně závislé a neexistuje pro ni inverzní matice.

2.1.10

Řídká matice

Řídká matice je taková matice, jejíž většina prvků se rovná nule. Není definována přesná hranice, kdy je matice ještě označována za řídkou a kdy už ne, ale obecně platí, že matice se zaplněním menším než 10% jsou považovány za řídké. Řídké matice umožňují úspornější uložení v paměti počítače, neboť není nutné ukládat hodnoty všech prvků, ale pouze těch, jejichž hodnota není nulová. Pro zápis řídkých matic existuje několik různých formátů, které ale pro naši práci nejsou podstatné.

2.2

Formát Matrix Market pro ukládání maticových dat

Matrix Market formát[1] poskytuje snadný způsob pro ukládání a výměnu matic. Tento formát je využíván službou Matrix Market, databází maticových testovacích dat přístupnou na internetu, pro niž byl vytvořen. Hlavním cílem při návrhu tohoto formátu bylo, aby umožňoval snadné parsování vstupního souboru při načítání matice, především v jazyce C je čtení dat velmi jednoduché pomocí standardní funkce scanf(). Matrix Market je ve skutečnosti kolekce příbuzných formátů, které sdílejí designové prvky. V současnosti existují dva formáty: 1. Coordinate format — formát vhodný pro reprezentování řídkých matic, jsou ukládány pouze nenulové prvky a souřadnice každého prvku jsou zadány explicitně 2. Array format — formát vhodný pro ukládání hustých matic, jsou vypsány všechny prvky matice v definovaném pořadí (po sloupcích) Tato práce se zaměřuje především na generování řídkých matic, a proto se v dalším textu budeme věnovat pouze coordinate formátu.

2.2. FORMÁT MATRIX MARKET PRO UKLÁDÁNÍ MATICOVÝCH DAT

2.2.1

7

Coordinate Format pro řídké matice

Coordinate formát je vhodný pro ukládání řídkých matic. Jeho strukturu si ukážeme na následujícím příkladu. Uvažujme následující 5 × 5 matici. 

 1 0 0 6 0 0 10.5 0 0 0    0  0 .015 0 0   0 250.5 0 −280 33.32 0 0 0 0 12 V MM coordinate formátu by byla reprezentována takto: %%MatrixMarket matrix coordinate real general % řídká matice rozměru 5x5 s 8 nenulovými prvky 5 5 8 1 1 1.0 2 2 10.5 4 2 250.5 3 3 0.015 1 4 6.0 4 4 -280.0 4 5 33.32 5 5 12.0 První řádek obsahuje hlavičku %%MatrixMarket následovanou sekvencí klíčových slov, která oznamují, že pracujeme s maticí uloženou v coordinate formátu, její hodnoty jsou typu real (desetinná čísla) a typ matice je general. Druhý řádek je komentář. Na tomto místě v souboru se může nacházet 0 nebo více řádků s komentářem, každý z nich musí začínat znakem %. Následující řádek obsahuje tři čísla, která udávají počet řádků, počet sloupců a počet nenulových prvků v matici. Další řádky poté obsahují popis jednotlivých nenulových prvků. První dvě čísla udávají souřadnice prvku (i,j) a pak následuje hodnota prvku. Indexy řádků i sloupců začínají od 1.

2.2.2

Specifikace Matrix Market formátu pro matice

V této podkapitole popíšeme přesnou strukturu MatrixMarket formátu pro ukládání matic a vysvětlíme, jaký význam mají jednotlivé parametry. První řádek souboru (hlavička) musí odpovídat tomuto vzoru: %%MatrixMarket matrix format field symmetry parametr format tento parametr určuje formát využitý pro uložení matice a může nabývat dvou hodnot, oba formáty byly již popsány v sekci 2.2:

8


kód coordinate array

význam řídká matice, uloženy pouze nenulové prvky hustá matice, uloženy všechny prvky v definovaném pořadí Tabulka 2.1: Možné hodnoty parametru format

parametr field tento parametr určuje typ hodnot jednotlivých prvků matice: kód real integer complex pattern

význam hodnota prvku je reprezentována desetinným číslem matice obsahuje pouze celočíselné hodnoty, každý prvek je reprezentován jedním celým číslem matice je komplexní, každý prvek matice je reprezentován dvěma desetinými čísly, která udávají reálnou a imaginární část komplexního čísla jsou poskytnuty pouze souřadnice jednotlivých nenulových prvků, jejich hodnoty chybí (používáno, pokud chceme uložit pouze šablonu matice udávající rozmístění prvků, nikoli jejich hodnoty) Tabulka 2.2: Možné hodnoty parametru field

parametr symmetry tento parametr určuje typ symetrie matice, symetrie určuje také to, které prvky jsou dále v souboru uvedeny: kód general symmetric

skew-symmetric

hermitian

význam matice není symetrická, jsou uvedeny všechny nenulové prvky čtvercová matice, pro jejíž prvky platí aij = aji . V souboru jsou uvedeny pouze prvky na hlavní diagonále a pod ní. Prvky nad hlavní diagonálou jsou známy podle symetrie. čtvercová matice, pro jejíž prvky platí aij = −aji . Jsou uvedeny pouze prvky pod hlavní diagonálou. Prvky na hlavní diagonále jsou nulové a prvky nad diagonálou jsou známy podle symetrie. čtvercová matice s komplexními prvky, pro něž platí aij = aji (symetrické prvky jsou tedy čísla komplexně sdružená). Jsou uvedeny pouze prvky na hlavní diagonále a pod ní. Prvky nad hlavní diagonálou jsou známy dle symetrie. Tabulka 2.3: Možné hodnoty parametru symmetry

Kapitola 3

Analýza a návrh řešení Než se pustíme do tvorby nějakého programu, je nejprve potřeba povést analýzu problému — musíme určit, jakou budeme využívat technologii (výběr programovacího jazyka a příslušných knihoven či frameworků), navrhnout strukturu jednotlivých tříd v aplikaci, a také vytvořit uživatelské rozhraní. Obsahem této kapitoly je právě popis jednotlivých kroků při návrhu aplikace a také představení finální verze GUI.

3.1

Volba technologie

Pro implementaci byl zvolen jazyk C++. Rozhodoval jsem se mezi C++ a Javou, což jsou dva jazyky, které ovládám nejlépe, ale nakonec jsem zvolil C++, protože s ním mám větší zkušenosti a je mi o něco bližší. Narozdíl od Javy není C++ interpretovaný jazyk, to sice znamená, že jeden program nemůže být spuštěn (interpretován) na různých operačních systémech, nýbrž se musí zdrojový kód zkompilovat pro každý systém zvlášť, ale na druhou stranu je díky tomu běh programu rychlejší. Protože samotné C++ neposkytuje prostředky k vytváření grafického uživatelského rozhraní, je k tomu potřeba využít některý z aplikačních frameworků. Byl zvolen framework Qt, protože je poměrně populární (je tedy možné snadno najít řešení problému, pokud člověk na nějaký narazí), dobře dokumentovaný a podporuje velké množství platforem, takže není problém výslednou aplikaci zkompilovat pod různými operačními systémy.

3.2

Průběh činnosti programu

Program umožňuje generovat matice různých typů a s různými parametry. Aby uživatel mohl nastavit požadované parametry dle svého přání, musí mu být poskytnuty příslušné přepínače a tlačítka. Rozhodl jsem se, že všechny ovládací prvky budou umístěny na jedné obrazovce, aby uživatel nemusel přecházet mezi různými okny, záložkami nebo položkami v menu. Dalším úkolem bylo dát uživateli možnost pokročilého nastavení prvků v matici — to znamená, že uživatel bude moci před generováním nastavit některé prvky na požadovanou hodnotu a vygenerovat pouze zbývající. K tomu byla vytvořena dvě nová okna, která může uživatel zobrazit stisknutím příslušného tlačítka na hlavní obrazovce. První z nich zobrazí

9

10

KAPITOLA 3. ANALÝZA A NÁVRH ŘEŠENÍ

matici ve standardní podobě (jako tabulku) a uživatel má možnost editovat jednotlivé buňky a tím nastavit prvkům hodnotu. Takto je možné zobrazit matice o velikosti maximálně 40 × 40, protože pro matice větších rozměrů by byla tabulka již příliš velká a nepřehledná. Aby bylo možné nastavit prvky i pro matice větších rozměrů, byl vytvořen ještě druhý způsob zobrazení matice. V tomto okně je matice zobrazena jako seznam, který obsahuje pouze nenulové prvky v matici. Pro každý prvek je v seznamu vedle sebe zobrazen jeho index a hodnota. Uživatel může přidat do matice nový prvek vyplněním jeho indexu a hodnoty do vstupních polí a také může samozřejmě prvky ze seznamu mazat nebo je v něm editovat. Po vygenerování matice má uživatel možnost matici zobrazit, editovat a uložit na disk. Ke zpřístupnění těchto voleb byla vytvořena nová záložka Editace, která se po vygenerování matice automaticky zobrazí. Matici může uživatel opět zobrazit dvěma způsoby (tabulka a seznam prvků). K jejímu zobrazení se využívají stejná okna jako při nastavování prvků a zobrazená matice může být libovolně editována. Když je uživatel s maticí spokojen, může ji uložit na disk. Jako výstupní formát byl zvolen formát Matrix Market, který je k ukládání řídkých matic přímo navržen a existuje řada aplikací, které ho využívají. Mezi záložkami Generování a Editace se může uživatel libovolně přepínat (pokud je záložka Editace přístupná) a může tedy po vygenerování matice ihned začít s novým generováním. Záložka Editace je přístupná pouze tehdy, pokud byla nějaká matice vygenerována nebo načtena. Nakonec si ještě ukážeme celkový postup běhu programu: 1. po spuštění programu je zobrazeno hlavní okno 2. uživatel nastaví požadované parametry generátoru, všechna vstupní pole jsou ošetřena tak, aby nebylo možné zadat nesprávné hodnoty 3. uživatel má možnost zobrazit editační okno a nastavit hodnoty některých prvků v matici 4. uživatel stiskne tlačítko Generovat, bude vygenerována matice podle zadaných parametrů a zobrazena záložka Editace 5. vygenerovaná matice může být zobrazena a editována 6. uživatel může matici uložit do souboru

3.3

Struktura systému

V předchozí části jsme si popsali, jak bude probíhat činnost programu, nyní ještě zbývá rozdělit aplikaci do jednotlivých tříd. Jádrem programu bude třída MatrixGenerator, která bude obsahovat funkce pro generování matic a její součástí bude i samotná datová struktura reprezentující matici. Třídy tvořící GUI budou s touto třídou komunikovat. Vstup a výstup bude prováděn pomocí třídy MatrixMarketIO, přičemž maticová data budou předávána jako instance třídy Matrix.

3.4. POPIS GUI

3.3.1

11

GUI

Jak bylo popsáno v sekci 3.2, aplikace se skládá ze tří oken — jednoho hlavního a dvou pomocných, která umožňují zobrazit a editovat matici. GUI se budeme podrobně zabývat v části 3.4, takže nyní si ho projdeme jenom stručně. Hlavní okno programu se stará o vstup od uživatele a zobrazuje ostatní okna, pokud je to potřeba. Toto okno spolupracuje se třídou MatrixGenerator — nastavuje parametry matice a volá její metody, pokud chce uživatel generovat, uložit nebo načíst matici. Zbylá dvě okna slouží k zobrazení matice a také komunikují s třídou MatrixGenerator — načítají z ní data, která mají zobrazit, a pokud uživatel provedl změny a chce je uložit, tak tato změněná data zase posílají zpátky. Velikost každého okna se dá měnit a rozmístění ovládacích prvků se přizpůsobuje novým rozměrům. Při návrhu jsem uvažoval, zda bych měl editační okna vytvořit hned při spuštění programu a pouze je podle potřeby zobrazovat a skrývat, nebo okno vytvořit ve chvíli, kdy chce uživatel zobrazit matici a po jeho uzavření ho zničit. Nakonec jsem se rozhodl pro první možnost, kdy jsou okna vytvořena při startu programu a při zobrazení matice se pouze provede načtení nových dat. Předpokládám totiž, že uživatel bude chtít matici zobrazit často, takže by neustálé vytváření a mazání oken nebylo ideální. Všechna tři okna byla vytvořena pomocí utility Qt Designer, což je nástroj, který umožňuje návrh uživatelského rozhraní ve vizuální podobě - přetahováním ovládacích prvků na formulář.

3.3.2

MatrixGenerator

Tato třída bude tvořit jádro programu. Komunikace s GUI bude probíhat tak, že GUI nejprve předá této třídě parametry nastavené uživatelem a poté zavolá metodu generate(), která se postará o vygenerování matice dle zadaných parametrů. V případě, že chce uživatel provést vstup nebo výstup do souboru, zavolá GUI příslušné metody a MatrixGenerator následně zavolá funkce třídy MatrixMarketIO, které se o to postarají. Podrobný popis této třídy naleznete v kapitole 4.8.

3.3.3

MatrixMarketIO

Tato třída bude zajišťovat vstup a výstup ve formátu MatrixMarket, k čemuž budou sloužit funkce save() a load(). Samotná matice bude mezi touto třídou a třídou MatrixGenerator předávána jako instance třídy Matrix.

3.3.4

Matrix

Tato třída bude reprezentovat matici při vstupu a výstupu. Bude obsahovat proměnné určující parametry matice (rozměry, typ) a samotná data (indexy nenulových prvků a jejich hodnoty).

3.4

Popis GUI

V této části naleznete podrobný popis jednotlivých částí grafického uživatelského rozhraní.

12


Obrázek 3.1: Hlavní okno programu - záložka Generování

3.4.1

Hlavní okno

Jak můžete vidět na obrázcích 3.1 a 3.2, okno je tvořeno dvěma záložkami — Generování a Editace. Po spuštění programu je aktivní pouze záložka Generování, kde může uživatel nastavit parametry matice — rozměry, počet nenulových prvků, maximální hodnotu prvku, typ hodnot a typ matice. Po vygenerování matice nebo načtení matice ze souboru bude aktivována záložka Editace. Zde může uživatel zobrazit matici jako tabulku nebo jako seznam nenulových prvků, či matici uložit do souboru. U všech políček umožňujících vstup uživatele jsou vždy nastaveny limity tak, aby nebylo možné zadat nesmyslné hodnoty. Pokud je např. rozměr matice nastaven na 10 × 10, je maximální možná hodnota pro počet nenulových prvků nastavena na 100. Stejně tak pokud je vybrána například horní trojúhelníková matice, je přepočítán maximální počet nenulových prvků s ohledem na to, že pod hlavní diagonálou musí být samé nuly. Pokud je vybrán speciální typ matice, který je definován pouze pro matice čtvercových rozměrů (jako např. regulární matice), je aktivní pouze spinBox pro nastavení výšky matice, a šířka matice je automaticky nastavena na stejnou hodnotu. Maximální rozměry matice jsou 1000 × 1000 a maximální hodnota prvku 100 000. V dolní části obrazovky se nachází dvě tlačítka, která umožňují pokročilé nastavení. Po kliknutí na jedno z nich se otevře okno s maticí zobrazenou buď jako tabulka nebo jako seznam nenulových prvků (viz kapitoly 3.4.2 a 3.4.3). Ve standardním maticovém tvaru je možné zobrazit pouze matice o velikosti maximálně 40×40. Zde má uživatel možnost nastavit

3.4. POPIS GUI

13

Obrázek 3.2: Hlavní okno programu - záložka Editace

hodnoty konkrétních prvků matice. Při následném generování budou tyto hodnoty zachovány a vygenerovány budou pouze prvky chybějící do zadaného počtu nenulových prvků. Toto pokročilé nastavení je však možné pouze pro standardní typ matice. Pokud je vybrán nějaký speciální typ matice z menu na pravé straně okna, jsou tato tlačítka neaktivní. Na záložce Editace můžete vygenerovanou nebo načtenou matici zobrazit též jako tabulku nebo seznam prvků. Rozdíl je v tom, že v režimu Generování program kontroluje, zda jsou dodržována nastavení generátoru — tzn. že nedovolí nastavit prvku vyšší hodnotu, než je zadané maximum, nedovolí vložit záporné číslo, pokud jsou nastavena pouze kladná a kontroluje, zda nebyl překročen vybraný počet nenulových prvků. V režimu Editace se žádné takové kontroly neprovádějí.

3.4.2

Okno zobrazující matici jako tabulku

Toto okno slouží k zobrazení matice ve standardním maticovém tvaru. Jednotlivé buňky tabulky zobrazují hodnotu příslušných prvků v matici, tabulku je možno běžným způsobem editovat a měnit tak hodnoty prvků. Pokud je zobrazená matice symetrická, je při změně některého prvku automaticky změněn i symetrický prvek na opačné straně diagonály. Pomocí nabídek v menu můžete provedené změny uložit a vrátit se do hlavního okna, nebo změny zrušit. Také zde můžete aktuální matici rovnou uložit do výstupního souboru na disk.

14


Obrázek 3.3: Zobrazení matice ve formě tabulky

3.4.3

Okno zobrazující matici jako seznam nenulových prvků

Toto okno zobrazuje matici jako seznam nenulových prvků. V horní části se nachází vstupní pole pro vkládání nových prvků. Všechny vložené prvky jsou zobrazeny v tabulce v levé části. Index může být zadán buď jako jedno číslo (prvky matice jsou číslovány po řádcích a číslování začíná od 1), nebo ve formátu „řádek sloupec“ (dvě čísla oddělená mezerou). Pokud je matice zobrazena v režimu generování, nemusí se vyplňovat hodnota prvku, hodnota prvku bude poté doplněna při generování matice. Toho se dá využít, pokud chcete, aby se prvky matice nacházely na konkrétních pozicích, ale jejich hodnoty chcete nechat vygenerovat automaticky. V režimu Editace se hodnota vyplnit musí. Seznam prvků je seřazený vzestupně dle indexu a editovatelný, takže můžete změnit index prvku a tím ho přesunout na jiné místo nebo změnit jeho hodnotu. Program vždy kontroluje, zda není zadán nesmyslný index či zda se na tomto indexu už nenachází jiný prvek. Stav tlačítek „Vložit“, „Smazat vybrané“ a „Smazat všechny“ se mění mezi enabled či disabled 1 podle aktuálního stavu okna. Tlačítko „Vložit“ je enabled, pokud tabulka obsahuje méně prvků, než je nastavený maximální počet nenulových prvků. Tlačítko „Smazat všechny“ je aktivní, pokud tabulka obsahuje alespoň jeden řádek a tlačítko „Smazat vybrané“ je aktivní, pokud uživatel označil některý z řádků tabulky. Tlačítkem „Hotovo“ se uloží veškeré provedené změny, stisknutím tlačítka „Zrušit“ se matice vrátí do takového stavu, v jakém byla před otevřením editoru.

1

stavy enabled a disabled určují, zda může být tlačítko uživatelem stisknuto nebo ne

3.4. POPIS GUI

Obrázek 3.4: Zobrazení matice ve formě seznamu nenulových prvků

15

16


Kapitola 4

Popis implementace V následující kapitole si popíšeme implementaci generátoru matic. Budou představeny jednotlivé třídy, z nichž se program skládá a také nejdůležitější algoritmy. Nejprve začneme souhrnným popisem programu jako celku a poté se podíváme podrobně na jednotlivé třídy tvořící aplikaci.

4.1

Celkový úvod do implementace

Program je napsaný v jazyce C++ s využitím multiplatformní knihovny Qt[2]. Qt je framework určený k vytváření programů s grafickým uživatelským rozhraním. Poskytuje řadu tříd reprezentujících jednotlivé prvky rozhraní, jako jsou okna (třídy QMainWindow nebo QWidget), tlačítka (QButton), textová pole (QTextEdit), popisky (QLabel) a podobně. Jak jste si jistě všimli, poznávacím znakem tříd z této knihovny je to, že jejich název začíná na písmenko Q. Kromě uživatelského rozhraní obsahuje knihovna také třídy implementující standardní datové struktury jako je seznam (QList) nebo mapa (QMap) a mnoho algoritmů, které s těmito strukturami pracují. Zajímavostí Qt je systém pro komunikaci mezi objekty — tzv. signály a sloty. Signál je vyslán, když dojde k určité události. Slot je funkce, která je volána jako odpověď na takovýto signál. Např. při stisknutí tlačítka je vyvolán signál clicked(), který může být připojen ke slotu pro zavření okna. Signály i sloty můžeme vytvářet podle svojí potřeby a vzájemně je spolu propojovat. Spojení signálu se slotem se provede pomocí funkce connect() — tím se zajistí, že pokaždé, když je vyslán tento signál, bude proveden připojený slot. Nyní se již podívejme na strukturu samotného Generátoru řídkých matic. Aplikace je v podstatě tvořena třemi okny —- jedním hlavním oknem, které se zobrazí po spuštění programu a kde uživatel nastavuje parametry matice, a dále dvěma pomocnými okny sloužícími k zobrazení a editaci matice. Jedno z těchto editačních oken zobrazuje matici v běžném maticovém formátu jako tabulku (s m řádky a n sloupci pro matici rozměru m×n), zatímco druhé zobrazuje matici jako seznam nenulových prvků (je zobrazen index prvku a jeho hodnota). Jádrem programu je třída MatrixGenerator, která poskytuje funkce pro generování matic a všechny ostatní třídy, které potřebují k těmto funkcím přistupovat, v sobě obsahují odkaz na její instanci. Samotná matice je v programu reprezentována jako mapa (QMap), kde klíčem je index prvku. Je pravda, že matici by bylo možné ukládat paměťově úsporněji jako pole, ale

17

18

KAPITOLA 4. POPIS IMPLEMENTACE

reprezentace ve formě mapy usnadňuje manipulaci s prvky matice při editování a generování, a proto jsem zvolil tuto formu. V případě, že matice, se kterou se právě pracuje, je symetrická, tak jsou v mapě uloženy pouze prvky nacházející se na hlavní diagonále nebo pod ní. Prvky nad hlavní diagonálou lze určit dle symetrie, takže je zbytečné vkládat je do mapy. Program umožňuje vstup a výstup ve formátu MatrixMarket. Jsou podporovány soubory o těchto parametrech (jejich význam je popsán v kapitole 2.2 na straně 6, která podrobně pojednává o tomto formátu): • format: coordinate • field: integer nebo real • symmetry: general nebo symmetric

4.2

Třídy tvořící aplikaci

V této kapitole si stručně představíme všechny třídy, z nichž se aplikace skládá. Každá z nich je podrobně popsána v následujících sekcích.

Třídy reprezentující GUI Tyto třídy reprezentují okna uživatelského rozhraní, se kterými se může uživatel setkat. Patří sem hlavní okno, které slouží k ovládání generátoru a dále dvě okna umožňující zobrazení a editaci prvků matice (dvěma různými způsoby). • MainWindow — hlavní okno programu, zde uživatel nastavuje všechny parametry generátoru matic • MatrixTable – zobrazení matice ve standardním maticovém formátu (jako tabulka) • ElementEditor – zobrazení matice jako seznam nenulových prvků Datové modely pro tabulky Na některých místech GUI jsou uživateli zobrazována data prostřednictvím tabulky. Tyto tabulky využívají tzv. model/view architekturu, to znamená, že neobsahují vlastní datové složky, ale data získávají z datových modelů pomocí jednotného rozhraní. • MatrixTableModel – datový model pro tabulku zobrazující matici v maticovém formátu • ElementTableModel – datový model pro tabulku zobrazující seznam nenulových prvků matice

4.3. TŘÍDA MAINWINDOW

19

Třídy zajišťující funkci generátoru matic • MatrixGenerator — hlavní třída programu, provádí vlastní generování matic a komunikuje se všemi ostatními třídami • MatrixMarketIO – třída poskytující vstup a výstup ve formátu MatrixMarket • Matrix – datová třída reprezentující matici, předávána mezi generátorem a IO při ukládání a načítání matice

4.3

Třída MainWindow

Tato třída reprezentuje hlavní okno programu. Jeho obrázek a popis uživatelského rozhraní najdete v kapitole 3.4.1, v této části se zaměřujeme na popis z programátorského hlediska. Tato třída obsahuje většinou funkce, které se starají o zpracování požadavků zadaných uživatelem. Uživatelské rozhraní bylo vytvořeno pomocí programu Qt Designer, proto se musí v konstruktoru nejprve toto rozhraní načíst pomocí funkce setupUi(). Poté se v konstruktoru rovnou vytvoří nové instance tříd ElementEditor a MatrixTable, které reprezentují okna pro zobrazení matice, a tyto okna zůstanou vytvořena po celou dobu běhu programu, dokud nejsou v destruktoru opět smazána. V konstruktoru se také připojí signály k příslušným slotům, čímž se zajistí, aby se po stisknutí nějakého tlačítka uživatelem provedla odpovídající funkce. Dále je tato třída tvořena víceméně pouze sloty, které jsou připojeny k příslušným tlačítkům uživatelského rozhraní. Jedná se např. o tyto sloty: • generateMatrix() — připojen k tlačítku Generovat, provádí komunikaci s třídou MatrixGenerator, nejprve nastaví příslušné parametry pomocí funkce setOptions() a poté spustí generování voláním funkce generate() • save() — volá funkci save() třídy MatrixGenerator, čímž uloží matici • showElementEditor() — zobrazí editační okno matice ve formě seznamu nenulových prvků Myslím, že tyto sloty není nutné dále popisovat, jejich funkce je naprosto zřejmá.

4.4

Třída MatrixTable

Tato třída reprezentuje okno zobrazující matici jako tabulku. Celá třída je velmi jednoduchá, je tvořena jednou tabulkou (třída QTableView), o jejíž funkčnost se stará datový model MatrixTableModel, který je popsán v kapitole 4.6. Stejně jako u předchozí třídy, je v konstruktoru nejprve načteno uživatelské rozhraní pomocí funkce setupUi(). Třída obsahuje funkci reloadData(), která slouží k načtení nových dat po zobrazení tohoto okna a také funkci changeSize(), která upraví velikost okna tak, aby odpovídala velikosti tabulky (a tedy velikosti matice). Pokud je ale tabulka větší než

20


rozměry obrazovky, je velikost okna nastavena tak, aby se na obrazovku vešlo celé a po jeho stranách se objeví posuvníky. Nakonec třída ještě obsahuje funkci accept(), která je volána po vybrání položky Uložit změny z hlavního menu. Tato funkce předá aktuální matici třídě MatrixGenerator pomocí funkce setMap() (matice je v programu reprezentována jako mapa). Tím se zajistí, že provedené změny budou v generátoru uloženy. V případě, že uživatel vybral z menu položku Zrušit, se žádná funkce nevykonává a okno je pouze skryto. Jak bylo uvedeno, při zobrazení okna se totiž vždy volá funkce reloadData(), takže bude znovu načtena původní (neupravená) matice a všechny změny tedy budou zrušeny (což jsme chtěli).

4.5

Třída ElementEditor

Tato třída reprezentuje okno, které zobrazuje matici jako seznam nenulových prvků. Obrázek tohoto okna a popis uživatelského rozhraní najdete v kapitole 3.4.3. Hlavní část této třídy je tvořena tabulkou QTableView, která využívá datový model ElementTableModel, popsaný v kapitole 4.7. Stejně jako u předchozí třídy, po zobrazení okna je volána funkce reloadData(), která se postará o aktualizaci dat. Dále tato třída obsahuje několik funkcí: • insertRow() — vložení nového prvku do tabulky, nejprve jsou přečteny zadané hodnoty ze vstupních polí a poté je zavolána funkce addRow() nacházející se v datovém modelu ElementTableModel, která se postará o vložení dat • deleteRows() — tato funkce naopak prvky z tabulky odstraňuje, nejprve jsou získány indexy všech vybraných řádků z tabulky a poté jsou tyto řádky odstraněny voláním funkce removeRows() datového modelu • updateSelection() — tato funkce přepíná stav tlačítka Smazat vybrané mezi aktivním a neaktivním podle toho, zda je vybrán některý řádek v tabulce nebo není Ukládání změn (funkce accept()) a jejich rušení probíhá naprosto stejně jako v předchozí třídě.

4.6

Třída MatrixTableModel

Tato třída je datovým modelem pro tabulku zobrazující matici ve standardním maticovém tvaru. Třída rozšiřuje (dědí) abstraktní třídu QAbstractTableModel a reimplementuje potřebné funkce tak, aby vykonávaly námi požadovanou činnost. Prvky matice jsou uloženy jako mapa (QMap), což je datová struktura, která obsahuje páry ve tvaru (klíč, hodnota). Aby byla možná spolupráce mezi tabulkou a datovým modelem, musí model reimplementovat několik standardních funkcí, pomocí kterých s ním tabulka komunikuje. Jedná se o tyto funkce: • rowCount() — vrací počet řádků, v tomto případě tedy výšku matice • columnCount() — počet sloupců, tedy šířka matice

4.7. TŘÍDA ELEMENTTABLEMODEL

21

• headerData(int section, Qt::Orientation orientation ) — tato funkce vrací data, která mají být zobrazena v záhlaví sloupců a řádků, má parametry orientation, který udává, zda se jedná o vertikální nebo horizontální záhlaví a section, který určuje řádek nebo sloupec • flags(QModelIndex & index ) — tato funkce vrací takzvané flagy (indikátory), které popisují vlastnosti buňky v tabulce (např. zda může být editována, vybrána apod.), konkrétní buňka je určena parametrem index. Jelikož prvky matice jsou editovatelné, tak v našem případě vrací metoda konstantu Qt::ItemIsEditable. • data(QModelIndex & index ) — touto funkcí získává tabulka vlastní data, která budou zobrazena v jednotlivých buňkách, v našem případě tedy hodnotu prvku matice, parametr index je instancí třídy QModelIndex, která je používána k určení pozice v tabulce (určuje řádek a sloupec, na kterém se nacházíme). Z parametru index si nejprve vypočítáme index prvku1 a poté se podíváme, zda mapa tento index obsahuje. Pokud ano, vrátíme hodnotu přiřazenou tomuto indexu, jinak vrátíme 0. V případě, že je matice symetrická, obsahuje mapa pouze prvky nacházející se na hlavní diagonále a pod ní, protože prvky nad hlavní diagonálou lze určit dle symetrie. V tomto případě je index prvku přepočítán vždy tak, aby ukazoval na symetrický prvek pod hlavní diagonálou a tento index je vyhledán v mapě. Tím je zajištěno, že tabulka zobrazuje správně i symetrické matice. • setData(QModelIndex & index, QVariant & value ) — tato funkce slouží k nastavení nové hodnoty v určité buňce tabulky. Pokud uživatel edituje nějakou buňku v tabulce, je po ukončení editace zavolána tato funkce s parametrem index určujícím konkrétní pozici a parametrem value, který obsahuje data zadaná uživatelem. Funkce musí provést aktualizaci základní datové struktury modelu (tedy v našem případě mapy prvků), aby se změny provedené uživatelem projevily. Nejprve je provedena kontrola správnosti zadaných dat, tedy např. že se jedná o číslo. Poté je stejně jako ve funkci data() vypočítán index prvku a do mapy je vložena dvojice (index, hodnota). Pokud je matice symetrická, je opět nejprve přepočítán index tak, aby ukazoval na symetrický prvek pod hlavní diagonálou a tento index je vložen do mapy. Nakonec je potřeba dát tabulce vědět, že byla změněna data, což je provedeno vyslání signálu dataChanged(index ), kde index označuje pozici změněného prvku. V případě symetrické matice je tento signál vyslán dvakrát, protože byly změněny dva prvky (nad a pod hlavní diagonálou).

4.7

Třída ElementTableModel

Tato třída tvoří datový model tabulky, která zobrazuje matici jako seznam nenulových prvků. Stejně jako předchozí model, i tato třída vznikla děděním z třídy QAbstractTableModel a reimplementací potřebných funkcí. Tabulka obsahuje 3 sloupce: 1. jednočíselný index 1

index je vypočítán podle rovnice „řádek × šířka matice + sloupec“

22


2. index ve tvaru (i,j) (tedy „řádek, sloupec“) 3. hodnotu prvku Oproti třídě MatrixTableModel je složitější, neboť počet řádků tabulky se mění v závislosti na tom, jak do matice postupně přidáváme prvky nebo je z ní odebíráme, zatímco v předchozím modelu byl rozměr tabulky stále stejný a měnila se pouze data v jednotlivých buňkách. Základem modelu je opět mapa (index, hodnota), pro správnou funkčnost však musely být provedeny určité změny a přidána další pomocná struktura. Tabulka totiž s datovým modelem komunikuje tak, že posílá pozici buňky v tabulce (tedy např. „1. řádek, 1. sloupec“ nebo „3. řádek, 2.sloupec“) a model musí vrátit odpovídající data. Mapa je ale asociativní kontejner, a proto se nedá určit, který její prvek je 1. nebo který je 5. Proto je nejprve provedena iterace přes celou mapu a každý index je vložen do seznamu (QList). Pokud je zpracovávaná matice symetrická, je za každý načtený prvek, nenacházející se na hlavní diagonále, vložen do seznamu ještě symetrický prvek na opačné straně diagonály, neboť mapa symetrické matice obsahuje pouze prvky pod hlavní diagonálou. Když chce poté tabulka prvek na 2. řádku, je vrácen 2. prvek seznamu. Při vkládání a mazání prvků je tedy potřeba tyto prvky vkládat nejen do mapy, ale i do tohoto seznamu indexů. Třída obsahuje privátní funkce checkIndex(), checkMatrixIndex() a checkValue(), sloužící ke kontrole dat zadaných uživatelem. Funkce checkIndex() kontroluje jednočíselný index a ověřuje např. to, zda uživatel zadal číselnou hodnotu a tato hodnota je platným indexem, to znamená od 1 do m × n (kde m a n jsou rozměry matice). CheckMatrixIndex() ověřuje index ve tvaru „řádek sloupec“, kontroluje tedy, že byla zadána dvě čísla oddělená mezerou a příslušná hodnota není větší než počet řádků, respektive sloupců. Poslední funkce, checkValue(), ověřuje hodnotu prvku matice. Funkce zajišťuje, aby nebyla porušena nastavení generátoru matic, je tedy odmítnuto záporné číslo, pokud byla nastavena pouze kladná, nebo je odmítnuto desetinné číslo, pokud jsou nastavena pouze celá čísla. Jména funkcí, pomocí nichž tabulka s modelem komunikuje, jsou stejná jako v předchozím případě, jejich implementace se ale samozřejmě liší: • rowCount() — počet řádků je takový, jako je velikost seznamu indexů • columnCount() — počet sloupců je v tomto případě konstantní (3) • headerData(int section, Qt::Orientation orientation ) — tato tabulka obsahuje pouze horizontální záhlaví, pro příslušné sekce tedy funkce vrací popisky „index“, „(i,j)“ a „hodnota“ • flags(QModelIndex & index ) — implementace této funkce je naprosto stejná jako v předchozím modelu, všechny buňky jsou editovatelné • data(QModelIndex & index ) — nejprve si zjistíme, na jaký řádek ukazuje parametr index a pak ze seznamu indexů přečteme prvek na příslušné pozici. Poté se rozhodujeme podle toho, o jaký se jedná sloupec tabulky. Pokud je to 1. sloupec, rovnou vrátíme tento přečtený index. Pokud se nacházíme ve 2. sloupci tabulky, přepočítáme index do tvaru „(i,j)“, tedy „(řádek, sloupec)“. V případě 3. sloupce tabulky vyhledáme v mapě hodnotu prvku příslušící tomuto indexu a tu vrátíme. Pokud je zobrazena symetrická

4.7. TŘÍDA ELEMENTTABLEMODEL

23

matice, tak provádíme stejně jako v předchozím modelu nejprve přepočítání indexů tak, aby ukazoval na prvek nacházející se pod hlavní diagonálou. • setData(QModelIndex & index, QVariant & value ) — touto funkcí se mění data v jednotlivých buňkách tabulky. V porovnání s předchozím modelem je mnohem složitější, neboť je možné změnit nejen hodnotu prvku matice, ale také index, a tím tedy přesunout prvek na jinou pozici. To vyžaduje provádět kontrolu většího množství podmínek a případně provádět manipulaci s daty. Algoritmus se větví podle sloupce tabulky, kde je prováděna změna. Pokud se mění 1. sloupec tabulky, jde o změnu indexu prvku. Nejprve se zavolá funkce checkIndex() a poté se provede kontrola, zda se tento index již v seznamu nenachází. Pokud některá z kontrol dopadne špatně, vrátí funkce false, čímž se změny odmítnou a tabulka bude obsahovat stejná data jako před editací. V opačném případě přečteme z mapy hodnotu příslušící původnímu indexu, tento index z mapy vymažeme a do mapy vložíme nový index zadaný uživatelem, kterému přiřadíme přečtenou hodnotu. Také v seznamu indexů nahradíme prvek na pozici určené aktuálním řádkem v tabulce novým indexem. Složitější je situace v případě změny indexu prvku v symetrické matici, v určitých případech totiž může dojít ke změně počtu řádků v tabulce. Pokud změníme index prvku nacházejícího se na hlavní diagonále na index, který se na hlavní diagonále nenachází, musíme do tabulky vložit i symetrický prvek na opačné straně diagonály, a tím se zvýší počet řádků v tabulce o jeden. Podobná je situace v opačném případě, kdy změníme index nediagonálního prvku na diagonální – z tabulky musíme odstranit i symetrický prvek a počet řádků se tedy o jeden sníží. Pokud měníme druhý sloupec tabulky, tedy index ve tvaru „(i,j)“, jsou nejprve ověřena data pomocí funkce checkMatrixIndex() a poté takto zadaný index přepočítáme na jednočíselný index. Dále probíhá algoritmus zcela stejně jako v případě změny 1. sloupce tabulky. V případě změny ve třetím sloupci tabulky jde o změnu hodnoty prvku. Znovu se nejprve provede kontrola uživatelem zadaných dat pomocí funkce checkValue(), podle řádku tabulky, na kterém se právě nacházíme, zjistíme ze seznamu indexů index měněného prvku a do mapy vložíme tento index spolu s novou hodnotou prvku matice. Starý prvek není potřeba z mapy odstraňovat, protože mapa v defaultním nastavení může obsahovat pouze jeden prvek se stejným klíčem, tudíž ten starý bude automaticky smazán. Kromě těchto funkcí obsahuje ElementTableModel navíc ještě funkce umožňující vkládat a odebírat řádky tabulky, které ve třídě MatrixTableModel nebyly potřeba. • removeRows(int position, int rows ) — tato funkce slouží k odstranění řádků z tabulky, počet řádků je určen parametrem rows a pozici, kde se mají řádky odstranit, udává parametr position. Nejprve je zavolána funkce beginRemoveRows()2 , která upozorňuje tabulku, že dojde k odstranění řádků. To je potřeba z toho důvodu, aby po 2 Funkce beginRemoveRows(), stejně jako funkce endRemoveRows(), je součástí třídy QAbstractItemModel. Každá třída, která reimplementuje funkce pro odstraňování řádků z tabulky, musí tyto funkce volat před začátkem mazání, respektive po jeho dokončení.

24


odstranění řádků nebyla tabulka v nekonzistentním stavu. Poté se odstraní příslušné indexy ze seznamu indexů a zároveň se tyto indexy vymažou také z mapy prvků matice. Nakonec je zavolána funkce endRemoveRows(), která tabulce oznámí, že mazání řádků bylo dokončeno. Po smazání prvků se též zkontroluje, zda je matice prázdná a pokud ano, je vyslán signál matrixEmpty(). Tento signál je připojen ke tlačítku Smazat všechny nacházejícímu se ve třídě ElementEditor a určuje, zda je tlačítko stisknutelné. Pokud je matice prázdná, je toto tlačítko neaktivní. • deleteAll() — tato funkce není standardní funkcí rozhraní datového modelu, ale vytvořil jsem ji za účelem smazání celého obsahu tabulky. Tato funkce je provedena, pokud uživatel stiskne tlačítko Smazat všechny v okně editoru matic. Na začátku je zavolána funkce beginResetModel(), která dává tabulce vědět, že dojde k zásadní změně datového modelu. Poté se provede vymazání všech prvků ze seznamu indexů a z mapy pomocí metody clear() tříd QList a QMap. Nakonec se zavolá funkce endResetModel(), která informuje tabulku, že resetování modelu bylo dokončeno a tabulka si poté znovu načte všechna data. Důvodem k vytvoření této funkce bylo to, že mazání tímto způsobem je mnohem rychlejší, než kdyby byly řádky odstraňovány jednotlivě pomocí funkce removeRows(). Ke vkládání řádků do tabulky se běžně používá funkce insertRows(), která do tabulky vloží prázdný řádek. V našem případě ale vždy vkládáme do tabulky již existující data načtená ze vstupních políček v okně editoru matice a bylo by zbytečné nejprve vložit prázdný řádek a teprve potom měnit hodnoty buněk v tomto řádku. Proto jsem vytvořil svou vlastní funkci addRow(), která rovnou vloží do tabulky řádek obsahující příslušná data. • addRow(QVariant & index, QVariant & matIndex, QVariant & value ) — parametry této funkce jsou získány z obsahu vstupních políček v okně editoru matice, funkce je zavolána při stisknutí tlačítka Vložit. QVariant je třída, která funguje jako unie různých datových typů. Může v sobě obsahovat např. hodnotu typu int, double, string apod. To ulehčuje práci s různými typy hodnot, protože není nutné vytvářet více funkcí lišících se typem parametrů a různé hodnoty můžeme reprezentovat jednou proměnnou. Hodnotu prostého typu získáme z této třídy zavoláním příslušné funkce, jako je např. toInt(), toDouble() atd. Pomocí nám již známých funkcí checkIndex(), checkMatrixIndex() a checkValue() se provede kontrola zadaných dat. Také se ověří, že jednočíselný index odpovídá indexu ve tvaru (i,j) (pokud uživatel zadal oba) a že se tento index ještě v tabulce nenachází. Poté se zavolá funkce beginInsertRows(), která upozorní tabulku, že bude vložen nový řádek. Index je vždy vložen na počátek seznamu indexů a zároveň je do mapy vložena dvojice (index, hodnota). Nakonec je zavolána funkce endInsertRows() a tím je vkládání řádků dokončeno. V případě symetrické matice je situace opět o trochu složitější, neboť si musíme zjistit, zda se vkládaný prvek nachází na hlavní diagonále. Pokud ano, proběhne vložení prvku stejně jako bylo popsáno, v opačném případě jsou do seznamu vloženy dva prvky (nejprve ten pod diagonálou a za něj symetrický prvek na opačné straně). Do mapy je vložen pouze prvek nacházející se pod hlavní diagonálou.

4.8. TŘÍDA MATRIXGENERATOR

4.8

25

Třída MatrixGenerator

Tato třída tvoří jádro celé aplikace. Jejím hlavním účelem je provádět generování matic podle zadaných parametrů. Jak již bylo uvedeno v úvodu do implementace (kapitola 4.1, strana 17), součástí této třídy je instance mapy (třída QMap), která v programu reprezentuje matici. Třída obsahuje několik privátních proměnných, v nichž je uloženo nastavení generátoru a ke každé z nich poskytuje přístupové funkce setProměnná() a getProměnná(), kterými je možno tyto proměnné nastavit a přečíst. Konkrétně se jedná o tyto funkce: • setHeight(int h ) — nastavuje výšku matice • setWidth(int w ) — šířka matice • setMaxValue(int max ) — maximální hodnota prvku matice • setNumberOfElements(int num ) — počet nenulových prvků • setSigned(bool b ) — nastavuje, zda prvky matice mohou být kladné i záporné (true), nebo pouze kladné (false) • setValueType(Matrix::ValueType vt ) – ValueType je výčtový typ definovaný ve třídě Matrix (viz kapitola 4.10), nastavuje, zda hodnoty prvků jsou celá čísla (Int), nebo desetinná (Double) • setMatrixType(MatrixType mt ) – MatrixType je výčtový typ definující konstanty pro různé typy matic, a to Singular (singulární matice), Regular (regulární), UpDiagonal (horní trojúhelníková), DownDiagonal (dolní trojúhelníková), Banded (pásová), Symmetric (symetrická) a Normal (běžná matice, nepatřící do žádné z předchozích kategorií) Pro nastavení pásových matic jsou definovány ještě následující dvě funkce: • setUpperBand(int band ) — šířka naddiagonálního pásu • setLowerBand(int band ) — šířka poddiagonálního pásu Aby nebylo nutné nastavovat každou proměnnou zvlášť, obsahuje generátor ještě funkci setOptions(int width, int height, int numElements, int maxValue, bool sign, Matrix::ValueType values ), která nastaví všechny parametry generátoru najednou. Tato funkce je volána třídou MainWindow vždy před zobrazením okna editoru matic a před začátkem generování nové matice. Kromě nastavení vnitřních proměnných provádí tato funkce ještě aktualizaci mapy tak, aby odpovídala novému nastavení generátoru. Konkrétně se jedná o tyto změny: • pokud se rozměry matice změnily, je provedeno přepočítání indexů a prvky, které překračují rozsah indexů jsou odstraněny • pokud byl změněn typ hodnoty prvků z desetinných čísel na celá čísla, jsou hodnoty prvků zaokrouhleny na celá čísla

26


• pokud byla změněna maximální hodnota prvku, jsou odstraněny všechny prvky, které mají větší hodnotu • pokud byl typ hodnot změněn z „kladná i záporná“ na „pouze kladná“, jsou odstraněny všechny záporné prvky • pokud byl snížen počet nenulových prvků a matice jich obsahuje více, jsou všechny přebývající prvky odstraněny Hlavním úkolem této třídy je generování různých typů matic. Hlavní okno vždy volá funkci generate(), která se větví podle nastaveného typu matice. Algoritmy pro generování jednotlivých typů matic budou nyní detailně popsány.

4.8.1

Generování singulárních matic

Singulární matice je taková čtvercová matice, jejíž řádky (či sloupce) nejsou lineárně nezávislé. Algoritmus pro vytvoření singulární matice se liší podle zaplnění matice nenulovými prvky. Pokud je zaplnění menší než 20%, je singulární matice vytvořena tím způsobem, že některý řádek (nebo sloupec) obsahuje samé nuly a nenulové prvky jsou náhodně rozmístěny v ostatních řádcích. Matice, ve které se nachází alespoň jeden řádek obsahující samé nuly, je totiž vždy singulární. V případě, že je zaplnění matice větší, působilo by nepřirozeně, kdyby některý řádek obsahoval pouze nuly, zatímco ostatní řádky by byly poměrně hustě obsazené. Z tohoto důvodu je použit jiný algoritmus, a to takový, že náhodně vygenerujeme hodnoty dvou řádků a třetí řádek se vytvoří jako jejich součet. Tím je zajištěno, že jsou tyto řádky lineárně závislé. Zbývající řádky matice jsou pak vyplněny náhodně. Pozor se musí dávat na to, aby žádná hodnota prvku v řádku, který je součtem dvou jiných řádků, nepřekročila maximum nastavené uživatelem. Tomu je zabráněno tím, že v prvních dvou řádcích jsou generovány prvky o velikosti nanejvýš poloviny maxima. Uvedený algoritmus by nefungoval správně v případě, že je generátor nastaven tak, aby generoval celá čísla s maximální hodnotou 1, nebo pokud je šířka (a tedy i výška) matice menší nebo rovna 3. Tyto speciální případy jsou ošetřeny zvlášť. Pro snadnější pochopení si ukážeme vývojový diagram popisovaného algoritmu (obrázek A.1 na straně 36). Popis vývojového diagramu Myslím, že většina algoritmu je z diagramu snadno pochopitelná, proto budou popsány pouze kroky označené v diagramu písmeny A) a B): A) seznam indexů obsahuje čísla od 0 do maximálního indexu (šířka × výška − 1). Z tohoto seznamu jsou náhodně vybírána jednotlivá čísla, která poté určují pozici prvku v matici. Pokud nechceme, aby se na nějakém řádku matice nacházely prvky, stačí indexy všech prvků z tohoto řádku odstranit ze seznamu.

4.8. TŘÍDA MATRIXGENERATOR

27

B) hodnoty ve třetím poli vznikají jako součet hodnot prvních dvou polí a může se stát, že výsledkem součtu bude číslo 0 (např. pokud je v prvním poli hodnota -2 a ve druhém 2). V určitém případě by mohla tato situace znemožnit vytvoření matice podle uživatelových požadavků. Uvažujme, že uživatel bude chtít vygenerovat matici o rozměru 5 × 5 s 25 nenulovými prvky. Pokud by pak na nějaké pozici byla součtem 0, nebylo by možné splnit požadavek na 25 nenulových prvků. Z tohoto důvodu je ověřováno, že počet nulových prvků ve třetím poli nepřekračuje maximum, a pokud ano, je tento prvek nahrazen jedničkou a hodnota na odpovídající pozici 1. nebo 2. pole je zvětšena o 1. 4.8.1.1

Speciální případy singulárních matic

Jak bylo řečeno, pro některé typy matic by předešlý algoritmus nebyl funkční a bylo proto nutné tyto případy speciálně ošetřit. Pokud je generátor nastaven na generování celých čísel a maximální hodnota prvku je 1, není možné použít předešlý algoritmus, protože při vyplňování prvních dvou polí (která pak budou sečtena) se používají pouze čísla větší než 0 a menší než polovina maximální hodnoty. Žádné celé číslo větší než 0 a menší než 12 však neexistuje. Proto je použit jiný algoritmus, který vytvoří v matici dva stejné řádky, čímž se matice stane singulární. Nejprve je vytvořeno pole, do kterého je na náhodné pozice umístěn určitý počet jedniček. Toto pole je poté vloženo na dva náhodně vybrané řádky matice. Indexy těchto řádků jsou odstraněny ze seznamu indexů a zbývající prvky se vyberou ze zbylých prvků v seznamu. Pokud je rozměr matice 3 × 3, je nejprve vytvořen jeden řádek, druhý je jeho dvojnásobkem a poslední řádek je vyplněn náhodně. U matic rozměru 2 × 2 se podle počtu nenulových prvků pouze zvolí jejich vhodné rozmístění tak, aby vznikla singulární matice. Jedinou výjimkou je matice rozměru 2 × 2 se třemi nenulovými prvky, která nemůže být nikdy singulární. V tomto případě program pouze zobrazí informační okno o nemožnosti vytvoření požadované matice.

4.8.2

Generování regulárních matic

Zatímco generování singulárních matic probíhalo tak, že algoritmus záměrně vytvořil několik lineárně závislých řádků, čímž bylo zajištěno, že vzniklá matice je singulární, generování regulárních matic probíhá jinak. Algoritmus vychází z toho, že singulární matice jsou velmi vzácné, to znamená, že když vytvoříme náhodnou matici, téměř vždy bude regulární. Jako první krok algoritmus vytvoří tolik prvků, jako je šířka matice, a rozmístí je takovým způsobem, aby žádný řádek ani sloupec nebyl prázdný. Matice, která by obsahovala nějaký sloupec či řádek tvořený samými nulami, by totiž byla singulární. Po tomto kroku jsou už zbylé prvky rozmístěny zcela náhodně. Ačkoliv platí, že náhodně vybraná matice je téměř vždy regulární, určitá malá pravděpodobnost, že vznikla singulární matice, přece jenom existuje. Proto je po vygenerování matice provedena gaussova eliminace3 , čímž se s jistotou určí, že matice je skutečně regulární. Pokud matice regulární není, tak se celé generování opakuje od začátku. V případě, že by se ani po 3

algoritmus pro výpočet gaussovy eliminace je vytvořen podle pseudokódu nacházejícího se v [4]

28


5 pokusech nepodařilo vygenerovat regulární matici, je zobrazeno okno informující uživatele o nezdaru a algoritmus je ukončen. Při testování se potvrdilo, že téměř vždy je regulární matice vygenerována hned prvním pokusem. Jediným problémem je případ, kdy je nastavena maximální hodnota prvku na 1 (matice tedy obsahuje pouze jedničky a nuly) a matice je hustě zaplněna. V takovém případě existuje pouze malé množství kombinací jednotlivých prvků tak, aby matice nebyla singulární, a programu se většinou během 5 pokusů nepodaří vygenerovat regulární matici, takže generování skončí neúspěchem. Ve všech ostatních případech probíhá generování bez problémů. Průběh celého algoritmu je opět zachycen na vývojovém diagramu (obrázek A.2, strana 37).

4.8.3

Generování symetrických matic

Algoritmus pro generování symetrických matic je v zásadě velmi jednoduchý. Jak bylo již řečeno, mapa symetrické matice obsahuje pouze prvky nacházející se na hlavní diagonále nebo pod ní. Nejprve je vytvořen seznam indexů prvků, které je možno vložit do mapy, poté je tento seznam náhodně promíchán a nakonec jsou z něj postupně vybírány prvky a vkládány do mapy. Pozor se musí dát pouze na to, aby nebyl překročen počet nenulových prvků zadaný uživatelem. To znamená, že pokud už zbývá do matice vložit jen jeden prvek, musí to být prvek na hlavní diagonále, protože v případě prvku, který se na hlavní diagonále nenachází, by poté matice obsahovala i symetrický prvek na druhé straně diagonály. Stejně tak není možné vložit do matice poslední zbývající diagonální prvek, pokud zbývá vložit ještě sudý počet prvků (po jeho vložení by zbýval lichý počet, čehož by nebylo možné dosáhnout, neboť nediagonální prvky se vlastně vkládají po dvou). Celý průběh algoritmu je pro názornost opět ukázán na vývojovém diagramu (obrázek A.3 na straně 38).

4.8.4

Generování ostatních typů matic

Postup generování ostatních typů matic (horní trojúhelníková, dolní trojúhelníková, pásová a obyčejná) je do značné míry stejný. Nejprve je vytvořen seznam indexů, který je naplněn příslušnými indexy v závislosti na typu matice a poté je z tohoto seznamu náhodně vybrán zadaný počet prvků. Každý vybraný prvek je vložen do mapy, reprezentující v programu matici. Tím je generování ukončeno. Odlišný postup je použit pouze u obyčejných matic, jejichž zaplnění nenulovými prvky je menší než 50%. V tomto případě se nevytváří seznam všech indexů, čímž se ušetří nějaký čas, ale rovnou je náhodně generován index prvku a před jeho vložením se kontroluje, zda se již tento index v mapě nenachází. U matic s vyšším zaplněním by se stávalo příliš často, že bude vygenerován index, který se již v matici nachází, a proto je použit postup využívající seznam indexů. Vývojový diagram je v tomto případě velice jednoduchý. Prohlédnout si ho můžete na obrázku A.4 na straně 39.

4.9. TŘÍDA MATRIXMARKETIO

4.8.5

29

Optimalizování generovacích algoritmů

Po implementaci první verze uvedených algoritmů jsem provedl otestování výkonu. Rozhodl jsem se vyzkoušet rychlost vygenerování singulární matice s maximálními parametry – to znamená o rozměru 1000 × 1000 obsahující 1 milion nenulových prvků. Vykonání celého algoritmu trvalo přibližně 2 minuty a 19 sekund. S tímto časem jsem nebyl spokojen a proto jsem se pokusil najít způsob, jak proces generování zrychlit. Jak bylo již dříve popsáno, algoritmus pracuje tak, že si vytvoří seznam všech přípustných indexů (v tomto případě obsahující milion prvků) a z něj náhodně vybírá jednotlivé prvky a vkládá je do matice. V první verzi to probíhalo tak, že bylo vygenerováno náhodné číslo mezi 0 a velikostí seznamu a prvek na této pozici byl ze seznamu odstraněn, aby již nemohl být znovu vybrán. Problém byl v tom, že třída QList (pomocí níž je implementován seznam indexů) je vnitřně reprezentována jako pole a když jsme tedy smazali prvek z prostředku tohoto pole, všechny následující prvky musely být zkopírovány o jedno místo dopředu. To samozřejmě velmi zpomalovalo celý algoritmus. Proto byl použit jiný způsob, a to ten, že po vytvoření seznamu indexů je tento seznam náhodně promíchán pomocí STL4 funkce random_shuffle(). Složitost této funkce je lineární (provede se tolik prohození prvků jako je velikost pole). Poté už stačí pouze postupně projít seznam od začátku do konce, žádné prvky z něj není nutné mazat. Po provedení této úpravy se běh algoritmu zrychlil na přibližně 45 s. Ani tento algoritmus však ještě nebyl optimální. Jak je popsáno v kapitole o generování singulárních matic, jsou nejprve vytvořeny tři lineárně závislé řádky a ty jsou potom vloženy na náhodné řádky matice. Indexy prvků nacházejících se na těchto řádcích je pak samozřejmě potřeba odstranit ze seznamu indexů, aby nemohly být vybrány při zaplňování zbylých řádků matice. Toto mazání prvků ze seznamu ovšem opět působilo stejné potíže, jaké byly popsány v předchozím odstavci. Proto byl použit jiný postup – místo mazání ze seznamu jsou prvky vkládány do množiny již použitých prvků (třída QSet). Třída QSet byla zvolena z toho důvodu, že umožňuje velice rychle vyhledat, zda se v ní nachází konkrétní prvek (průměrná složitost tohoto vyhledání se blíží konstantní složitosti), což je vlastnost, na které nám nejvíce záleží. Při procházení seznamu indexů se poté u každého přečteného prvku nejprve kontroluje, zda se nenachází v této množině již použitých prvků a pokud ne, je vložen do matice. Po této optimalizaci trvá vytvoření singulární matice s 1 milionem prvků přibližně 3,5 s. Jak tedy můžete vidět, díky těmto úpravám se běh algoritmu zrychlil asi 40×. Uvedené optimalizace jsou použity nejen při generování singulárních matic, ale ve všech algoritmech, které pracují se seznamem indexů. Doba trvání algoritmu byla měřena na mém počítači a na jiném stroji se samozřejmě bude lišit, byla ale uvedena z toho důvodu, aby bylo vidět, v jaké míře se zrychlil průběh generování.

4.9

Třída MatrixMarketIO

Tato třída umožňuje vstup a výstup do souboru ve formátu MatrixMarket. Obsahuje dvě statické funkce open() a save(), které dělají to, co jejich název napovídá. Načtenou, respek4 STL je zkratka Standard Template Library. Jedná se o standardní knihovnu šablon v jazyce C++, která obsahuje šablony běžně používaných tříd, jako jsou např. datové kontejnery. Stejně tak obsahuje i šablony standardních algoritmů, které s těmito třídami pracují.

30


tive ukládanou matici reprezentuje třída Matrix, která je popsána v následující kapitole. Ve třídě jsou využívány funkce z knihovny pro MatrixMarket I/O z oficiálních stránek projektu Matrix Market5 . Jelikož je tato knihovna napsána v ANSI C (nikoliv C++), jsou pro vstup a výstup využívány funkce fprintf() a fscanf(). • Matrix open() — tato funkce načte matici ze souboru a vrátí ji jako instanci třídy Matrix. Funkce nejprve zobrazí dialog pro výběr souboru a poté se pokusí načíst jeho obsah, pokud není možné soubor otevřít nebo obsahuje data v nesprávném formátu, je o tom informován uživatel. • bool save(Matrix m ) — slouží k uložení matice do souboru. Matice je funkci předána jako parametr. Nejprve je zobrazen dialog pro výběr souboru a pak je proveden zápis. V případě úspěchu vrací funkce true, jinak false.

4.10

Třída Matrix

Třída Matrix reprezentuje matici a je využívána třídou MatrixMarketIO při vstupu a výstupu. Ve třídě se nachází několik proměnných popisujících matici – šířka, výška, typ hodnot (integer nebo real), typ matice (symetrická nebo obyčejná) a mapa obsahující vlastní prvky matice. Součástí třídy je také proměnná valid typu bool, která určuje, zda je matice platná nebo není. Pokud dojde při načítání matice ze souboru k chybě, je tato proměnná nastavená na false a ostatní třídy tak poznají, že nebyla načtena žádná matice. Celá třída je velmi jednoduchá a kromě funkcí, které nabízejí přístup k jednotlivým proměnným, obsahuje již jen dva konstruktory. Jeden bez parametrů, který pouze nastaví proměnnou valid na false. Tento konstruktor se používá k vytvoření neplatné matice, pokud při načítání souboru dojde k chybě. Druhý konstruktor nastaví všechny proměnné podle zadaných parametrů a používá se k vytvoření kompletní matice.

5

Kapitola 5

Závěr Práce na tomto projektu byla pro mě velice přínosná hned z několika pohledů. Zlepšil jsem svoje znalosti jazyka C++ a získal více zkušeností s tvorbou rozsáhlejší aplikace s grafickým uživatelským rozhraním, neboť dříve jsem programoval především aplikace s výstupem na konzoli. Tvorba GUI pomocí knihovny Qt je skutečně velmi snadná a v budoucnu ji jistě využiji v dalších projektech. Stejně tak jsem se mohl přesvědčit, jaký vliv má volba vhodné datové struktury na rychlost algoritmu a poznal jsem, že vymyslet vhodnou architekturu aplikace a jednotlivých tříd tak, aby jejich vzájemná spoupráce byla efektivní, dá někdy více práce a zabere více času, než jejich samotné naprogramování. Celkově jsem s výsledkem práce spokojen. Podařilo se mi splnit všechny zadané cíle a vytvořit program, který považuji za snadno ovladatelný a který poskytuje možnost nastavit mnoho parametrů podle přání uživatele, čímž umožňuje generovat nejrůznější typy matic.

31

32

KAPITOLA 5. ZÁVĚR

Literatura [1] BOISVERT, R. F. – POZO, R. – REMINGTON, K. A. The Matrix Market Exchange Formats: Initial Design. National Institute of Standards and Technology, Gaithersburg, MD 20899 USA, 1996. Dostupné z: . [2] Nokia Corporation. Qt Reference Documentation [online]. 2010. [cit. 4. 1. 2011]. Dostupné z: . [3] Přispěvatelé Wikipedie. Band matrix [online]. 2010. [cit. 1. 1. 2011]. Dostupné z: . [4] Přispěvatelé Wikipedie. Gaussian elimination [online]. 2011. [cit. 3. 1. 2011]. Dostupné z: . [5] Přispěvatelé Wikipedie. Matrix (mathematics) [online]. 2010. [cit. 1. 1. 2011]. Dostupné z: . [6] Přispěvatelé Wikipedie. Transpose [online]. 2010. [cit. 1. 1. 2011]. Dostupné z: . [7] Přispěvatelé Wikipedie. Triangular matrix [online]. 2010. [cit. 1. 1. 2011]. Dostupné z: .

33

34

LITERATURA

Příloha A

Vývojové diagramy V této příloze se nacházejí vývojové diagramy popisující algoritmy využívané pro generování různých typů matic. Původně jsem je zamýšlel umístit přímo do hlavního textu do příslušných sekcí zabývajících se generováním různých typů matic, ale systém LATEX, kterým je tato práce vysázena, pro ně nenašel vhodné místo a vysázel je všechny najednou až na konci kapitoly. Problémem byla velikost diagramů, které většinou zabírají celou stránku. Bylo by je sice možné zmenšit, ale s ohledem na zachování čitelnosti by to nebylo příliš vhodné. Proto jsem se je rozhodl umístit do této přílohy, což považuji za přehlednější, než kdyby se nacházely na konci kapitoly.

35

36

PŘÍLOHA A. VÝVOJOVÉ DIAGRAMY

start

ano

šířka matice < 4 nebo maximální hodnota prvku rovna 1?

speciální případ, ošetřen zvlášť

konec

ne

A)

ano

vytvoř seznam indexů

je zaplnění matice menší než 20%

ne

spočti počet prvků na jeden řádek vyber náhodný řádek vytvoř 3 pole o velikosti šířky matice indexy tohoto řádku odstraň ze seznamu indexů

do dvou z nich vlož na náhodné pozice spočtený počet prvků, třetí pole vznikne jejich součtem

potřebný počet prvků vyber náhodně ze seznamu indexů

B)

je počet nul ve třetím poli větší než maximum?

ano

konec potřebný počet nul nahraď jedničkou, hodnotu na odpovídající pozici v 1. poli zvětši o 1

ne

hodnoty z polí umísti na 3 náhodně vybrané řádky v matici

indexy těchto řádků odstraň ze seznamu indexů

zbývající prvky vyber náhodně ze seznamu indexů

konec

Obrázek A.1: Vývojový diagram algoritmu pro generování singulárních matic

37

start

rozmísti tolik prvků, jako je šířka matice, tak, aby žádný řádek ani sloupec nebyl prázdný

zbývající prvky rozmísti v matici náhodně

vymaž obsah matice proveď gaussovu eliminaci ne ne je matice regulární?

ano

konec

jedná se již o pátý neúspěšný pokus? ano vypiš informaci o neúspěchu při generování regulární matice

konec

Obrázek A.2: Vývojový diagram algoritmu pro generování regulárních matic

38


start

vytvoř seznam indexů prvků, nacházejících se na hlavní diagonále nebo pod ní

náhodně promíchej tento seznam

počet = 0

je počet < limit nastavený uživatelem ?

ne konec

ano vyjmi jeden prvek ze seznamu

ano

ne leží na hlavní diagonále?

je poslední diagonální a zbývá vložit ještě sudý počet prvků? ano

přeskoč prvek

ne

zbývá vložit už jen jeden prvek? ano

vlož prvek do matice

ne

vlož prvek do matice

přeskoč prvek počet += 2

počet += 1

Obrázek A.3: Vývojový diagram algoritmu pro generování symetrických matic

39

start

vytvoř sezam indexů, který obsahuje možné indexy prvků v závislosti na typu matice

z tohoto seznamu náhodně vyber zadaný počet prvků a vlož je do matice

konec

Obrázek A.4: Vývojový diagram algoritmu pro generování ostatních typů matic

40


Příloha B

Instalační a uživatelská příručka B.1 B.1.1

Instalační příručka Instalace pro operační systém Microsoft Windows

Program byl testován a je funkční na systémech Windows XP, Windows Vista a Windows 7. Instalace je velice jednoduchá, stačí pouze rozbalit přiložený archiv do libovolné složky. Pozor! Všechny přiložené knihovny (soubory .dll) musí zůstat ve stejné složce jako spustitelný soubor, jsou vyžadovány pro běh programu. Program poté spustíte dvojitým kliknutím na soubor matrix.exe.

B.1.2

Kompilace programu pod ostatními operačními systémy

Přiložený zkompilovaný program využívá nativní funkce systému Windows, takže ho není možné spustit na jiných operačních systémech. Aby bylo možné program spustit na jiném OS, je nutné ho pod tímto OS zkompilovat. Pokud si chcete program zkompilovat sami, můžete následovat tento postup: 1. Budete potřebovat knihovnu Qt, kterou aplikace využívá. Můžete si ji stáhnout z . 2. Staženou knihovnu si nainstalujte. Popis instalace naleznete zde . 3. Rozbalte zdrojové kódy programu do libovolné složky a přepněte se do složky, kde se nachází soubor matrix.pro (soubor projektu). 4. Napište do příkazové řádky příkaz qmake. Měl by se vytvořit soubor Makefile. 5. Nakonec příkazem make program zkompilujte (pokud používáte jiný kompilátor, použijte příslušný program na zpracování Makefilů). 6. Výsledný program se nachází ve složce release.

41

42

PŘÍLOHA B. INSTALAČNÍ A UŽIVATELSKÁ PŘÍRUČKA

B.2 B.2.1

Uživatelský manuál Postup generování matice

1. Po spuštění programu se zobrazí hlavní okno, kde můžete nastavit parametry generované matice. Můžete změnit její rozměry, počet nenulových prvků a typ hodnot. V pravé části okna se nachází přepínače, pomocí nichž můžete vybrat některý speciální typ matice. 2. V dolní části okna se nachází dvě tlačítka, pomocí nichž můžete provést pokročilé nastavení prvků matice. Postup je podrobně popsán v sekci B.2.2. Toto pokročilé nastavení není přístupné, pokud je vybrán některý ze speciálních typů matice. 3. Generování matice se spustí tlačítkem Generovat. 4. Pokud generování proběhlo v pořádku, je zobrazena záložka Editace. Zde můžete zobrazit vygenerovanou matici buď ve standardní podobě jako tabulku, nebo jako seznam indexů. Takto zobrazenou matici můžete podle potřeby editovat. 5. Uložení matice do souboru provedete stisknutím tlačítka Uložit na záložce Editace nebo vybráním příslušné položky v menu Soubor. Zobrazí se standardní systémové okno pro výběr výstupního souboru a poté bude matice uložena.

B.2.2

Pokročilé nastavení generování

Zde můžete nastavit hodnoty konkrétním prvkům matice. Při vytváření matice budou poté tyto hodnoty zachovány a vygenerovány budou pouze hodnoty zbývajících prvků. Toto nastavení můžete provést dvěma způsoby – buď můžete zobrazit matici v běžné podobě (stisknutím tlačítka Zobrazit matici. . . ), nebo ji můžete zobrazit jako seznam nenulových prvků (pomocí tlačítka Nastavit prvky. . . ). Zobrazení ve formě tabulky V tomto okně je matice zobrazena jako tabulka a v každém políčku se nachází hodnota příslušného prvku matice. Jednotlivá políčka tabulky můžete běžným způsobem editovat. Uložení všech změn a návrat do hlavního okna generátoru se provede výběrem položky Uložit změny z menu Soubor. Matici v aktuální podobě můžete také rovnou uložit na disk výběrem příslušné položky v hlavním menu. Zobrazení ve formě seznamu nenulových prvků V tomto okně jsou vypsány pouze nenulové prvky nacházející se v matici. V levé části okna se nachází seznam prvků, na každém řádku je vedle sebe zobrazen index prvku a hodnota prvku nalézajícího se na tomto indexu. Prvky do matice vkládáte pomocí vstupních polí v horní části okna tak, že vyplníte index a hodnotu prvku a stisknete tlačítko Vložit. Pokud hodnotu nevyplníte, bude do seznamu vložen pouze index a hodnota zůstane prázdná. Hodnota prvku bude v tom případě vygenerována programem při vytváření matice.

B.2. UŽIVATELSKÝ MANUÁL

43

Položky v seznamu jsou editovatelné – můžete měnit index prvku nebo jeho hodnotu. Pod seznamem prvků se nachází dvě tlačítka, pomocí nichž můžete smazat vybrané položky nebo celý seznam. Uložení změn provedete stisknutím tlačítka Hotovo. Tlačítkem Zrušit budou všechny změny zrušeny a vrátíte se do hlavního okna programu.

B.2.3

Načítání matice

Matice uložené na disku můžete otevřít a editovat. 1. Načtení uložené matice provedete pomocí menu Soubor→Otevřít. . . 2. Pokud proběhne načítání úspěšně, bude zobrazena záložka Editace, kde můžete matici zobrazit a upravovat.

44

PŘÍLOHA B. INSTALAČNÍ A UŽIVATELSKÁ PŘÍRUČKA

Příloha C

Obsah přiloženého CD | README.txt | +---program | +---exe | \---source | \---text | generator.pdf | \---source

\\ popis obsahu CD a popis instalace

\\ složka se zkompilovaným programem \\ složka se zdrojovými kódy programu

\\ text bakalářské práce v PDF formátu \\ složka se zdrojovým textem BP v LaTeXu

45

Generátor řídkých matic. Kamil Šnajdr

Recommend Documents