2.7 행렬 (Matrices] 이산수학 (Discrete Mathematics) Matrix Reloaded

Slides:



Advertisements
Similar presentations
1. 2 차원 배열  배열은 동일한 데이터 유형으로 여러 개의 변수를 사용할 경우 같은 이 름으로 지정하여 간편하게 사용할 수 있도록 하는 것으로서 앞에서 1 차원 배열을 공부하였습니다.  2 차원 배열은 바둑판을 생각하면 되며, 1 차원 배열에서 사용하는 첨자를 2.
Advertisements

2012 년 봄학기 강원대학교 컴퓨터과학전공 문양세 이산수학 (Discrete Mathematics)  중첩된 한정기호 (Nested Quantifiers)
주요 내용 행렬 스칼라, 벡터, 행렬 행렬의 합과 곱 여러가지 행렬들 전치 행렬 정방 행렬 역가능 행렬 역 행렬 행렬식.
컴퓨터 개론 및 실습 강의 9.
이산수학(Discrete Mathematics)
(Mathematical Induction)
Sources of the Magnetic Field
Mathematics for Computer Graphics
Mathematics for Graphics
Chapter 7 ARP and RARP.
스테레오 비젼을 위한 3장 영상의 효율적인 영상정렬 기법
6.9 Redundant Structures and the Unit Load Method
Engineering Mathematics, Fourth Edition
1.8 함수 (Functions) 이산수학 (Discrete Mathematics) 2006년 봄학기 문양세
Inversion of Geophysical Data
Chaper 2 ~ chaper 3 허승현 제어시스템 설계.
희소 행렬(sparse matrix) mn matrix A ≡ A[MAX_ROWS][MAX_COLS] 희소행렬
제2장 배열과구조.
수치해석 (Numerical Analysis)
제 5 장 암호학의 수학기초 Network Security Lab Mun Hyung Jin.
시스템 생명 주기(System Life Cycle)(1/2)
제 6 장 데이터 타입 6.1 데이터 타입 및 타입 정보 6.2 타입의 용도 6.3 타입 구성자 6.4 사례 연구
부록 1: 행렬대수의 기본개념 1. 기본정의 2. 행렬 연산 전치(transpose) 행렬의 동등(equal)
Ch. 1 선형대수학: 행렬, 벡터, 행렬식, 선형연립방정식
시스템 생명 주기(System Life Cycle)(1/2)
제 5장. Context-Free Languages
이산수학(Discrete Mathematics) 수학적 귀납법 (Mathematical Induction)
Dynamic Programming.
재귀 혹은 귀납 Recursive or Inductive Definition 집합을 정의하는 방법
Chapter 2. Finite Automata Exercises
Discrete Math II Howon Kim
숭실대학교 마이닝연구실 김완섭 2009년 2월 8일 아이디어  - 상관분석에 대한 연구
행렬 기본 개념 행렬의 연산 여러가지 행렬 행렬식 역행렬 연립 일차 방정식 부울행렬.
계수와 응용 (Counting and Its Applications)
Medical Instrumentation
PCA Lecture 9 주성분 분석 (PCA)
1.4 중첩된 한정기호 (Nested Quantifiers) 이산수학 (Discrete Mathematics)
(Relations and Its Properties)
Mathematical Description of Continuous-Time Signals
Report #3 - due: 4/6 100*100의 2개의 희소 행렬 A, B를 전달 받아서 이들의 덧셈을 구하고, 그 결과의 행렬 C를 반환하는 add_sparse_matrix(A, B, C)를 다음과 같이 작성하라. 희소 행렬은 sparse_matrix 타입으로 표현된다.
Introduction to Programming Language
MATLAB Image Processing Toolbox
Dynamic Programming.
이산수학(Discrete Mathematics)  증명 방법 (Methods of Proof)
제 3 강.
행렬의 개요 행렬은 수를 원소로 지니는 다차원 배열이다. mn (“m by n”) 행렬은 m개의 행과 n개의 열을 갖는다.
행렬의 개요 행렬은 수를 원소로 지니는 다차원 배열이다. mn (“m by n”) 행렬은 m개의 행과 n개의 열을 갖는다.
이산수학(Discrete Mathematics)  명제의 동치 (Propositional Equivalence)
6.1 점화 관계 (Recurrence Relations)
제 3장 행 렬.
제 세 동.
그래프와 트리 (Graphs and Trees)
동적계획법과 최적화 문제 Dynamic Programming을 사용한 최적화 문제를 해결하는 알고리즘 설계 절차
SEOUL NATIONAL UNIVERSITY OF SCIENCE & TECHNOLOGY
이산수학 (Discrete Mathematics)
이산수학(Discrete Mathematics) 비둘기 집 원리 (The Pigeonhole Principle)
이산수학(Discrete Mathematics)
이산수학(Discrete Mathematics)  집합 연산 (Set Operations)
점화와 응용 (Recurrence and Its Applications)
1. 관계 데이터 모델 (1) 관계 데이터 모델 정의 ① 논리적인 데이터 모델에서 데이터간의 관계를 기본키(primary key) 와 이를 참조하는 외래키(foreign key)로 표현하는 데이터 모델 ② 개체 집합에 대한 속성 관계를 표현하기 위해 개체를 테이블(table)
이산수학(Discrete Mathematics)
알고리즘(Algorithm) – Divide and Conquer (분할정복)
7장 연습 문제 풀이 학번 : 이름 :조 재한.
이산수학(Discrete Mathematics) 수열과 합 (Sequences and Summations)
Geometry and Algebra of Projective Views
이산수학(Discrete Mathematics)  술어와 한정기호 (Predicates and Quantifiers)
2014년 가을학기 손시운 지도 교수: 문양세 교수님 행렬과 배열 2014년 가을학기 손시운 지도 교수: 문양세 교수님.
[CPA340] Algorithms and Practice Youn-Hee Han
SEOUL NATIONAL UNIVERSITY OF SCIENCE & TECHNOLOGY
(Permutations and Combinations)
Presentation transcript:

