행렬의 개요 행렬은 수를 원소로 지니는 다차원 배열이다. mn (“m by n”) 행렬은 m개의 행과 n개의 열을 갖는다.

Slides:



Advertisements
Similar presentations
Chapter 04 컴퓨터에서 데이터 표현. 04 컴퓨터에서 데이터 표현 2 인코딩 (encoding) – 현실세계의 정보를 컴퓨터 내부에서 처리할 수 있는 이진수로 변환하는 방법 1. 컴퓨터 속에서 데이터 표현 원리 0 - 아빠 1 - 엄마 00 - 아빠 01 - 엄마.
Advertisements

1. 2 차원 배열  배열은 동일한 데이터 유형으로 여러 개의 변수를 사용할 경우 같은 이 름으로 지정하여 간편하게 사용할 수 있도록 하는 것으로서 앞에서 1 차원 배열을 공부하였습니다.  2 차원 배열은 바둑판을 생각하면 되며, 1 차원 배열에서 사용하는 첨자를 2.
주요 내용 행렬 스칼라, 벡터, 행렬 행렬의 합과 곱 여러가지 행렬들 전치 행렬 정방 행렬 역가능 행렬 역 행렬 행렬식.
4장 배열과 함수 한빛미디어(주).
이산수학(Discrete Mathematics)
Report #5 - due: 4/13 다음 10*5의 희소 행렬 A, B를 고려하라.
제2장 배열과구조.
Report #2 - Solution 문제 #1: 다음과 같이 프로그램을 작성하라.
보고서 #7 (기한: 6/2) 2개의 스택, stk1, stk2를 이용하여 큐를 구현하라.
부록 1: 행렬대수의 기본개념 1. 기본정의 2. 행렬 연산 전치(transpose) 행렬의 동등(equal)
분할 정복 (Divide-and-Conquer)
CHAP 2:순환 순천향대학교 컴퓨터공학과.
Chapter 02 순환 (Recursion).
P150 문제를 프로그래밍 할 것 Source file (헤더파일포함), 실행화면 (학번_이름_1.txt)
빠른정렬(Quick Sort) – 개요 (1/2)
CHAP 2:순환 C로 쉽게 풀어쓴 자료구조 생능출판사 2005.
8장 함수 함수의 필요성 라이브러리 함수와 사용자 정의 함수 함수의 정의, 원형, 호출 배열을 함수 인자로 전달 재귀호출.
Modulo 연산.
CAS (Computer Algebra System) 소개
2007 1학기 11 프로젝트 기초 실습.
행렬 기본 개념 행렬의 연산 여러가지 행렬 행렬식 역행렬 연립 일차 방정식 부울행렬.
제4장 제어 시스템의 성능.
Ⅲ. 이 차 방 정 식 1. 이차방정식과 그 풀이 2. 근 의 공 식.
프로그래밍 개요
어서와 C언어는 처음이지 제14장.
Lesson 4. 수식과 연산자.
자료구조: CHAP 7 트리 –review 순천향대학교 컴퓨터공학과 하 상 호.
Report #3 - due: 4/6 100*100의 2개의 희소 행렬 A, B를 전달 받아서 이들의 덧셈을 구하고, 그 결과의 행렬 C를 반환하는 add_sparse_matrix(A, B, C)를 다음과 같이 작성하라. 희소 행렬은 sparse_matrix 타입으로 표현된다.
CHAP 2:순환.
Quiz #7 다음 수들을 합병 정렬과 퀵 정렬 알고리즘을 이용하여 오름 차순으로 정렬하였을 때, 데이터 이동 회수를 각각 구하라. 여러분은 정렬 과정을 단계별로 보이면서 이동 회수를 추적해야 한다. 단, 퀵 정렬시에 피봇으로 배열의 왼쪽 첫 번째 원소를 선택한다. 5.
제 1 장 알고리즘 : 효율, 분석, 그리고 차수.
 Dynamic Programming (동적 프로그래밍)
Chapter6 : JVM과 메모리 6.1 JVM의 구조와 메모리 모델 6.2 프로그램 실행과 메모리 6.3 객체생성과 메모리
CHAP 2:순환 C로 쉽게 풀어쓴 자료구조 생능출판사 Slide 1 (of 19).
제 3 강.
행렬의 개요 행렬은 수를 원소로 지니는 다차원 배열이다. mn (“m by n”) 행렬은 m개의 행과 n개의 열을 갖는다.
알고리즘 강의 슬라이드 2 분할정복 분할정복법 도경구역, 알고리즘, 사이텍미디어, 1999.
 Divide and Conquer (분할정복)
제곱근의 곱셈과 나눗셈 제곱근의 곱셈과 나눗셈 a > 0, b > 0 일 때, √ 3 √ 5 √15 3 √ 5
김선균 컴퓨터 프로그래밍 기초 - 7th : 함수 - 김선균
컴퓨터 프로그래밍 기초 - 8th : 함수와 변수 / 배열 -
 Divide and Conquer (분할정복)
보고서 #7 (기한: 6/2) 2개의 스택, stk1, stk2를 이용하여 큐를 구현하라.
 Divide and Conquer (분할정복)
