알고리즘 알고리즘

(1)

알고리즘 알고리즘

영남대학교 컴퓨터공학과 조행래

(IT관 215호, 전화: 810-2559 l h h @ k )

email: hrcho@yu.ac.kr)

(2)

강의의 성격 강의의 성격



자료구조의 후속 과목



파일 처리



알고리즘 설계 방법론

(3)

강의의 주요 내용(1) 강의의 주 내용(1)

 보조기억 장치 특성 및 파일 처리를 위한 API 이해

 보조기억장치를 이용한 자료구조

 대량의 데이터에 대한 정렬/탐색 알고리즘

 분할정복 방법, Greedy 방법, 동적 프로그래밍 등을 이용 한 알고리즘 설계 방법론

(4)

강의의 주요 내용(2) 강의의 주 내용(2)

 File 처리의 개념

l 의 저장 방식 /O h d

 File의 저장 방식, I/O Processing, Access Method

 External Sorting Indexing

 Indexing

 Hashing

 Search Structures: AVL Tree 2-3 Trees B-Tree

 Search Structures: AVL Tree, 2 3 Trees, B Tree, …

 Dynamic Programming, Divide-And-Conquer

 NP-Hard and NP-Complete Problemsp

(5)

수업 목표 수업 목

 보편적이면서도 응용 범위가 넓은 여러 분야의 기본적인 알고리즘들을 설계하고 분석하는 방법을 설명

알고리즘들을 설계하고 분석하는 방법을 설명

 보조기억장치의 물리적 특성을 이해

 대용양의 데이터에 대한 정렬대용양의 데이터에 대 정렬/탐색 알고리즘, 분할정복/ 색 알 리 , 할정복 방법, Greedy 방법, 동적 프로그래밍, 그리고 NP-완전문제 등을 이해

(6)

ABEEK에 따른 학습성과 목표 ABEEK에 따른 학습성과 목

 수학, 기초과학, 공학의 지식과 정보기술을 응용할 수 있 는 능력 30%

는 능력: 30%

 자료를 이해하고 분석할 수 있는 능력 및 실험을 계획하고

 자료를 이해하고 분석할 수 있는 능력 및 실험을 계획하고 수행할 수 있는 능력: 20%

 현실적 제한조건을 반영하여 시스템, 요소, 공정을 설계할 수 있는 능력: 30%

 공학 문제들을 인식하며, 이를 공식화하고 해결할 수 있는 능력: 20%

능력: 20%

(7)

학습성과 달성을 위한 수업진행 방법 학습성과 달성을 위한 수업진행 방법

 수학, 기초과학, 공학의 지식과 정보기술을 응용할 수 있는 능력 저장장치의 특성을 이해하고 이를 고려하여 알고리즘을 작성할

 저장장치의 특성을 이해하고 이를 고려하여 알고리즘을 작성할 수 있는 방법을 배운다.

자료를 이해하고 분석할 수 있는 능력 및 실험을 계획하고 수행

 자료를 이해하고 분석할 수 있는 능력 및 실험을 계획하고 수행

 다양한 알고리즘의 복잡성을 정성적/정량적으로 분석할 수 있고, 장.단점을 이해

 현실적 제한조건을 반영하여 시스템, 요소, 공정을 설계

 저장장치의 HW적 제한조건과 데이터의 특성을 고려하여 알고리

 저장장치의 HW적 제한조건과 데이터의 특성을 고려하여 알고리 즘을 정의하고, 이를 다양한 프로그래밍언어로 개발

 공학 문제들을 인식하며 이를 공식화하고 해결할 수 있는 능력

 공학 문제들을 인식하며, 이를 공식화하고 해결할 수 있는 능력

 복잡한 응용분야에 대한 대표적인 접근방법(동적 프로그래밍, 분 할정복, Greedy 방법 등)을 이해하며, 이러한 접근방법에 따라 알 고리즘을 작성

고리즘을 작성

(8)

교재 재

 E. Horowitz 외 2명, Fundamentals of Data Structures in C, Comp te Science P ess 1^st Edition

Computer Science Press, 1^st Edition

 E. Horowitz 외 2명, Fundamentals of Data Structures in C,

 E. Horowitz 외 2명, Fundamentals of Data Structures in C, Silicon Press, 2^nd Edition

 이석호, 파일처리, 정익사

