조합과 순열 생성 알고리즘의 개선 = Enhancement of Combination and Permutation Generation Algorithms

http://www.riss.kr/link?id=T13218045

• 저자 : 장재수
• 형태사항 : 96 ; 26 cm

• 일반주기 :

  지도교수: 서창진

• 학위논문사항 : 학위논문(박사)-- 숭실대학교 대학원 : 컴퓨터학과(일원) 컴퓨터통신 2013. 8
• 발행국 : 서울
• 언어 : 한국어
• 출판년 : 2013
• 주제어 : 조합론, 조합, 순열, r-순열, 조합생성 알고리즘, 순열생성 알고리즘, combinatorial, combination, permutation, r-permutation, combination generation algorithms, permutation generation algorithms

• 소장기관 :

  • 숭실대학교 도서관

 

 

감사의 글

 

To my family and professor,

for their love and support.

& my lovely wife and pretty angels.

Special thanks to HyungMin, JaeWon, JinSook.

 

J.S.Jang

 

 

 

 

 

• This paper deals with programs and algorithms that generate a full data set as a list of combinations and permutations according to the basic combinatorial requirements of combination, permutation, and r-permutation. The total data list generated by t...
• This paper deals with programs and algorithms that generate a full data set as a list of combinations and permutations according to the basic combinatorial requirements of combination, permutation, and r-permutation. The total data list generated by the programs and algorithms for combination and permutation is used in the total inspection that the total data testing method for quality inspection or selecting the simulation input value. The run-time of the algorithms for combination and permutation exponentially raises when input value increases. We propose an improved algorithm having a shorter run time.
  We conducted a preliminary study by surveying programs for existing permutation and combination algorithms that satisfy combination, permutation, and r-permutation solutions. Then, we made the programs to execute and explained the contents and operation of the algorithms. Further, we organized the programs using pseudo-codes.
  With regard to combination, permutation, and r-permutation algorithms, we identify three properties: lexicographical sorting of the total data, total data generation ability according to the order of input values, and recursiveness of the algorithms. We also compared the run-times of the programs and then identified the relationship between the input values and the performance.
  We propose improved programs with shorter run-times than existing algorithms, and we also identify the characteristics of the algorithms and degree of performance improvement through performance evaluation. The proposed programs reduce the run-time as follows: adopting the non-recursive mode instead of the recursive mode for combinations, combining combination programs and permutation programs for r-permutation. According to our performance test, combination programs and r-permutation programs improve the run speed from minimum 12% to maximum 43% and from minimum 49% to maximum 370% respectively, as compared to the fastest analyzed program.
  Based on the proposed algorithms and pseudo-code, total data generation programs could be easily applied to specific cases, and the validity of the total data survey performance could be verified by predicting the run-time of total data list generation. By using the pseudo-code of the proposed algorithms and programs, the total data can be generated in minimum time. Algorithms with improved performance are expected to be used in the total inspection of industrial products, route selection for the entire wired and wireless networks, allocation of non-competitive sections on wireless networks, and selection of stable streaming servers for monitoring information transmission in M2M(Machine to Machine) environments.

닫기

