은둔형 공학자

이진트리

1. 이진트리의 기본 개념

2) 이진트리의 특징 

. 모든 노드들이  2개의 서브트리를 갖는 특별한 형태의 트리이며, 자료구조에서 가장 많이 쓰이는 트리구조 중의 하나이다. 

. 노드가 하나도 없는 빈 트리(empty  tree)가 될 수도 있다. 즉, 노드가 하나도 없는 빈 트리이거나 루트노드 하나로만 되어 있거나 두 개 이상의 노드로 되어 있을 때는 각 노드가 자식 노드를 최대한  2개까지만 가질 수 있는 트리를 말한다. 

.  이진트리에서  모든  노드는  왼쪽  자식  노드(left  child  node)와  오른쪽  자식노드(right  child node)를 가지고 있는데, 왼쪽 자식노드나 오른쪽 자식노드 중 하나만 가질 수도 있다. 

. 이진트리는 왼쪽 서브트리와 오른쪽 서브트리로 서브트리의 순서를 구별하지만 일반적인 트리에서는 서브트리의 순서를 구분하지 않는다. 

. 이진트리의 서브 트리들은 모두 이진트리여야 한다. 

정리  03 

트리  T가  i개의 내부정점 을 가진 완전 이진트리라면, 트리  T는  i+1개의 단말노드(잎노드)를 갖는다. 즉, 총  2i+1개의 정점을 가진다. 

[증명] 

T의 정점들은 어떤 부모의 자식인 정점들과 어떤 부모에게도 자식이 아닌 정점들로 구성된다. 

자식이 아닌 정점은 근노드(루트노드) 하나만 존재한다. 따라서 각각  2개의 자식을 갖는  i개의 내부정점이 있으므로,  2i개의 자식이 있게 된다. 그러므로  T의 정점의 총수는  2i+1이고, 잎노드의 수는  (2i+1)-i=i+1 이다. 

2) 연결리스트(linked  list)에 의한 방법 

. 노드가 구조체로 표현되고 각 노드가 포인터를 가지고 있어서 이 포인터를 이용하여 노드와 노드를 연결하는 방법이다. 

. 각 노드는 세 개의 필드(왼쪽 포인터, 노드의 값을 저장하는 부분, 오른쪽 포인터)로 구성. 

3. 이진트리의 순회 

이진트리의 순회(traversal) 

. 이진 트리에 속한 모든 노드들을 한 번씩 방문하여 노드가 가지고 있는 데이터를 목적에 맞게 처리하는 것 

. 이진트리의  3가지 순회 방법 

① 전위 순회  (preorder  traversal) 방법 

② 중위 순회  (inorder  traversal) 방법 

③ 후위 순회  (postorder  traversal) 방법 

1) 전위 순회(preorder  traversal) 

1차시

트리의 기본개념

1. 트리의 기본 개념

1) 트리(Tree) 

. 그래프에서 가장 중요한 클래스(class) 

. 가계도나 회사의 조직도 등을 나타낼 때 유용하게 사용되고 있는 비선형 자료구조(non-linear data  structure) 

. 계층적 자료구조(hierarchical data  structure) 

*화학에서의 트리

. 트리(Tree)의 정의 

.  A를 유한 집합이라 하고  T를  A에서의 관계라 하자.  A에 속하는 정점  v0 에 대해  v0 에서  A의 모든 다른 정점으로는 유일한 경로가 존재하고,  v0에서  v0 로 가는 경로는 존재하지 않을 때 관계  T를 트리(Tree)라 한다. 

.  트리T는  다음을  만족시키는  단순그래프이다.  v와  w가  T의  정점들이면,  v에서  w로의  유일한 단순 경로가 존재한다. 

. 근트리(rooted  tree)는 특별한 정점이 뿌리(루트노드)로 지정된 트리이다. 

2. 트리의 주요 용어 

1) 숲(forest) 

. 연결되어 있지 않아서 트리는 아니지만 그래프의 각 성분은 트리로 되어 있는 그래프. 즉, 서로 연결되어 있지 않은 트리들의 집합 

. 트리에서 루트 노드를 제거하면 발생하는  n개의 분리된 트리들을 숲(forest)이라고도 한다. 

. <그림6>에서 루트노드  a를 제거하면  T1,  T2로 이루어진 숲을 얻는다. 

2) 노드(node) 