2.7 행렬 (Matrices] 이산수학 (Discrete Mathematics) Matrix Reloaded 2006년 봄학기 문양세 강원대학교 컴퓨터과학과 Matrix Reloaded Revolution

Plural of matrix = matrices Introduction 2.7 Matrices A matrix (say MAY-trix) is a rectangular array of objects (usually numbers). (행렬은 수의 사각형 배열이다.) An mn (“m by n”) matrix has exactly m horizontal rows, and n vertical columns. (m개의 행과 n개의 열을 갖는 행렬) Plural of matrix = matrices An nn matrix is called a square matrix, whose order is n. (행과 열의 개수가 같은 행렬을 정방행렬이라 한다.) Tons of applications: Models within Computational Science & Engineering Computer Graphics, Image Processing, Network Modeling Many, many more …

Matrix Equality 2.7 Matrices Two matrices A and B are equal iff they have the same number of rows, the same number of columns, and all corresponding elements are equal. (두 행렬이 같은 수의 행과 열을 가지며 각 위치의 해당 원소의 값이 같으면 “두 행렬은 같다”고 정의한다.) Example

Row and Column Order (1/2) 2.7 Matrices The rows in a matrix are usually indexed 1 to m from top to bottom. (행은 위에서 아래로 1~m의 색인 값을 갖는다.) The columns are usually indexed 1 to n from left to right. (열은 왼쪽에서 오른쪽으로 1~n의 색인 값을 갖는다.) Elements are indexed by row, then column. (각 원소는 행 색인, 열 색인의 순으로 표현한다.)

Row and Column Order (2/2) 2.7 Matrices Let A be mn matrix [ai,j], ith row = 1n matrix [ai,1, ai,2, …, ai,n], jth column = n1 matrix

A+B = C = [ci,j] = [ai,j+bi,j] where A = [ai,j] and B = [bi,j] Example Matrix Sums 2.7 Matrices The sum A+B of two mn matrices A, B is the mn matrix given by adding corresponding elements. (A+B는 (i,j)번째 원소로서 ai,j+bi,j를 갖는 행렬이다.) A+B = C = [ci,j] = [ai,j+bi,j] where A = [ai,j] and B = [bi,j] Example

