컴퓨터 과학에서 피보나치 숫자가 중요한 이유는 무엇입니까?
피보나치 수 는 컴퓨터 과학 학생들에게 재귀에 대한 인기있는 소개가되었으며 자연 내에서 지속된다는 강력한 주장이 있습니다. 이러한 이유로 우리 중 많은 사람들이 그것에 익숙합니다.
그들은 또한 다른 곳에서도 컴퓨터 과학 내에 존재합니다. 시퀀스에 기반한 놀랍도록 효율적인 데이터 구조와 알고리즘에서.
떠오르는 두 가지 주요 예가 있습니다.
다른 숫자 시퀀스보다 이점을 제공하는이 숫자의 특별한 속성이 있습니까? 공간 품질입니까? 다른 가능한 응용 프로그램은 무엇입니까?
다른 재귀 문제에서 발생하는 자연수 시퀀스가 많기 때문에 이상하게 보이지만 카탈로니아 어 힙 은 본 적이 없습니다 .
피보나치 수는 컴퓨터 과학에서 탁월하게 만드는 모든 종류의 정말 좋은 수학적 속성을 가지고 있습니다. 다음은 몇 가지입니다.
- 기하 급수적으로 빠르게 성장합니다.피보나치 시리즈가 등장하는 흥미로운 데이터 구조 중 하나는 자체 균형 이진 트리의 한 형태 인 AVL 트리입니다. 이 트리 뒤에있는 직관은 각 노드가 균형 요소를 유지하여 왼쪽 및 오른쪽 하위 트리의 높이가 최대 1만큼 달라진다는 것입니다. 이 때문에 높이 h의 AVL 트리를 얻는 데 필요한 최소 노드 수는 N (h + 2) ~ = N (h) + N (h + 1)과 같은 반복으로 정의됩니다. 피보나치 시리즈와 매우 흡사합니다. 수학을 계산하면 높이 h의 AVL 트리를 얻는 데 필요한 노드 수가 F (h + 2)-1임을 보여줄 수 있습니다. 피보나치 시리즈가 기하 급수적으로 빠르게 증가하기 때문에 AVL의 높이가 tree는 노드 수에서 최대 로그이므로 우리가 알고 있고 균형 잡힌 이진 트리에 대해 좋아하는 O (lg n) 조회 시간을 제공합니다. 사실로, 일부 구조의 크기를 피보나치 수로 제한 할 수 있다면 일부 작업에서 O (lg n) 런타임을 얻을 수 있습니다. 이것이 피보나치 힙을 피보나치 힙이라고 부르는 진짜 이유입니다. 즉, 대기열에서 빼기 최소 후 힙의 수는 피보나치 수로 특정 깊이에서 가질 수있는 노드 수를 제한한다는 증거입니다.
- 고유 한 피보나치 수의 합으로 임의의 수를 쓸 수 있습니다. 피보나치 수의이 속성은 피보나치 검색이 작동하도록하는 데 매우 중요합니다. 고유 한 피보나치 수를 가능한 수에 더할 수 없다면이 검색은 작동하지 않습니다. 이것을 3n 또는 카탈로니아 숫자 와 같은 다른 많은 시리즈와 대조하십시오 . 이것은 또한 2의 거듭 제곱과 같은 많은 알고리즘을 사용하는 이유이기도합니다.
- 피보나치 수는 효율적으로 계산할 수 있습니다.시리즈가 매우 효율적으로 생성 될 수 있다는 사실 (O (n)에서 처음 n 개의 항 또는 O (lg n)에서 임의의 항을 얻을 수 있음),이를 사용하는 많은 알고리즘은 실용적이지 않습니다. 카탈로니아 어 숫자를 생성하는 것은 계산적으로 매우 까다 롭습니다. IIRC. 게다가, 피보나치 수는 두 개의 연속적인 피보나치 수가 주어지면 F (k)와 F (k + 1)이라고 가정하면 두 값을 더하여 다음 또는 이전 피보나치 수를 쉽게 계산할 수있는 좋은 속성을 가지고 있습니다. (F (k) + F (k + 1) = F (k + 2)) 또는 빼기 (F (k + 1)-F (k) = F (k-1)). 이 속성은 속성 (2)와 함께 여러 알고리즘에서 이용되어 숫자를 피보나치 숫자의 합으로 분리합니다. 예를 들어 피보나치 검색은이를 사용하여 메모리에서 값을 찾습니다.
- 교육적으로 유용합니다. 재귀를 가르치는 것은 까다 롭고 피보나치 시리즈는 그것을 소개하는 좋은 방법입니다. 시리즈를 소개 할 때 직선 재귀, 메모 화 또는 동적 프로그래밍에 대해 이야기 할 수 있습니다. 또한 피보나치 수에 대한 놀라운 폐쇄 형 은 종종 유도 또는 무한 급수 분석에서 연습으로 가르치며 , 피보나치 수 에 대한 관련 행렬 방정식 은 일반적으로 고유 벡터 및 고유 값의 동기로 선형 대수에 도입됩니다. 나는 이것이 그들이 입문 수업에서 매우 주목받는 이유 중 하나라고 생각합니다.
나는 이것보다 더 많은 이유가 있다고 확신하지만, 이러한 이유 중 일부가 주요 요인이라고 확신합니다. 도움이 되었기를 바랍니다!
최대 공약수 는 또 다른 마술입니다. 너무 많은 마술을 위해 이것을 보십시오 . 그러나 피보나치 수는 계산하기 쉽습니다. 또한 특정 이름이 있습니다. 예를 들어, 자연수 1,2,3,4,5는 논리가 너무 많습니다. 모든 소수는 그 안에 있습니다. 1..n의 합계는 계산할 수 있으며, 각각 다른 것과 함께 생산할 수 있지만 아무도 신경 쓰지 않습니다. :)
내가 잊은 한 가지 중요한 점 은 실제 생활에 매우 중요한 영향을 미치는 황금 비율입니다 (예 : 와이드 모니터를 좋아하는 경우 :).
CS와 자연에서 이해할 수있는 예제를 통해 간단하고 간결한 방식으로 성공적으로 설명 할 수있는 알고리즘이 있다면 어떤 더 나은 교육 도구를 생각 해낼 수 있을까요?
피보나치 수열은 실제로 자연 / 생활의 모든 곳에서 발견됩니다. 동물 개체군의 성장, 식물 세포 성장, 눈송이 모양, 식물 모양, 암호화 및 물론 컴퓨터 과학을 모델링하는 데 유용합니다. 나는 그것을 자연의 DNA 패턴이라고 들었다.
피보나치 힙은 이미 언급되었습니다. 힙에있는 각 노드의 하위 수는 최대 log (n)입니다. 또한 m 개의 자식이있는 노드를 시작하는 하위 트리는 최소한 (m + 2) 번째 피보나치 수입니다.
노드 및 슈퍼 노드 시스템을 사용하는 토렌트 유사 프로토콜은 피보나치를 사용하여 새 슈퍼 노드가 필요한시기와 관리 할 하위 노드 수를 결정합니다. 그들은 피보나치 나선 (황금 비율)을 기반으로 노드 관리를 수행합니다. 노드가 분할 / 병합되는 방법 아래 사진을 참조하십시오 (하나의 큰 정사각형에서 작은 정사각형으로 또는 그 반대로 분할 됨). 사진 참조 : http://smartpei.typepad.com/.a/6a00d83451db7969e20115704556bd970b-pi
자연의 일부 발생
http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/sneezewort.GIF
http://img.blogster.com/view/anacoana/post-uploads/finger.gif
http://jwilson.coe.uga.edu/EMAT6680/Simmons/6690Pictures/pinecone3yellow.gif
확실한 답은 없다고 생각하지만 한 가지 가능성은 세트 S를 두 개의 파티션 S1과 S2로 나누는 작업이 그 중 하나가 하위 파티션 S11과 S12로 나뉘는 것입니다. S2-많은 알고리즘에 대한 가능한 접근 방식이며 때로는 피보나치 수열로 수치 적으로 설명 될 수 있습니다.
또 다른 데이터 구조를 추가하겠습니다 : 피보나치 나무. 트리의 다음 위치 계산은 이전 노드를 추가하는 것만으로 수행 할 수 있기 때문에 흥미 롭습니다.
http://xw2k.nist.gov/dads/html/fibonacciTree.html
AVL 트리에 대한 templatetypedef의 토론과 잘 연결됩니다 (AVL 트리는 최악의 경우 피보나치 구조를 가질 수 있음). 또한 어떤 경우에는 2의 거듭 제곱이 아닌 피보나치 단계로 확장 된 버퍼를 보았습니다.
이것에 대한 퀴즈를 추가하기 위해 피보나치 숫자는 토끼의 빵가루를 설명합니다. (1, 1) 두 마리의 토끼로 시작하면 그 개체수가 기하 급수적으로 증가합니다.
[[0,1], [1,1]] 행렬의 거듭 제곱으로서의 계산은 운영 연구의 가장 원시적 인 문제로 간주 될 수 있습니다 (범죄자의 딜레마와 같은 종류는 게임 이론의 가장 원시적 인 문제입니다).
연속적인 피보나치 수인 주파수를 가진 심볼은 최대 깊이의 허프만 트리를 생성하며, 트리는 최대 길이 이진 코드로 인코딩되는 소스 심볼에 해당합니다. 비 피보나치 소스 심볼 주파수는 더 짧은 코드로 더 균형 잡힌 트리를 생성합니다. 코드 길이는 주어진 허프만 코드의 디코딩을 담당하는 유한 상태 머신의 설명 복잡성에 직접적인 영향을 미칩니다.
추측 : 첫 번째 (fib) 이미지는 38 비트로 압축되고 두 번째 (uniform) 이미지는 50 비트로 압축됩니다. 소스 심볼 주파수가 피보나치 수에 가까울수록 최종 이진 시퀀스가 짧을수록 압축이 더 좋으며 허프만 모델에서 최적 일 수 있습니다.
추가 자료 :
Buro, M. (1993). Huffman 코드의 최대 길이. 정보 처리 편지, 45 (5), 219-223. 도이 : 10.1016 / 0020-0190 (93) 90207-p
'code' 카테고리의 다른 글
| React Router의 Link 컴포넌트 밑줄을 제거하는 방법은 무엇입니까? (0) | 2020.10.23 |
|---|---|
| BibTeX에서 모든 대문자 유지 (0) | 2020.10.22 |
| 동시 사전 올바른 사용법 (0) | 2020.10.22 |
| 내 Android 앱이 배터리를 소모합니까? (0) | 2020.10.22 |
| 인텔의 통합 그래픽 프로세서에서 CUDA를 실행할 수 있습니까? (0) | 2020.10.22 |