. 트리의 구성 요소. <그림  6>에서  a, b,  c,  d,  e,  f,  g, h,  i,  j,  k이다. 

3) 루트(root) 

. 주어진 그래프의 시작 노드로서 통상 트리의 가장 높은 곳에 위치하며 <그림  6>에서 노드  a가 루트노드이다. 

3) 서브트리(subtree) 

. 하나의 노드와 그 노드들의 자손들로 이루어진 트리, <그림  6>에서 트리  T1과  T2이다. 

4) 차수(degree) 

. 어떤 노드의 차수는 그 노드의 서브트리의 개수를 나타낸다.  <그림  6>에서 노드  a의 차수는 2,  d의 차수는  3,  h의 차수는  1,  k의 차수는  0이다. 

.트리에 있는 각 노드의 차수 중에서 가장 큰 차수를 트리의 차수(degree of  tree)라고 한다. 

5) 잎노드  (leaf  node) 또는 단말노드(terminal  node) 

. 차수가  0인 노드로서 <그림  6>에서  c,  e,  f, g,  j,  k이다. 

6) 자식 노드(children  node) 

. 어떤 노드의 서브 트리의 루트노드들을 말하는데 <그림 6>에서 노드 a의 자식 노드는 b, h 이다. 

7) 부모노드(parent  node) 

. 자식 노드의 반대 개념으로서  <그림  6>에서  b의 부모노드는  a이고,  e,  f,  g의 부모노드는  d이다. 

8) 형제노드(sibling  node) 

. 동일한 부모를 가지는 노드인데  <그림  6>에서  b,  h는 모두 형제 노드이고,  e,  f,  g도 형제노드이다. 

9) 중간노드  (internal  node) 

. 루트도 아니고 잎노드도 아닌 노드를 말한다.<그림  6>에서  b,  d, h,  i이다. 

그래프의 탐색

1. 그래프의 탐색

. 그래프의 가장 기본적인 연산 

. 연결된 간선들을 통하여 그래프의 각 정점들을 모두 한 번씩 방문하는 방법 

. 그래프의 많은 문제들이 단순히 그래프의 노드를 탐색하는 것으로 해결됨 

(예) 도로망에서 특정 도시에서 다른 도시로 갈 수 있는지 여부 

(예) 전자회로에서 특정 단자와 다른 단자가 서로 연결되어 있는지 여부 

. 주어진 그래프 G=(v,E)와 정점  v∈V가 주어졌을 경우,  v로부터 도달 가능한 모든 정점들을 방문하는 그래프의 탐색에는 깊이 우선 탐색과 너비 우선 탐색 방법이 있다. 

1) 깊이우선 탐색(Depth  First  Search  : DFS) 

. 탐색과정 

①출발 정점을  v를 방문한다. 

②  v에 인접하고 아직 탐색을 거치지 않은 정점w를 선택한다. 그리고 w를 기준으로 다시 w에 인접하고 아직 탐색을 거치지 않은 정점u을 선택해 나가는 방식으로 탐색을 반복한다. 

③반복 과정 중에 인접한 모든 정점이 이미 탐색을 거친 상태라면 가장 최근에 탐색했던 정점 중에서 아직 탐색되지 않은 정점을 기준으로 다시 깊이 우선 탐색을 시작한다. 

④모든 정점을 방문 후 탐색을 종료한다. 

depth_first_search(v) 

  v를 방문되었다고 표시; 

for  all  u ∈  (v에 인접한 정점)  do 

  if  (u가 아직 방문되지 않았으면)then  depth_first_search(u) 

2) 너비 우선 탐색(breadth  First  Search  :  BFS) 

. 너비우선 탐색은 항상 새로 선택한 정점을 기준으로 인접한 정점을 방문하는 깊이 우선 탐색과는 달리 출발정점을 기준으로 인접한 정점들을 차례로 먼저 모두 방문하는 방식의 탐색방법이다. 

. 탐색과정 

① 출발 정점을  v를 방문한다. 

②  v에 인접하고 아직 탐색하지 않은 정점들 을 모두 탐색한다. 

③  그리고  순서대로  에  인접한  정점들을  같은  방법으로  탐색하게  된다.  이  과정을  더  이상 방문할 정점이 없을 때까지 반복 실행한다. 

④ 모든 정점을 방문 후 탐색을 종료한다.

너비 우선 탐색 알고리즘 

