Cvičení 5: 2D pole

• Nedokončený příklad z minulého cvičení

• Načtení matice - dvourozměrného pole - ze souboru kombinuje načítání vektoru z minulého cvičení

pole=[]
f=open('pole.txt','r')
for line in f:
    pole.append(list(map(int, line.split())))

• 2D pole se hodí např. pro reprezentaci matic

• Napište funkci printMatrix, která vypíše matici zadanou 2D polem
• Prvky budou odděleny mezerou a každý řádek bude vypsán na nový řádek
• Kromě prvků matice nebude vypsán žádný jiný znak

• Napište funkci multiVecMat(v,m), která vypočte součin vektoru $v$ a matice $m$.
• Pokud nesouhlasí rozměry matice a vektoru, pak funkce vrací None.
• Vypočtete výsledek násobení $v \cdot m$:

m=[[0,0,1],[0,1,0],[1,0,0]]
v=[2, 4, 6]

Implementujte následující úlohy:

• Funkce, která v matici najde všechny záporné hodnoty, vraťte seznam jejich indexů
• Funkce pro násobení dvou matic
• Funkce pro výpočet determinantu matice
• Funkce pro výpočet stopy matice

• Napište program, který hledá nejlepší překryv dvou matic.
• Vstup:
  • Jména dvou soborů zadaná na příkazové řádce.
  • Každý soubor obsahuje 2D matici reálných čísel. Matice je uložena po řádcích, čísla jsou oddělena mezerou
  • První soubor obsahuje 'velkou' matici $I$ o rozměru $M \times N$, druhý soubor obsahuje 'malou' matici $W$ o rozměnu $a \times b$, $a<M,b<N$. Malá matice má vždy lichý počet řádků a lichý počet sloupců.
• Výstup:
  • Index řádku $r$ a sloupce $s$ matice $I$, kde je rozdíl matic nejmenší. Indexy začínají nulou ($0 < r < M-1$ a $0 < s < N-1$).
  • Indexy jsou vypsány na standardní výstup a jsou odděleny mezerou.
• Výpočet rozdílu matic:
  • Nechť $I(i,j)$ je prvek matice $I$ na řádku $i$ a sloupci $j$ (obdobně, W(i,j) je prvek v matici $W$).
  • Podobnost matice $I$ a matice $W$ na souřadnici $i,j$ je: $D(i,j) = \sum_{r=-a/2}^{a/2} \sum_{s=-b/2}^{b/2} |I(i+r,j+s)-W(r+a/2,s+b/2)|$, kde '/' značí celočíselné dělení.
  • Výstupem programu je taková souřadnice $(i,j)$, kde $D(i,j)$ nabývá minima.
  • Při výpočtu podobnosti uvažujte pouze takové souřadnice, ve kterých se matice $W$ celá vejde do matice $I$.
• Soubor odevzdejte do BRUTE, úloha HW05, soubor bestmatch.py
• Předpokládejte, že
  • Program je volán se jmény existujících souborů
  • Soubory jsou neprázdné a vždy obsahují správně zadané matice
  • V případě, že existuje více řešení, vypište libovolné z nich

• Příklad výpočtu podobnosti matic:

• Podobnost na pozici $D(1,1)= |2-1| + |4-2| + |2-3| + |6-4| + |0-5| + |1-6| + |2-7|+|8-8| + |2-9| = 28$
• Podobnost na pozici $D(2,3)=|1-1|+|9-2|+|0-3|+|2-4|+|1-5|+|0-6|+|4-7| + |2-8| + |1-9| = 39$

Příklady:

python3 bestMatch.py velka.txt mala.txt

Testovat můžete na jednoduchých příkladech, kde se matice $W$ celá nachází v matici $A$ (a minimální hodnota metriky je 0), například

'velka.txt'

1 2 1 2 3 8
1 2 1 2 3 8
1 2 4 5 6 8
1 2 7 8 9 8

