알고리즘(Algorithm) 유비쿼터스 컴퓨팅학과 교수 송 창근 E-mail : cgsong@hallym.ac.kr http://web.hallym.ac.kr/~cgsong
강의 진행 방법 강의 : 2시간 강의실에서 offline으로 강의 실습 : 2시간 실습실에서 offline으로 실습 교과서의 내용을 설명함. E-campus의 게시판/교과목 공지사항 참조 실습 : 2시간 실습실에서 offline으로 실습 교과서에 소개된 프로그램을 실습함. E-campus의 게시판/실습 게시판 활용 참고 자료 : http://www.hallym.ac.kr/~cgsong/korean/lecture/lec_struc2_past.htm (2005년도)
교재 및 참고문헌 부 교재 주 교재 원저: Data Structures with Java, Hubbard & Hurray 이 석호, 자료구조와 자바, 정익사 부 교재 Java를 이용한 자료구조, 홍릉출판사, 나 연묵, 채진석, 박영배 공역 원저: Data Structures with Java, Hubbard & Hurray Fundamentals of Data Structures in C 혹은 C++, E. Horowitz, S, Sahni, Computer Science Press.
평가 방법 중간고사 (30%), 기말고사(30%), 실습 (10%) 과제(30%),출석(10%, 보너스) 과제는 프로그래밍 리포트 2회 이상 포함 4-6회. 결석 시간별에 따라서 출석 점수를 계산함. 결석 2시간 당 -1점씩. 15시간 이상 결석 시 F 학점 처리 상대평가 A (20%), B(30%), C(30%), D(20%)
주별 강의 계획 1주 : 1학기 내용 복습, 강의 소개 등 2주 : 트리(Tree) 및 이진 트리 (Binary Tree)의 정의 및 특징 3주 : 이진 트리(Binary Tree)의 주요 연산 및 쓰레드 인진트리 4주 : 이원 탐색 트리 정의, 검색, 삽입, 삭제 구현 및 검색 등 5주 : 힢(Heap)의 정의 및 기본 연산 구현 6주 : 우선 순위 큐 및 선택 트리 7주 : 그래프 (Graph)의 정의, 특징, 표현 및 구현, 8주 : 중간고사 9주 : 그래프의 순회, 연결요소, 신장 트리 10주 : 최소비용 신장 트리, 최단경로 알고리즘 11주 : 위상순서 찾기, 임계 경로 구하기 12주 : 정렬 (선택, 버블, 삽입, 합병, 퀵) 13주 : 정렬 (히프, 쉘, 기수, 트리) 14주 : AVL 트리 보충기간 주 : Huffman code, 해쉬테이블(Hash Table) 및 총정리 15주 : 기말고사 실습 계획은 강의 계획서를 참조하기 바랍니다. 다소 변동이 있을 수 있습니다.
자료구조론(복습) 선형 자료 구조 선형 리스트의 구현 특별한 선형 리스트 선형 리스트 (Liner list, Ordered list) 구체적인 예: 다항식, 희소 행렬 선형 리스트의 구현 배열(Array) 대 연결 리스트 순차 표현 (Sequential Representation) 연결 구현 (Linked Representation) 특별한 선형 리스트 스택 : 순차표현, 복수 스택, 연결 표현, 스택의 이용 큐 : 순차 표현(원형큐), 복수 큐, 연결 표현, 큐의 이용, 우선 순위큐
알고리즘 (개요) 비선형(Non linear) 자료 구조 트리 (Tree) 그래프 (Graph) 정렬 (Sorting) 트리, 그래프, 가중치 그래프 비선형 자료 구조의 활용 : 정렬, 탐색 트리 (Tree) 트리의 표현, 포리스트 이진 트리 이원 탐색 트리, 히프, 선택 트리 그래프 (Graph) 그래프의 표현, 순회, 활용 가중치 그래프 (Network) 최소비용 신장 트리, 최단 경로, 위상 순서, 임계경로 정렬 (Sorting) 선택, 버블, 삽입, 합병, 퀵, 히프, 쉘, 기수, 트리 정렬 알고리즘 균형 탐색 (Searching) 트리 AVL 트리, 스플레이, 2-3, 2-3-4, 레드-블랙 트리