breadth_first_search(v) 

v를 방문되었다고 표시; 

큐 Q에 정점  v를 삽입; 

while  (not  is_empty(Q))  do 

       Q에서 정점 w를 삭제; 

        for  all u ∈  (w에 인접한 정점) do 

                 if  (u가 아직 방문되지 않았으면)  then  { 

                          u를 큐에 삽입; 

                          u를 방문되었다고 표시; 

2. 그래프의 색칠문제

정의1

G=(V,  E)는 다중 간선이 없는 그래프이고,  C={c1,  c2,  c3,…,  cn  }은  n개의 색깔로 구성된 임의의 집합이라고 하자. 

임의의 함수  f  :  V.  C는  “n색깔을 이용한 그래프  G의 채색(또는 그래프G의 색칠문제  coloring problem))’이라고 한다. 모든 정점  v 각각에 대하여,  f(v)는  v의 색깔이다. 

.그래프 색칠문제의 예를 들면 그래프가 연결된 도시들을 표현한다고 하자.

 각 도시는 그 도시에 가장 많이 이륙 또는 착륙하는 항공편을 가진 항공사 이름으로 레이블 될 수 있다. 이 경우 

정점은 도시이고, 색깔은 항공사 이름이 된다. 

. 모든 이웃한 정점  i와  j는 서로 다른 색깔로 채색될 때, 이러한 채색은  ‘적당하다(proper)’라고 한다. 

정의2

그래프  G를  색칠하는데  필요한  최소한의  색의  수를  x(G)로  표현하고  G의  색칠수  (chromatic number) 혹은 채색수 라고 한다. 

. 단순 그래프의 색칠은 각각의 정점을 서로 다른 색으로 색칠함으로써 알 수 있다. 

그러나 대부분의  그래프에서  정점의  수보다  적은  색깔을  사용해도  색칠이  가능하다.  

그렇다면  몇  가지 색으로 모든 경계가 구별되도록 색칠을 할 수 있을까? 

. 그래프 채색의 예  :  (1) 지도채색문제 

. 지도를 채색하는 것은 각 영역(국가, 주, 군, 도, 등)이 경계선을 공유하는 두 영역에 같은 색깔로 채색되는 일이 없도록 색칠 하는것. 

. 지도 채색문제는 지도를 채색하기 위하여 사용되는 최소의 색깔의 가지 수를 찾는 것. 

. 지도 M이 주어지면, 각 영역을 하나의 정점으로 표현하고 경계를 공유하는 영역에 해당하는 정점들을 간선으로 표현함으로써 그래프 GM을 구축. 

. 지도를 색칠하는 문제는 그래프의 색칠문제와 연관시킬 수 있다. 예를 들어  (1)의 지도는  (2)의 그래프와 동형이 되는데, 이것을 쌍대 그래프(dual graph)라고 한다. 

. 지도의 영역을 색칠하는 문제는 쌍대 그래프의 정점들을 색칠하는 문제와 동일하므로 그래프의 인접한 어떤 정점들도 같은 색을 가지지 않도록 해야 한다. 

. Welch-Powell의 알고리즘 

(1)  G의  정점의  차수가  내림차순(descending  order)이  되게  배열한다(이  배열은  차수가  같은정점이 여러 개 있을 수 있으므로 몇 가지 다른 순서가 존재할 수 있다). 

(2) 배열의 첫 번째 정점은 첫 번째 색으로 착색하고 계속해서 배열의 순서대로 이미 착색된 정점과 인접하지 않은 정점을 모두 같은 색으로 착색한다. 

(3) 배열에서 먼저 나타나는 착색되지 않은 정점을 두 번째 색으로 착색하고 계속해서 배열의 순서대로 지금 착색하고 있는 색으로 이미 착색된 정점과 인접하지 않은 정점을 모두 착색한다. 

(4) 계속해서 위의 과정을 그래프의 모든 정점이 착색될 때까지 반복한다. 

. 그래프 채색의 예  :  (2) 세기(counting) 문제 

. 가까이 두면 서로 반응하는 화학 물질들을 분리하여 저장할 필요가 있을 때, 화학물질을 저장하기 위한 실험실 서랍의 최소개수를 계산하는 문제 

.  15가지 음식을 같은 냉장고 안에 여러 칸에 넣으려고 하는 것을 그래프로 표현 하는 경우 