M F lk d B Z lli k Fil St t Addi W l

 M. Folk and B. Zoellick, File Structures, Addison Wesley

 R Neapolitan and K Naimipour Foundations of

 R. Neapolitan and K. Naimipour, Foundations of

Algorithms using Java Pseudocode, Jones and Bartlett Pub.

(9)

기타 기타

 자료구조를 수강한 컴퓨터공학과 3학년 학생을 대상으로

하여 진행한다 하여 진행한다.

 타과 학생 및 4학년 학생들의 관리?

 수강생들은 강의 시간에 익힌 개념을 실습하기 위해 N번 의 (N≒6) 프로그래밍 과제를 제출하도록 한다.

 프로그래밍 과제에서 다양한 프로그래밍 언어 사용: C(2회), C++(2회), Java(2회)

숙제 제출 및 검사 방법

 숙제 제출 및 검사 방법

 프로그램 복사에 대한 처리 방법

(10)

평가 평가

 수학, 기초과학, 공학의 지식과 정보기술을 응용할 수 있는 능력 중간/기말시험 프로그램 숙제(Shell Command 구현)

 중간/기말시험, 프로그램 숙제(Shell Command 구현)

 자료를 이해하고 분석할 수 있는 능력 및 실험을 계획하고 수행

 중간/기말시험

 현실적 제한조건을 반영하여 시스템, 요소, 공정을 설계, ,

 중간기말시험, 프로그램 숙제(순차파일 구현, B+ 트리 구현)

 공학 문제들을 인식하며 이를 공식화하고 해결할 수 있는 능력

 공학 문제들을 인식하며, 이를 공식화하고 해결할 수 있는 능력

 중간기말시험, 프로그램 숙제(동적 프로그래밍/분할정복/Greedy 중 한 분야 선택)

 중간시험(35) + 기말시험(35) + 실습 숙제(30) = 100(상대 평가)

 1회 결석시 2점 감점

(11)

주별 강의 내용 주별 강의 내용

1 Introduction 9 B Tree

2 Secondary Storage 10 B⁺ Tree 3 File Processing using

C/C++/Java 11 Hashing (1)

Hashing (2) 4 Sequential File Structures 12 Hashing (2)

Divide and Conquer 5 External Sorting 13 Dynamic Programming 6 Search Structures (1) 14 Greedy Algorithm

NP Complete Problems Search Structures (2)

7 Search Structures (2),

Indexing의 개념 15 기말 시험

8 중간 시험 16

(12)

Chapter 1 Chapter 1

Introduction to File

Structures

(13)

1. The Heart of File Structure Design . e ea t o e St uctu e es g

 Motivation

 Disks are slow.

 RAM 속도: 10 ~ 20 nanoseconds (DDR3 SDRAM) Di k 속도 10 20 illi d

 Disk 속도: 10 ~ 20 milliseconds Disk의 장점

 Disk의 장점

 Enormous capacity at much less cost than RAM

 Non-volatile storage device

 Non volatile storage device

 Goal

Accessing to all the capacity without making our

applications spend a lot of time waiting for the disk

(14)

2. A Short History of File Structure Design 2. A Short History of File Structure Design

 General goal of research in file structures

 One access to the disk. 

Ideal

Only two or three trips to the disk 

Practical

 Only two or three trips to the disk. 

Practical

 Grouping information for fewer trips

☞ File 의 역동성 ( File 내용 혹은 크기의 변화 )

(15)

History sto y

 Sequential file in tape device

 Direct access of disk using

index

 Simple index (sequentially stored)

 Tree structured index

Binary search tree AVL tree

 Binary search tree, AVL tree

 B-tree, B⁺-tree: log_k

N

access

 Hashing

 Extendible, Dynamic hashing

 Multi-key access method

 Spatial access method: R-tree K-D-B tree

 Spatial access method: R tree, K D B tree

(16)

3. A Conceptual Toolkit: File Structure Literacy

Literacy

 File structure를 구성하는데 사용되는 개념들

S i l h d

 Sequential Access Method

 Indexed Sequential Access Method Direct Access Method

 Direct Access Method

 Disk I/O 를 줄이기 위해 사용되는 개념들

 Buffering

 Blockingg

 Bucket Concept

 Splitting & Merging

(17)

접근 방향

 앞의 개념들을 완전 이해

새로운 응용 분야에 활용할 수 있는 능력 배양

접근 방향

 새로운 응용 분야에 활용할 수 있는 능력 배양

 기존 상용 package 들의 사용 능력 함양