1 2 3
4 5 6
7 8 9

Výsledek je souřadnice číslice 5, tj.

2 3

Pokud soubory 'velka.txt' a 'mala.txt' obsahují:

'velka.txt'

0.658824 0.603922 0.639216 0.462745 0.376471 0.380392 0.345098
0.607843 0.545098 0.572549 0.521569 0.376471 0.345098 0.333333
0.576471 0.47451 0.501961 0.490196 0.384314 0.286275 0.333333
0.52549 0.529412 0.443137 0.384314 0.423529 0.247059 0.286275

'mala.txt'

0.576471 0.47451 0.501961
0.52549 0.529412 0.443137
0.52549 0.541176 0.419608

Výsledek:

2 1

'velka.txt'

0.709804 0.698039 0.666667 0.670588 0.627451 0.635294 0.686275 0.639216 0.596078 0.737255 0.772549 0.745098 0.623529 0.52549 0.541176 0.419608
0.756863 0.74902 0.737255 0.745098 0.745098 0.658824 0.639216 0.701961 0.733333 0.682353 0.67451 0.635294 0.698039 0.607843 0.427451 0.392157
0.733333 0.694118 0.717647 0.729412 0.729412 0.764706 0.756863 0.705882 0.705882 0.721569 0.701961 0.678431 0.647059 0.603922 0.462745 0.4
0.705882 0.701961 0.690196 0.611765 0.6 0.596078 0.588235 0.615686 0.584314 0.6 0.537255 0.576471 0.588235 0.619608 0.588235 0.482353
0.705882 0.54902 0.494118 0.462745 0.45098 0.443137 0.454902 0.505882 0.513726 0.47451 0.415686 0.443137 0.427451 0.482353 0.509804 0.458824
0.509804 0.403922 0.45098 0.517647 0.533333 0.533333 0.486275 0.47451 0.556863 0.623529 0.521569 0.447059 0.384314 0.329412 0.333333 0.337255

'mala.txt'

0.509804 0.403922 0.45098
0.411765 0.470588 0.458824
0.419608 0.407843 0.447059

Výsledek je:

4 11

Praktická motivace: hledáním nejlepšího překryvu matice lze (velmi zjednodušeně) hledat např. obrázek v obrázku. Data pro domácí úlohu jsou generována z tohoto obrázku:

• Napište program chess.py, který načte soubor zadaný na příkazové řádce (argv[1]). Tento soubor kóduje stav šachovnice po tahu bílého. Program zkontroluje, zda bílý dává černému mat, šach, nebo garde.
• Vstup
  • Stav šachovnice je zaznamenán čísly reprezentující jednotlivé figury podle následující tabulky (bíle figury mají kladnou hodnotu, černé zápornou):

• Výstup (standardní výstup)
  • Výstupem Vašeho programu je hláška:
    • MAT - pokud černý dostal mat
    • SACH - pokud černý dostal šach a nenastala výše popsaná situace
    • GARDE - pokud je ohrožena černého dáma a nenastala žádná z výše popsaných situací
    • NO - pokud nenastala žádná výše popsaná situace.
• Soubor (viz. příklad sachovnice.txt) obsahuje dvourozměrné pole, ve kterém jsou výše definované hodnoty
• Program v souboru chess.py odevzdejte pomocí odevzdávacího systému (úloha HW05).
• Pokud Váš program nebude umět detekovat mat, pak získáte pouze 1 bod.

Vstup obsah souboru, zdaného jako vstupní argument:

-3  0 -4 -2  0 -1 -5 -3
-6 -6 -6  0  0  0 -6 -6
 0  0 -5  4  0  0  0  0
 0  0  0 -6  0  0  0  2
 0  0  0  6  0  0  0  0
 0  0  5  0  0  0  0  0
 6  6  6  0  0  0  6  6
 3  0  0  0  0  3  1  0

Výstup:

MAT