. 먼저  1가지 음식을 하나의 정점(vertex)으로 표현하고, 반드시 분리되어 저장되어야 하는 음식을 간선(edge)으로 연결한다. 그러면  x(G)는  15가지 음식을 저장하는데 최소한 필요한 칸의 수가 된다. 

. 채색다항식(Chromatic  polynomial) 

.  x(G)를 계산하는 문제와 깊이 관련이 있는 문제 중에 집합  C={c1,  c2,  …  ,  cn  }의 색깔을 이용한 그래프 G의 적당한 채색의 가지수는 몇인가 계산하는 문제 

정의3

G가 그래프이고  n≥0은 정수이면,  n이나 더 적은 수의 색을 이용하여 그래프  G를 적당히 채색하는 방법의 수를 채색다항식  (Chromatic  polynomial) 이라고 하고,  PG(n)으로 표기한다.

특수형태의 그래프와 그래프의 응용

1. 특수형태의 그래프

1) 오일러의 경로와 오일러 순환 

: 그래프의 각 간선을 정확히 한번씩만 사용하여 방문하는 문제 

오일러의 성질을 만족하는 특수한 형태의 그래프인 오일러 경로와 오일러 순환(circuit, 또는 순회)는 다음과 같이 정의된다. 

(1) 오일러 경로(Euler  path)란 그래프  G=(V,  E)에 대해  G 안의 모든 정점과 모든 에지가 포함되는 경로를 말한다. 즉, 그래프에서 각 에지(edge)를 한 번씩만 통과하는 경로를 의미한다. 

(2) 오일러 순환(Euler  circuit,  Euler  cycle)란 그래프 G=(V,  E)에 대해  G 안의 모든 정점과 모든 연결선이 포함되는 순환을 말한다. 

(3) 또한 오일러 순환이 포함된 그래프를 오일러 그래프(Euler graph)라고 한다. 

정의2

그래프에서  연필을  떼지  않고  모든  간선(edge)을  오직  한번만  지나는  것을  한붓그리기(traversable)라고 한다. 연결된 그래프에서 한붓그리기가 가능하려면 시작정점과 끝나는 정점을 제외한 모든 정점의 차수가 짝수이어야 한다. 

정의2

해밀턴의 성질을 만족하는 특수한 형태의 그래프인 해밀턴 경로와 해밀턴 순환(circuit, 또는 순회)은 다음과 같이 정의된다. 

(1) 해밀턴 경로(Hamiltonian  path)란 그래프 G=(V,  E)에 대해  G 안의 임의의 정점에서 출발하여 그래프의 각 정점이 한 번씩만 나타나도록 만들어진 경로를 말한다. 즉, 그래프에서 모든 정점을 오직 한 번씩만 지나지만 시작점으로 돌아오지 않는 경로를 의미한다. 

(2) 해밀턴 순환(Hamiltonian  circuit,  Hamiltonian  cycle)란 그래프  G=(V,  E)에 대해  G 안의 임의의 정점에서 출발하여 그래프의 각 정점이 한 번씩만 지나고 다시 시작 정점으로 돌아오는 순환을 말한다. 해밀턴 순회를 찾을 때 루프는 사용될 수 없고, 한 쌍의 정점 사이에는 단 하나의 간선만 사용될 수 있다. 또한 해밀턴 순환이 포함된 그래프를 해밀턴 그래프(Hamiltonian graph)라고 한다. 

. 해밀턴 퍼즐의 그래프 

. 해밀턴은  19세기 중반  12면체의 입체도형에 도시 이름을 주고 어떤 도시에서 출발하여 주어진 길을 따라 각 도시를 한 번만 방문하고 다시 출발 도시로 돌아오는 퍼즐을 제시 

2. 그래프의 응용 

. 그래프의 응용 분야 

. 데이터 흐름 모델(Data  flow model), 

. 스케쥴링 알고리즘(scheduling  algorithm), 

. 논리회로설계(logic  circuit  design), 

. 통신네트워크(communication  network), 

. 순서도(flow  chart), 

. 정렬(sorting), 

. 탐색(searching), 등 

다익스트라 알고리즘(dijkstra  algorithm) 

  : 어떤 간선도 음수 값을 갖지 않는 방향그래프에서 주어진 출발점과 도착점 사이의 최단경로 문제를 푸는 알고리즘 

