강의의 성격 강의의 성격
자료구조의 후속 과목
파일 처리
알고리즘 설계 방법론
강의의 주요 내용(1) 강의의 주 내용(1)
보조기억 장치 특성 및 파일 처리를 위한 API 이해
보조기억장치를 이용한 자료구조
대량의 데이터에 대한 정렬/탐색 알고리즘
분할정복 방법, Greedy 방법, 동적 프로그래밍 등을 이용 한 알고리즘 설계 방법론
강의의 주요 내용(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
수업 목표 수업 목
보편적이면서도 응용 범위가 넓은 여러 분야의 기본적인 알고리즘들을 설계하고 분석하는 방법을 설명
알고리즘들을 설계하고 분석하는 방법을 설명
보조기억장치의 물리적 특성을 이해
보조기억장치의 물리적 특성을 이해
대용양의 데이터에 대한 정렬대용양의 데이터에 대 정렬/탐색 알고리즘, 분할정복/ 색 알 리 , 할정복 방법, Greedy 방법, 동적 프로그래밍, 그리고 NP-완전문제 등을 이해
ABEEK에 따른 학습성과 목표 ABEEK에 따른 학습성과 목
수학, 기초과학, 공학의 지식과 정보기술을 응용할 수 있 는 능력 30%
는 능력: 30%
자료를 이해하고 분석할 수 있는 능력 및 실험을 계획하고
자료를 이해하고 분석할 수 있는 능력 및 실험을 계획하고 수행할 수 있는 능력: 20%
현실적 제한조건을 반영하여 시스템, 요소, 공정을 설계할 수 있는 능력: 30%
공학 문제들을 인식하며, 이를 공식화하고 해결할 수 있는 능력: 20%
능력: 20%
학습성과 달성을 위한 수업진행 방법 학습성과 달성을 위한 수업진행 방법
수학, 기초과학, 공학의 지식과 정보기술을 응용할 수 있는 능력 저장장치의 특성을 이해하고 이를 고려하여 알고리즘을 작성할
저장장치의 특성을 이해하고 이를 고려하여 알고리즘을 작성할 수 있는 방법을 배운다.
자료를 이해하고 분석할 수 있는 능력 및 실험을 계획하고 수행
자료를 이해하고 분석할 수 있는 능력 및 실험을 계획하고 수행
다양한 알고리즘의 복잡성을 정성적/정량적으로 분석할 수 있고, 장.단점을 이해
현실적 제한조건을 반영하여 시스템, 요소, 공정을 설계
저장장치의 HW적 제한조건과 데이터의 특성을 고려하여 알고리
저장장치의 HW적 제한조건과 데이터의 특성을 고려하여 알고리 즘을 정의하고, 이를 다양한 프로그래밍언어로 개발
공학 문제들을 인식하며 이를 공식화하고 해결할 수 있는 능력
공학 문제들을 인식하며, 이를 공식화하고 해결할 수 있는 능력
복잡한 응용분야에 대한 대표적인 접근방법(동적 프로그래밍, 분 할정복, Greedy 방법 등)을 이해하며, 이러한 접근방법에 따라 알 고리즘을 작성
고리즘을 작성
교재 재
E. Horowitz 외 2명, Fundamentals of Data Structures in C, Comp te Science P ess 1st Edition
Computer Science Press, 1st Edition
E. Horowitz 외 2명, Fundamentals of Data Structures in C,
E. Horowitz 외 2명, Fundamentals of Data Structures in C, Silicon Press, 2nd 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.
기타 기타
자료구조를 수강한 컴퓨터공학과 3학년 학생을 대상으로
하여 진행한다 하여 진행한다.
타과 학생 및 4학년 학생들의 관리?
수강생들은 강의 시간에 익힌 개념을 실습하기 위해 N번 의 (N≒6) 프로그래밍 과제를 제출하도록 한다.
프로그래밍 과제에서 다양한 프로그래밍 언어 사용: C(2회), C++(2회), Java(2회)
숙제 제출 및 검사 방법
숙제 제출 및 검사 방법
프로그램 복사에 대한 처리 방법
평가 평가
수학, 기초과학, 공학의 지식과 정보기술을 응용할 수 있는 능력 중간/기말시험 프로그램 숙제(Shell Command 구현)
중간/기말시험, 프로그램 숙제(Shell Command 구현)
자료를 이해하고 분석할 수 있는 능력 및 실험을 계획하고 수행
중간/기말시험
현실적 제한조건을 반영하여 시스템, 요소, 공정을 설계, ,
중간기말시험, 프로그램 숙제(순차파일 구현, B+ 트리 구현)
공학 문제들을 인식하며 이를 공식화하고 해결할 수 있는 능력
공학 문제들을 인식하며, 이를 공식화하고 해결할 수 있는 능력
중간기말시험, 프로그램 숙제(동적 프로그래밍/분할정복/Greedy 중 한 분야 선택)
중간시험(35) + 기말시험(35) + 실습 숙제(30) = 100(상대 평가)
1회 결석시 2점 감점
주별 강의 내용 주별 강의 내용
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
Chapter 1 Chapter 1
Introduction to File
Structures
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
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 내용 혹은 크기의 변화 )
History sto y
Sequential file in tape device
Direct access of disk using
index
Simple index (sequentially stored)
Simple index (sequentially stored)
Tree structured index
Binary search tree AVL tree
Binary search tree, AVL tree
B-tree, B+-tree: logk
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
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 를 줄이기 위해 사용되는 개념들
Disk I/O 를 줄이기 위해 사용되는 개념들
Buffering
Blockingg
Bucket Concept
Splitting & Merging
접근 방향
앞의 개념들을 완전 이해
새로운 응용 분야에 활용할 수 있는 능력 배양
접근 방향
새로운 응용 분야에 활용할 수 있는 능력 배양
기존 상용 package 들의 사용 능력 함양