동적계획법과 최적화 문제 Dynamic Programming을 사용한 최적화 문제를 해결하는 알고리즘 설계 절차
CAS (Computer Algebra System) 소개
동적계획법과 최적화 문제 Dynamic Programming을 사용한 최적화 문제를 해결하는 알고리즘 설계 절차
CHAP 2:순환 C로 쉽게 풀어쓴 자료구조 생능출판사 2005.
1학기 수학 연산 풀이 (3학년) 와이즈캠프 담임선생님.
4장. 데이터 표현 방식의 이해. 4장. 데이터 표현 방식의 이해 4-1 컴퓨터의 데이터 표현 진법에 대한 이해 n 진수 표현 방식 : n개의 문자를 이용해서 데이터를 표현 그림 4-1.
Chapter 1 단위, 물리량, 벡터.
DA :: 퀵 정렬 Quick Sort 퀵 정렬은 비교방식의 정렬 중 가장 빠른 정렬방법이다.
5장. 선택 알고리즘.
빠른정렬(Quick Sort) – 개요 (1/2)
 Dynamic Programming (동적 프로그래밍)
7주차: Functions and Arrays
CHAP 2:순환.
쉽게 배우는 알고리즘 2장. 점화식과 점근적 복잡도 분석
2.7 행렬 (Matrices] 이산수학 (Discrete Mathematics) Matrix Reloaded
컴퓨터 프로그래밍 기초 - 9th : 배열 / 포인터 -
알고리즘(Algorithm) – Divide and Conquer (분할정복)
I. 수와 식 1. 유리수와 순환소수.
수치해석 ch3 환경공학과 김지숙.
2014년 가을학기 손시운 지도 교수: 문양세 교수님 행렬과 배열 2014년 가을학기 손시운 지도 교수: 문양세 교수님.
어서와 C언어는 처음이지 제21장.
빠른정렬(Quick Sort) – 개요 (1/2)
(Permutations and Combinations)
교착 상태 해결 : 교착 상태 탐지 교착 상태 탐지(Deadlock Detection)
II-1 단항식의 계산 01 소인수분해 지수법칙 지수법칙 지수법칙⑴ 3개 2개 5개 3+2 m개 n개 (m+n)개 합.
5. 1 두 수를 입력받아 큰 수를 구하는 순서도를 작성하시오
Presentation transcript:

행렬의 개요 행렬은 수를 원소로 지니는 다차원 배열이다. mn (“m by n”) 행렬은 m개의 행과 n개의 열을 갖는다. 행과 열의 개수가 같은 nxn 행렬을 정방행렬이라 한다. 두 행렬이 같은 수의 행과 열을 가지며 각 위치의 해당 원소의 값이 같으면 “두 행렬은 같다”고 정의한다.

행렬의 곱 행렬의 곱:  