.  [알고리즘1]에서 주어진 방향그래프 G=(V,  E)에서  v={1,2,3,…,  n}이고, 점{1}이 출발점이라고 가정한다. 

. 출발점으로 부터 거리가 최소로 알려진 점들의 집합  S를 유지함으로써 가장 짧은 거리를 가지는 나머지 점  v를 차례로  S에 포함시킨다. 

. 점  i에서 점  j로 가는 거리를  C[i,  j]로 나타내는데 만약  i에서  j로 가는 경로가 없으면 거리는 ∞가 된다. 

. D[i]는 출발점에서 현재점  i에 이르는 가장 짧은 거리를 나타낸다. 

2) 해밀턴 순환의 응용  : 순회판매원 문제(traveling  salesperson  problem) 

  : 방문해야 할 도시들과 이들 사이의 거리가 주어졌을 경우, 순회판매원이 어떤 특정한 도시를 출발하여 어떠한 도시도 두 번 방문함이 없이 모든 도시를 거쳐 처음 출발한 도시로 되돌아올 때, 총 여행거리가 최소가 되는 경로를 찾는 문제 

  . 최근접 이웃방법(nearest  neighbor method) 이용 

  :  임의로  선택한  꼭지점에서  출발하여  그  꼭지점과  가장  가까운  꼭지점을  찾아서  연결하고, 그 경로를 첨가하는 과정을 반복하며 마지막에 순회를 형성하도록 하는 방법

1. 그래프의 표현방법

그래프의 표현방법 

(1) 인접행렬(adjacency matrix) 

(2) 인접리스트  (adjacency  list) 

임의의 연결선  (u,  v)∈E에 대하여  u와  v를 서로 인접했다(adjacent)라고 하고, 정점  u와  v를 연

결선  e의  끝점(end  point)이라고  한다.  또  정점  u가  연결선  e의  끝점이면  e는  u에  접했다

(incident, 또는 부속)라고 한다. 

2) 인접리스트(adjacency  list) 

. 그래프의 한 정점에서 연결되어 있는 정점들을 하나의 연결리스트로 표현하는 방법 

. 인접행렬의 n행들의 값을  n개의 연결 리스트로 나타낸다. 

. 인접리스트 방식은 각 정점에 인접한 정점들을 순서와 상관 없이 일일이 열거하는 것이다. 

. 인접리스트로 나타낼 때 헤드(head)에서 출발한 각 정점은 적어도 두 개의 필드를 갖는다. 

. 필드의 구성 

. 시작 정점  : 헤드(head) 

. 첫 번째 필드  : 정점(vertex) 

. 두 번째 필드  : 링크(link)필드 

3) 정규 그래프

정의3

그래프  G의 모든 정점들이 같은 차수를 갖는다면  G를 정규그래프(regular  graph)라고 한다. 이

때 차수가  k값을 가지면  k-정규그래프라고 한다.

. 정규 그래프(regular graph) 

. 그래프 G 의 모든 정점들이 같은 차수를 갖는 경우 

.  K-정규 그래프(regular  graph) 

. 차수가  k인 정규그래프 

그래프의 기본개념과 용어

1. 그래프의 기본개념

. 연결되어 있는 객체 간의 관계를 표현하는 비선형자료구조(non-linear  data  structure) 

. 가장 일반적인 자료구조 형태 

. 전기회로의 소자 간 연결 상태 

. 운영체제의 프로세스와 자원 관계 

. 큰 프로젝트에서 작은 프로젝트 간의 우선순위 

. 지도에서 도시들의 연결 상태 

 그래프 이론의 출발 

.  18세기의  스위스의  수학자  오일러(Leonard  Euler)에  의해  시작되었다.  쾨니히스베르크

(Konigsberg)다리문제는 <그림  1>과 같이 두개의 섬과 강둑 사이를 연결하는  7개의 다리가 있

을 때 각 다리를 똑 한번만 건너는 경로를 찾는 문제이다. 

2. 그래프의 용어 

. 단순그래프(simple  graph) 

한 쌍의 정점 사이에 많아도 하나의 연결선으로 이루어진 그래프로서, 자기 자신으로의 연결선

이 없는 그래프 또는 다중그래프가 아닌 그래프 

. 다중그래프(multi-graph) 

단순 그래프의 확장으로 한 쌍의 꼭지점 사이에 연결선의 개수의 제한이 없는 일반적인 그래