Matrix Products (1/2) 2.7 Matrices For an mk matrix A and a kn matrix B, the product AB is the mn matrix: I.e., element (i,j) of AB is given by the vector dot product of the ith row of A and the jth column of B (considered as vectors). (AB의 원소 (i,j)는 A의 i번째 열과 B의 j번째 행의 곱이다.)

Matrix multiplication is not commutative! (교환법칙 성립 안 함) Matrix Products (2/2) 2.7 Matrices Example Matrix multiplication is not commutative! (교환법칙 성립 안 함) A = mn matrix, B = rs matrix AB can be defined when n = r BA can be defined when s = m Both AB and BA can be defined when m = n = r = s

What’s the  of its time complexity? Matrix Multiplication Algorithm 2.7 Matrices procedure matmul(matrices A: mk, B: kn) for i := 1 to m for j := 1 to n begin ci,j := 0 for q := 1 to k ci,j := ci,j + ai,qbq,j end {C=[ci,j] is the product of A and B} (m)· (n)·( What’s the  of its time complexity? (1)+ Answer: (mnk) (k) · (1))

Identity Matrices 2.7 Matrices The identity matrix of order n, In, is the order-n matrix with 1’s along the upper-left to lower-right diagonal and 0’s everywhere else. ((i,i)번째 원소가 1이고, 나머지는 모두 0인 행렬) AIn = InA = A

Matrix Inverses 2.7 Matrices For some (but not all) square matrices A, there exists a unique multiplicative inverse A-1 of A, a matrix such that A-1A = In. (정방 행렬 A에 대해서 하나의 유일한 역행렬 A-1이 존재한다.) If the inverse exists, it is unique, and A-1A = AA-1. A A-1 I3

Matrix Transposition (전치 행렬) 2.7 Matrices If A=[ai,j] is an mn matrix, the transpose of A (often written At or AT) is the nm matrix given by At = B = [bi,j] = [aj,i] (1in,1jm) If the inverse exists, it is unique, and A-1A = AA-1. Flip across diagonal

Symmetric Matrices (대칭 행렬) A square matrix A is symmetric iff A=At. I.e., i,jn: aij = aji . Which is symmetric?

Powers of Matrices (멱행렬) If A is an nn square matrix and p0, then: Ap  AAA···A (A0  In) Example: p times

Zero-One Matrices (0-1 행렬) Useful for representing other structures. E.g., relations, directed graphs (later in course) All elements of a zero-one matrix are 0 or 1 Representing False & True respectively. The join of A, B (both mn zero-one matrices): AB : [aijbij] (= [aij bij]) The meet of A, B: AB : [aijbij]

A⊙B Boolean Products (부울 곱) (1/2) 2.7 Matrices Let A=[aij] be an mk zero-one matrix, & let B=[bij] be a kn zero-one matrix, The Boolean product of A and B is like normal matrix multiplication, but using “” instead “+” using “” instead of “∙” A⊙B

Boolean Products (부울 곱) (2/2) 2.7 Matrices Example: Algorithm of Boolean Product ⊙ procedure Boolean product(A,B: zero-one matrices) for i := 1 to m for j := 1 to n begin cij = 0 for q := 1 to k cij = cij  (aiq  bqj) end {C = [cij] is the Boolean product of A and B.}

Boolean Powers (부울 거듭제곱) 2.7 Matrices For a square zero-one matrix A, and any k0, the kth Boolean power of A is simply the Boolean product of k copies of A. (A의 k 부울린 거듭제곱) A[k]  A⊙A⊙…⊙A, A[0]  In Example: k times ⊙ ⊙ ⊙ ⊙

Homework #4 $2.4의 연습문제: 4, 12(d), 28(a, d) 2.7 Matrices $2.4의 연습문제: 4, 12(d), 28(a, d) $2.5의 연습문제: 4(d), 22(c), 36(b, c) $2.7의 연습문제: 2(b), 4(b), 8, 28 Due Date: