(Basic Theory of Information Processing) 1

(Basic Theory of Information Processing) 1

10 (p.178) Java a[0] = 1; 1 a[4] = 7; i = 2; j = 8; a[i] = j; b[0][0] = 1; 2 b[2][3] = 10; b[i][j] = a[2] * 3; x = a[2]; a[2] = b[i][3] * x; 2

public class Array0 { public static void main(string[] args) { int iarray[] = new int[5]; iarray[0] = 3; iarray[1] = 1; iarray[2] = 4; iarray[3] = 1; iarray[4] = 5; for (int i = 0 ; i < 5 ; ++i) { System.out.println("iArray[" + i + "] = " + iarray[i]); int a0, a1, a2; i = 1: ai a1 ai 3

10.1 [] int 1 a e f int 2 b int 3 c double 1 x double 2 y int a[], b[][], c[][][]; int[] e, f; double x[], y[][]; int e[], f[]; 4

10.2 ( ) new a = new int[10]; b = new int[20][30]; x = new double[40][50]; 10 int a a[0] a[9] 20 30 int b b[0][0] b[19][29] 3 40 50 double x x[0][0] x[39][49] ( ) 5

int[] a = {1,9,8,10,7; int a[]; a = new int[5]; a[0] = 1; a[1] = 9; a[2] = 8; a[3] = 10; a[4] = 7; Java 6

10.3 1 length class ArrayLength { public static void main(string[] args) { int[] a, b; a = new int[2]; b = new int[4]; int[] c = {1, 2, 3, 4, 5; System.out.println("a.length = " + a.length); System.out.println("b.length = " + b.length); System.out.println("c.length = " + c.length); a.length = 2 b.length = 4 c.length = 5 7

10.4 2 1 1 int[][] m; 2 m int[] a, b, c, d; 1 a, b, c, d m = new int[4][]; a = new int[2]; b = new int[4]; c = new int[1]; d = new int[2]; m[0] = a; m[1] = b; m[2] = c; m[3] = d; m 1 8

class TwoArray1 { public static void main(string[] args) { int[][] m; 2 m int[] a, b, c, d; 1 a, b, c, d m = new int[4][]; a = new int[2]; b = new int[4]; c = new int[1]; d = new int[2]; m[0] = a; m[1] = b; m[2] = c; m[3] = d; m 1 System.out.println("m.length = " + m.length); for (int i = 0 ; i < 4 ; ++i) { System.out.println("m[" + i + "].length = " + m[i].length); m.length = 4 m[0].length = 2 m[1].length = 4 m[2].length = 1 m[3].length = 2 9

class TwoArray2 { public static void main(string[] args) { int[][] m; int[] a, b, c, d; m = new int[4][]; a = new int[2]; b = new int[4]; c = new int[1]; d = new int[2]; System.out.println("d[1] = " + d[1]); m[0] = a; m[1] = b; m[2] = c; m[3] = d; b[3] = 6; m[3][1] = 5; for (int i = 0 ; i < 4 ; ++i) { for (int j = 0 ; j < m[i].length ; ++j) { System.out.println("m[" + i + "][" + j + "] = " + m[i][j]); System.out.println(""); System.out.println("d[1] = " + d[1]); d[1] = 0 m[0][0] = 0 m[0][1] = 0 m[1][0] = 0 m[1][1] = 0 m[1][2] = 0 m[1][3] = 6 m[2][0] = 0 m[3][0] = 0 m[3][1] = 5 d[1] = 5 10

class TwoArray3 { public static void main(string[] args) { int[][] m = {{1, 2, {3, 4, 5, 6, {7, {8, 9; for (int i = 0 ; i < 4 ; ++i) { System.out.println("m[" + i + "].length = " + m[i].length); for (int j = 0 ; j < m[i].length ; ++j) { System.out.println("m[" + i + "][" + j + "] = " + m[i][j]); m[0].length = 2 m[0][0] = 1 m[0][1] = 2 m[1].length = 4 m[1][0] = 3 m[1][1] = 4 m[1][2] = 5 11 m[1][3] = 6 m[2].length = 1 m[2][0] = 7 m[3].length = 2 m[3][0] = 8 m[3][1] = 9

12

11 ( ) 13

11.1 ( ) (SSE: Streaming Single instruction multiple data Extensions, AVX: Advanced Vector extensions) GPU (Graphics Processing Unit) BLAS (Basic Linear Algebra Subprograms) LAPACK (Linner Algebra Package) 14

11.1.1 N i = 1, 2,..., N z = x + y z i = x i + y i public class AddVect { // AddVect.java public static void main(string[] args) { int N = 4; int[] a = {1, 3, 4, 5, b = {3, 9, 4, 5; int[] c = new int[4]; for (int i = 0 ; i < N ; ++i) { // c[i] = a[i] + b[i]; for(int i = 0 ; i < N ; ++i) { System.out.println("c[" + i + "] = " + c[i]); 15

11.1.2 N x, y N x i y i i=1 public class InPro { // InPro.java public static void main(string[] args) { int N = 4; int[] a = {1, 3, 4, 5, b = {3, 9, 4, 5; int inpro = 0; for(int i = 0 ; i < N ; ++i) { inpro += a[i] * b[i]; System.out.println("inPro = " + inpro); 16

11.1.3 M N C = A + B i = 1, 2,..., M j = 1, 2,..., N C ij = A ij + B ij public class AddMat { // AddMat.java public static void main(string[] args) { int M = 3, N = 4; int[][] A = {{1, 3, 2, 7, {4, 5, 1, -3, {7, 4, -3, -2; int[][] B ={{3, 5, 2, 7, {3, 2, 5, -7, {3, 2, -4, 2; int[][] C = new int[m][n]; 17

for(int i = 0 ; i < M ; ++i) { for(int j = 0 ; j < N ; ++j) { C[i][j] = A[i][j] + B[i][j]; // for(int i = 0 ; i < M ; ++i) { for(int j = 0 ; j < N ; ++j) { System.out.println("C[" + i + "][" + j + "] = " + C[i][j]); 18

11.1.4 M N C = A T i = 1, 2,..., N j = 1, 2,..., MN C ij = A ji public class TransMat { // Transposition.java public static void main(string[] args) { int M = 3, N = 4; int[][] A = {{1, 3, 2, 7, {4, 5, 1, -3, {7, 4, -3, -2; int[][] B = new int[n][m]; for(int i = 0 ; i < N ; ++i) { for(int j = 0 ; j < M ; ++j) { B[i][j] = A[j][i]; for(int i = 0 ; i < N ; ++i) { for(int j = 0 ; j < M ; ++j) { System.out.println("B[" + i + "][" + j + "] = " + B[i][j]); 19

11.1.5 M N N y i = y = Ax N A ij x j j=1 20

public class MulMatVect { // MulMatVect.java public static void main(string[] args) { int M = 3, N = 2; int[][] A = {{1, 3, {4, 5, {7, 4; int[] x = {3, 9; int[] y = new int[m]; for(int i = 0 ; i < M ; ++i) { int sum = 0; for(int j = 0 ; j < N ; ++j) { sum += A[i][j] * x[j]; y[i] = sum; for(int i = 0 ; i < M ; ++i) { System.out.println("y[" + i + "] = " + y[i]); 21

11.1.6 M K K N C = AB K C ij = A ik B kj k=1 public class MulMat { // MulMatMat.java public static void main(string[] args) { int M = 3, K = 2, N = 4; int[][] A = {{1, 3, {4, 5, {7, 4; int[][] B = {{3, 9, 4, 5, {3, 7, 1, 2 ; int[][] C = new int[m][n]; 22

for(int i = 0 ; i < M ; ++i) { for(int j = 0 ; j < N ; ++j) { int sum = 0; for(int k = 0 ; k < K ; ++k) { sum += A[i][k] * B[k][j]; C[i][j] = sum; for(int i = 0 ; i < M ; ++i) { for(int j = 0 ; j < N ; ++j) { System.out.println("C[" + i + "][" + j + "] = " + C[i][j]); 23

11.2 1 24

11.3 ( ) int[] A = new int[n] 25

11.3.1 1. 2. N! 11.3.2 1. l = 0 2. A[l] A[N-1] ( A[m] ) 3. A[l] A[m] 4. l = l + 1 5. l == N - 1 2 N 2 26

(l = 0) 2 (l = 1) 2 3 (l = 2) 3 27

4 (l = 3) 4 5 (l = 4) 5 6 (l = 5) 6 7 (l = 6) 7 28

11.3.3 public class SortAsc { public static void main(string[] args) { int data[] = {1, 3, 5, -2, -3, 6, -9; for (int k = 0 ; k < data.length - 1 ; ++k) { int minind = k; for (int l = k + 1 ; l < data.length ; ++l) { if (data[minind] > data[l]) minind = l; int min = data[minind]; data[minind] = data[k]; data[k] = min; for (int k = 0 ; k < data.length ; ++k) { System.out.println((k + 1) + " " + data[k] + " "); ( ) 29

11.3.4 1. l = 0; m = 1; 2. l l = m; m = m + 1; 3. l == N - 1 4. 4. A[l] <= A[l + 1] l = m; m = m + 1; A[l] A[l + 1] l = l - 1 5. 2 N 2 30

(l = 0, m = 1) 1 2 (l = 0, m = 1) 2 3 (l = 1, m = 2) ( l = 0, m = 2) 1 2 (l = 0, m = 2) ( l = -1, m = 2) (l = -1) (l = 1) (l = 2) 3 4 (l = 2, m = 3) ( l = 1, m = 3) 31

2 3 (l = 1, m = 3) (l = 2) (l = 3) 4 5 ( l = 3, m = 4) 5 6 (l = 4, m = 5) ( l = 3, m = 5) 4 5 (l = 3, m = 5) ( l = 2, m = 5) 3 4 (l = 2, m = 5) ( l = 1, m = 5) 32

33

11.3.5 1. 2. return 3. ( ) 4. ( ) 5. 2 2 6. return return N log N N 2 34

35

36

37

38

11.3.6 n = 1 n 2 2 2n 1 39

40

N log N ( ) ( ) ( ) ( ) 41

11.3.7 1 ( ) N log N (ShowHeapSort.java) 42

11.4 int i[]; int[] j; double d[][]; i = new int[5]; j = new int[10]; d = new int[8][8]; 43