프 즉, 두 정점 사이에 두 개 이상의 에지가 있는 그래프 

 차수(degree) 

. 그래프  G 의 임의의 정점  v를 끝점으로 하는 에지(edge)의 수, 즉 한 정점에 연결되어 있는 에지의 수를 의미 

.  deg(v) 표시 

정점 차수의 특성 

. 어떤 그래프에 있는 모든 정점의 차수의 합은 이 그래프가 가진 에지의 수의  2배가 된다. 따

라서, 정점의 차수의합은 짝수가 되면, 차수가 홀수인 정점의 수도 짝수가 된다는 성질을 가진다. 

방향그래프에 있어서 정점  v의 차수는 진입차수(in-degree, 내차수)와 진출차수(out-degree, 외차수)로 나타낸다. 

. 정점  v의 진입차수  : 정점  v를 끝점(end-vertex)으로 하는 에지(edge)들의 수, 즉 한 꼭지점으로 들어오는 에지의 수 

. 정점  v의 진출차수  : 정점  v를 시작점(start-vertex)으로 하는 에지(edge)들의 수, 즉 한 정점에서 나가는 에지의 수. 

주어지 그래프에 루프(loop)가 존재할 경우, 루프는 자기 자신으로 되돌아오는 에지(edge)이므로 차수는 항상  2이다. 

행렬식

1. 행렬식의 기본개념

행렬식의 일반적인 성질을 살펴보면 다음과 같다. 

.  n×n행렬 A에서 임의의 두 행(또는 열)이 같으면 행렬식의 값은  0이다. 

.  n×n행렬  A의  임의의  두  행(또는  열)을  서로  바꾸어서  만든  행렬을  B라고  하면 

Det(B)=-Det(A)이다. 

. 행렬 A의 행렬식의 값은 그 전치행렬의 행렬식의 값과 같다. 즉, Det(A)=Det(AT)이다. 

.  A와  B가  n×n행렬 이면 곱의 행렬식은 행렬식의 곱과 같다. 즉, Det(AB)=Det(A).Det(B)가 성립

한다. 

. 행렬식의 어떤 행(또는 열)의 각 원소에 같은 수  k를 곱하여 얻은 행렬식은 처음 행렬식에  k

를 곱한 것과 같다. 

.  n×n행렬 A 의 한 행  (또는 열)에 있는 모든 원소가  0이면 Det(A)=0이다. 

. 한 개의 행(또는 열)에  k배를 하여 다른 행(또는 열)에 더하여 만든 행렬식은 원래의 행렬식

과 같다.

2) 역행렬

3) 연립일차방정식

2. 부울행렬

행렬과 행렬의 연산

1. 행렬의 기본개념

. 벡터(vector)  :  1차원 배열의 형태로 나타내는 것

. 행 벡터(row  vector)  : 행렬의 특수한 형태로서  1행으로 된 행렬, 

. 열 벡터(column  vector)  :  1열로 된 행렬 

. 스칼라(scalar)  : 행렬과 벡터의 각 원소

2. 행렬의 연산

정의2

두 행렬이 같기 위해서는 행과 열의 개수가 각각 같고 대응하는 원소도 같아야 한다. 

정리1

행렬의 합과 스칼라 곱은 같은 크기의 행렬  A,  B,  C 와 어떤 상수  c,  d 가 주어졌을 때 다음과 

같은 연산 법칙들을 만족한다.  (여기서 O는 행렬의 모든 원소가  0인 행렬이다.) 

. A+B=B+A  (덧셈의 교환법칙) 

. A+(B+C)=(A+B)+C  (덧셈의 결합법칙) 

. A+O=A=O+A  (덧셈의 항등 법칙) 

. A+(-A)=O=(-A)+A  (덧셈의 역원) 

.  (-1)A =-A 

.  c(A+B)=cA+cB  (스칼라 곱의 배분법칙) 

.  (c+d)A =cA+dA  (스칼라곱의 배분법칙) 

.  (cd)A=c(dA) 

정리2

A가  m×n행렬이고  ,  행렬  B와  C는  행렬의  합과  곱에서  정의된  크기를  만족한다고  가정하자. 

이때  k가 어떤 스칼라 값일 때 다음과 같은 연산 법칙들을 만족한다. 

.  (AB)C=A(BC)  (곱셈의 결합법칙) 