• 논문에서는 기초적인 콤비나토리얼 문제인 조합(combination)과 순열(permutation), r-순열(r-permutation)을 이용하여 전수데이터를 조합과 순열의 목록으로 생성하는 프로그램과 알고리즘을 다룬다. ...
• 논문에서는 기초적인 콤비나토리얼 문제인 조합(combination)과 순열(permutation), r-순열(r-permutation)을 이용하여 전수데이터를 조합과 순열의 목록으로 생성하는 프로그램과 알고리즘을 다룬다. 조합과 순열 생성 알고리즘과 프로그램을 통해 생성되는 전수데이터 목록은 상품에 대한 품질검사를 위한 전수조사(total inspection), 시뮬레이션의 입력값 선정 등에서 사용된다. 조합과 순열 생성 알고리즘은 입력값이 증가함에 따라 수행시간이 지수적으로 증가하기 때문에 수행시간을 단축할 수 있는 개선된 알고리즘을 제안한다.
  선행연구로는 조합, 순열, r-순열 문제의 해법을 만족하는 기존 순열, 조합 생성 알고리즘에 대해 구현된 프로그램들을 조사하여 수행이 가능하도록 프로그램을 완성하고 알고리즘의 내용과 동작방법을 설명하였으며 의사코드(pseudo-code)로 정리한다.
  각 조합, 순열, r-순열 알고리즘에 대해 전수데이터의 사전적 정렬 여부, 입력값의 순서에 따른 전수데이터 생성가능 여부, 알고리즘의 재귀형태 여부의 세 가지 속성을 확인하고, 각 프로그램의 수행시간에 대한 비교와 입력값과 성능과의 연관관계를 확인한다.
  연구를 통해 기존 알고리즘 보다 수행시간을 단축하여 성능을 개선한 프로그램을 제안하고 성능평가를 통해 알고리즘의 특성과 성능의 개선도를 확인하였다. 조합 문제에는 재귀 형식에서 비재귀 형식으로 변형시키고 r-순열 문제에서는 조합 프로그램과 순열 프로그램을 결합하는 방법으로 수행시간을 단축하였다. 성능평가에 대한 분석결과는 수집한 가장 빠른 프로그램에 비해서 수행속도를 조합문제에서 최소 12%에서 최대 43%, r-순열 문제에서 최소 49%에서 최대 370%로 개선하였다.
  제안한 알고리즘과 의사코드를 기반으로 다양한 응용분야에 따라 속성을 확인하여 응용분야의 특성에 적합한 전수데이터 생성 프로그램을 쉽게 적용이 가능하며, 전수조사 목록의 생성에 소요되는 수행시간을 예측하여 전수조사의 수행에 대한 타당성 여부를 결정할 수 있다. 또한, 제공한 알고리즘과 프로그램 의사코드를 이용하여 최소의 시간으로 전수데이터를 생성할 수 있다.
  성능을 개선한 알고리즘들은 산업제품의 전수검사, 유무선망에서의 전체 경로의 선택, 무선망에서 비경쟁구간의 할당, M2M(Machine to Machine) 환경에서 모니터링 정보 전송을 위한 안정된 스트리밍서버를 선택 등을 위해 활용이 가능할 것으로 기대한다.

닫기

• 국문초록 ⅹⅲ
• 영문초록 ⅹⅴ
•  
• 제 1 장 서 론 1
• 1.1 연구의 배경 1
• 1.2 관련 연구동향 3
• 1.3 연구 목적 및 내용 4
• 1.4 논문의 구성 10
•  
• 제 2 장 관련 연구 11
• 2.1 조합, 순열 생성 알고리즘 11
• 2.1.1 조합의 생성 14
• 2.1.2 순열의 생성 16
• 2.2 알고리즘 사전조사 19
•  
• 제 3 장 기존 알고리즘 연구 25
• 3.1 기존 조합 생성 알고리즘 25
• 3.1.1 기존 조합 생성 알고리즘 정의 26
• 3.1.2 기존 조합 생성 알고리즘 동작 28
• 3.2 기존 순열 생성 알고리즘 29
• 3.2.1 기존 순열 생성 알고리즘 정의 30
• 3.2.2 기존 순열 생성 알고리즘 동작 39
• 3.3 기존 r-순열 생성 알고리즘 41
• 3.3.1 기존 r-순열 생성 알고리즘 정의 41
• 3.3.2 기존 r-순열 생성 알고리즘 동작 43
•  
• 제 4 장 개선된 조합, r-순열 생성 알고리즘 45
• 4.1 개선된 조합 생성 알고리즘 45
• 4.1.1 개선된 조합 생성 알고리즘 정의 45
• 4.1.2 개선된 조합 생성 알고리즘 동작 47
• 4.2 개선된 r-순열 생성 알고리즘 49
• 4.2.1 개선된 r-순열 생성 알고리즘 정의 49
• 4.2.2 개선된 r-순열 생성 알고리즘 동작 53
•  
• 제 5 장 성능평가 56
• 5.1 평가 방법 56
• 5.2 조합, 순열, r-순열별 성능평가 63
• 5.2.1 조합 문제 성능평가 64
• 5.2.2 순열 문제 성능평가 68
• 5.2.3 r-순열 문제 성능평가 70
• 5.3 단위 수행시간별 성능평가 75
• 5.3.1 조합 문제 단위 수행시간 성능평가 76
• 5.3.2 순열 문제 단위 수행시간 성능평가 80
• 5.3.3 r-순열 문제 단위 수행시간 성능평가 82
• 5.4 평가 결과 85
•  
• 제 6 장 결론 87
•  
• 참고문헌 89

 

출처 : http://www.riss.kr/search/detail/DetailView.do?p_mat_type=be54d9b8bc7cdb09&control_no=1295291567fd1db8ffe0bdc3ef48d419#redirect