행렬곱셈 – 단순 알고리즘 (1/3) void matrixmul(int n, number[][] A, number[][] B, 입력: 양수 n, n  n 크기의 행렬 A와 B 출력: 행렬 A와 B의 곱인 C 알고리즘: void matrixmul(int n, number[][] A, number[][] B, number[][] C){ index i, j, k; for (i = 1; i <= n; i++) for (j = 1; j <= n; j++) { C[i][j] = 0; for (k = 1; k <= n; k++) C[i][j]=C[i][j] + A[i][k]*B[k][j]; }

행렬곱셈 – 단순 알고리즘 (2/3) 곱셈 연산의 시간복잡도 분석 - I 단위연산: 가장 안쪽의 루프에 있는 곱셈 연산 입력크기: 행과 열의 수, n 모든 경우 시간복잡도 분석: 총 곱셈의 횟수는 다음과 같다.

행렬곱셈 – 단순 알고리즘 (3/3) 곱셈 연산의 시간복잡도 분석 – II (P. 86 연습문제 25번) … 단위연산: 가장 안쪽의 루프에 있는 덧셈(뺄셈) 연산 입력크기: 행과 열의 수, n 모든 경우 시간복잡도 분석: 아래와 같이 약간만 알고리즘을 변경하면 총 덧셈의 횟수는 다음과 같다. … for (i = 1; i <= n; i++) for (j = 1; j <= n; j++) { C[i][j] = A[i][1]*B[1][j]; for (k = 2; k <= n; k++) C[i][j]=C[i][j]+A[i][k]*B[k][j]; }

쉬트라쎈(Strassen) 방법 – 2x2 행렬 (1/2) 문제: 두 2  2 행렬 A와 B의 곱(product) C, 쉬트라쎈(Strassen)의 해: Why? 앉아서 꼼꼼히 따져보세요.

쉬트라쎈(Strassen) 방법 – 2x2 행렬 (2/2) 시간복잡도 분석: 단순 곱셈 방법: 8번의 곱셈과 4번의 덧셈이 필요함 쉬트라쎈 방법: 7번의 곱셈과 18번의 덧셈/뺄셈이 필요함  언뜻 봐서는 전혀 좋아지지 않았다!  그러나 행렬의 크기가 커지면 쉬트라쎈의 방법의 가치가 드러난다.

쉬트라쎈(Strassen) 방법 – nxn 행렬 (1/3) 문제: n이 2의 거듭제곱이고, 각 행렬을 4개의 부분행렬(submatrix)로 나눈다고 가정하자. 두 n  n 행렬 A와 B의 곱 C: 쉬트라센의 해

쉬트라쎈(Strassen) 방법 – nxn 행렬 (2/3) 예 (수행과정의 일부 – M1 구하기)

쉬트라쎈(Strassen) 방법 – nxn 행렬 (3/3) 문제: n이 2의 거듭제곱일 때, n  n 크기의 두 행렬의 곱을 구하시오. 입력: 정수 n, n  n 크기의 행렬 A와 B 출력: 행렬 A와 B의 곱인 C 알고리즘: nxn_matrix strassen(int n, nxn matrix A, nxn matrix B){ if (n <= threshold) 단순한 알고리즘을 사용하여 C = A * B를 계산; else { A를 4개의 부분행렬 A11, A12, A21, A22로 분할; B를 4개의 부분행렬 B11, B12, B21, B22로 분할; 쉬트라쎈의 방법을 사용하여 C = A * B를 계산; // C 계산시에 다음과 같은 재귀 호출 사용: // M1=strassen(n/2, A11+A22, B11+B22) // M2=strassen(n/2, A21+A22, B11) // M3=… } return C; Threshold? 쉬트라쎈 알고리즘보다 단순 알고리즘이 더 좋을 것이라 예상되는 지점

쉬트라쎈(Strassen) 방법의 분석 (1/7) 곱셈 연산에 대한 시간복잡도 분석 단위연산: 곱셈하는 연산 입력크기: 행과 열의 수, n 1×1 행렬이 될 때까지 계속 분할한다고 가정. threshold를 1이라고 가정 두 개의 1×1 행렬의 곱은 그 비용이 1이다. [모든 경우 시간복잡도] 분석 점화식을 다음과 같이 구할 수 있다. Why? 하나의 nxn 곱셈이 일곱 개의 (n/2)x(n/2) 곱셈으로 바뀌었기 때문

쉬트라쎈(Strassen) 방법의 분석 (2/7) 곱셈 연산에 대한 시간복잡도 분석 (계속) n=2k에 대해서 앞에서 구한 점화식을 전개하면 다음과 같다. 상기 결과는 귀납법에 의해서 증명이 가능하다. (Skip!) 또한, 상기 점화식은 Master Theorem 1번을 이용하면 간단히 해를 구할 수 있다. (See the next page)

쉬트라쎈(Strassen) 방법의 분석 (3/7) 곱셈 연산에 대한 시간복잡도 분석 (계속) n=2k에 대해서 앞에서 구한 점화식의 해를 Master Theorem 을 이용하여 구하기 f(n) = af(n/b) + cnd a=7, b=2, c=0, d=0  

쉬트라쎈(Strassen) 방법의 분석 (4/7) 덧셈/뺄셈 연산에 대한 시간복잡도 분석 단위연산: 덧셈/뺄셈하는 연산 입력크기: 행과 열의 수, n 모든 경우 시간복잡도 분석: 앞서와 마찬가지로 threshold를 1이라 한다. 점화식을 다음과 같이 구할 수 있다. nxn 곱셈이 일곱 개의 (n/2)x(n/2) 곱셈으로 바뀌었고, 18번의 (n/2)x(n/2) 행렬 덧셈/뺄셈이 필요한데, 각각은 (n/2)2 번의 덧셈/뺄셈을 필요로 하기 때문 Why?

쉬트라쎈(Strassen) 방법의 분석 (5/7) 덧셈/뺄셈 연산에 대한 시간복잡도 분석 (계속) 점화식은 다음과 같다. 부록 B의 예제 B.20을 이용하면 다음과 같이 점화식의 해가 구해진다. Master Theorem을 사용하면 상기 점화식의 해는 다음과 같이 구할 수 있다.   f(n) = af(n/b) + cnd a=7, b=2, c=9/2, d=2  

쉬트라쎈(Strassen) 방법의 분석 (6/7) 표 2.3 nxn 행렬을 곱하는 두 알고리즘의 비교 (p. 70) 단위 연산 표준 알고리즘 쉬트라센 알고리즘 곱셈 n3 n2.81 덧셈/뺄셈 n3 - n2 6n2.81 - 6n2

쉬트라쎈(Strassen) 방법의 분석 (7/7) Shmuel Winograd는 덧셈과 뺄셈을 조금 더 적게 수행하는 쉬트라센 알고리즘의 변형을 개발 이후에 Coppersmith와 Winograd는 곱셈의 복잡도를 까지 낮춘 알고리즘을 개발하였다. 그렇다면, 과연 얼마까지 복잡도를 낮출 수 있을까? 두 행렬을 곱하기 위한 문제에 대해서 시간복잡도가 이 되는 알고리즘을 만들어 낸 사람은 아무도 없다. 게다가 그러한 알고리즘을 만들 수 없다고 증명한 사람도 아무도 없다.  

Skip… Chapter 2.6 Chapter 2.7

  분할정복을 사용하지 말아야 하는 경우 c