. A(B+C)=AB+AC  (곱셈의 배분법칙) 

.  (B+C)A=BA+CA  (곱셈의 배분법칙) 

.  k(AB)=(kA)B=A(kB)  (스칼라 곱) 

.  In A=A=AIn  (행렬 곱셈의 항등식) 

3. 여러 가지 행렬

추상화

소프트웨어 설계 

개요 

 소프트웨어를 개발하기 위한 청사진을 만들기 위한 반복되는 과정 

 개발하고자 하는 것을 공학적으로 의미 있게 표현한 것 

 설계는 문제를 푸는 활동(Problem Solving Activity) 

 요구공학과정의 소프트웨어 요구사항 명세서를 받아서 자료구조, 시스템구조, 인터페이스표현, 구성요소 등의 

4가지 레벨의 설계로 자세히 변화 

 각 설계 행위 도중에 고품질을 위한 설계개념과 원리를 적용 

 소프트웨어설계는 매우 귀찮은 문제(Wicked Problem) 

정의 

사용자의 요구를 만족시키기 위하여 제약 조건이 반영된 구현 대안을 창출하는 일 

소프트웨어의 시스템의 내부를 설계 

 모듈의 구조 

 자료 구조 

 알고리즘 설계 

소프트웨어 설계란? 

설계 시 고려 사항들 

모듈(Module) 

 독립적으로 처리할 수 있는 구별단위(Identifiable Unit), 그 단위들은 하나 이상의 프로시저들을 포함 

 모듈의 개념 사용 

 모듈은 소프트웨어에 꼭 나타남 

모듈 분할의 바람직한 방법의 특징 

 설계의 질을 측정 시 사용 

 유지보수와 재사용 용이 

 영향을 주는 설계 형태 

– 추상화(Abstraction) 

– 모듈화(Modularity) 

– 정보 은폐(Information Hiding) 

– 복잡도(Complexity) 

– 시스템 구조(System Structure) 

추상화(Abstraction)  

정의 

복잡한 현상을 이해하는 과정에서 인간의 이해력을 돕는 도구 

추상 

현실세계에 있는 특정한 범위의 대상물(Things), 상태 또는 과정 등에서 일어나는 세부적인 사항이 아닌 본질적인 사항, 

유사한 점을 인식하여 주의를 집중하는 것 

목적 

추상화 기술을 통해 사물을 간결하게 표시 

효과 

추상화의 개념 

 기계어의 어셈블러에 의한 기호화부터 시작하여 같은 형태의 변수로 묶은 배열의 추상화 

 프로그램의 구조도 알기 쉽게 함 

- 함수, 서브루틴 

 자연언어를 사용하여 모듈 구조나 알고리즘을 알기 쉽게 함 

계층적 기능 분할 모듈 

 Top 모듈은 개념적인 내용 

 밑으로 내려갈수록 단계적으로 상세화 

 독립성이 높은 범용성이 있는 모듈을 생성하는 효과 

일반화시킨 기능 ->독립성 높은 모듈 

상호작용을 제거 ->범용성 있는 모듈 

형태 

절차적 추상화(Procedural Abstraction) 

 분할 타입 

     - 하향식 분할(Top-down), 단계적(Stepwise) 분할 

 절차적 개념은 분할 처리의 결과로부터 하위 문제들의 표기법 제공 

 절차적 추상화에서 절차의 이름은 처리행위의 응답(Sequence of Action)으로 표시 

 소프트웨어 설계할 때 가장 간단한 형태로 입력 처리와 출력에 관한 설계로 분할 

 프로그램의 제어구조의 계층을 찾는 것이 목적 

데이터 추상화(Data Abstraction) 

 프로그램의 데이터의 계층을 찾는 것이 목표 

 프로그램의 언어는 숫자나 진리 값을 원시 데이터구조에 제공 

 데이터구조를 좀더 복잡하게 만드는 스택이나 이진트리와 같은 블록도 사용 

 데이터추상화를 응용한 것을 때때로 객체지향 설계라 함 

- 객체의 타입과 연관된 연산(Associated Operation)이 하나의 모듈로 캡슐화되어 있음 

기능 추상화(Function Abstraction) 

 입력자료를 출력자료로 변환하는 과정을 추상화 

 부프로그램의 시그너처와 기능만 생각 

제어 추상화(Control Abstraction) 

외부 이벤트에 대한 반응을 추상화 

2 모듈화

설계작업 

특징 

프로그래밍에서의 모듈

구조 

근본은 주 모듈 

분할된 각각은 하위 모듈 

모듈 사이의 인터페이스 

모듈 사이의 종속 관계 

 상위 모듈이 주 모듈이 됨 

 상위 모듈이 하위 모듈을 이용 

 모듈 사용 시 상위 모듈을 「 호출 」 또는 「 Call 한다. 」라고 함 

 이때 모듈 사이에는 파라미터의 주고 받음이 이루어짐 

모듈 응집력(Cohesion) 

모듈 안의 구성 요소들이 공동의 목적을 달성하기 위하여 관련되어 있는 정도 

모듈 내에서의 관련성의 척도 

목표 

한 모듈이 단일 기능을 갖도록 설계 

예 – finishup 

       최종 보고서를 출력하고, 계산 결과를 디스크에 저장

응집력의 7가지 단계 

기능적(Functional)   1 

모듈의 기능이 한 문장으로 떨어짐 

예 – 판매세금 계산  

순차적(Sequential)   2 

작업의 결과가 다른 작업에 입력 

예 – 거래를 읽고 마스터 파일을 변경  

교환적(Communicational)   3 

동일한 입력과 출력을 사용하는 작업의 모임 

예 – 출력 파일을 출력하고 저장  

절차적(Procedural)  4 

같은 범주에 속하는 일들이 순서적으로 수행 

예 – restart-RTN 

총계를 출력하고, 화면을 지우고 메뉴를 뿌리고,  메뉴 선택을 받음 

시간적(Temporal)   5 

프로그램 초기화 

논리적(Logical)  6 

유사한 성격의 작업을 한 모듈로 모음 

우연적(Coincidental)  7 

아무 관련 없는 작업을 한 모듈에 모음 

결합도(Coupling) 

상호 모듈 간의 연결 강도 측정, 모듈과 모듈 간 관련성 척도 

독립적인 모듈이 되기 위해서는 모듈 간의 결합도가 낮은 설계가 바람직함 

결합도의 타입 정의 

내용 결합도(Content Coupling)  

어떤 모듈이 다른 모듈에 직접적인 영향을 미치는 것 

공유 결합도(Common Coupling)  

두 모듈 간 데이터를 나누는 것 

외부 결합도(External Coupling)  

모듈이 외부 개체(파일)와 통신하는 것 

제어 결합도(Control Coupling)  

하나의 모듈이 다른 모듈에게 필요한 제어 정보를 전달하는 경우 

스탬프 결합도(Stamp Coupling)  

완전한 자료 구조가 한 모듈에서 다른 모듈로 전달되어지는 경우에 해당 

자료 결합도(Data Coupling)  

자료구조는 모듈 간의 단순한 자료가 전달되어지는 경우에 해당 

모듈의 독립성 

모듈간의 결합도가 약하고, 모듈 구성 요소 간의 응집력이 강한 단순 인터페이스의 중요성 

 프로그래머 간의 대화가 단순해짐 

 정확성 증명(Correctness Proofs)은 유도를 좀더 쉽게 함 

 어떤 변화가 다른 모듈들 간에 전해지는 것을 줄임으로써, 유지비용을 줄일 수 있음 

 모듈 간의 재사용성(Reusability)을 증가시킬 수 있음 

 모듈의 판독성(Comprehesibility) 향상 

 경험적인 학습(Empirical Studies)은 인터페이스의 약한 결합도와 강한 응집력, 이런 속성을 가지지 않는 

것보다 더 에러가 적다는 것을 보여줌 

3. 정보은폐

개념 

모듈 사이의 정보(데이터와 기능)의 상호작용을 제거하기 위해 모듈을 이용하기 위하여 필요한 최소한의 정보만 

보이고, 그 외의 자세한 것은 외부의 모듈로부터 액세스할 수 없도록 감춤 

특징 

각 모듈의 자세한 처리 내용이 시스템의 다른 부분으로부터 감추어져 있어야 함 

각 모듈이 다른 모듈에 구애 받지 않고 설계 

인터페이스가 모듈 안의 구체적 사항을 최소로  반영 

전역변수가 없어야 함 

모듈 단위의 수정, 시험, 유지보수에 큰 장점 

모듈 설계 평가에 기초 

여러 가지 함수

1. 합성함수