콘크리트 수학에서 "특별한 숫자"는 어디에서 언급됩니까?

StackOverflow https://stackoverflow.com/questions/901761

문제

나는 온라인으로 구체적인 수학의 내용을 살펴 보았습니다. 나는 적어도 언급 된 대부분의 기능과 요령을 들었지만 특수 번호에 대한 전체 섹션이 있습니다. 이 숫자에는 스털링 숫자, Eulerian 번호, 고조파 번호가 포함됩니다. 이제 나는이 이상한 숫자를 결코 만나지 못했습니다. 그들은 계산 문제에 어떻게 도움이됩니까? 일반적으로 어디에서 사용됩니까?

도움이 되었습니까?

해결책

이 숫자의 대부분은 특정 종류의 개별 구조를 계산합니다 (예 : 스털링 숫자는 서브 세트와 사이클 수). 그러한 구조, 따라서 이러한 서열은 암시 적으로 알고리즘 분석.

거기 있습니다 OEIS의 광범위한 목록 그 목록 콘크리트 수학에 나타나는 거의 모든 시퀀스. 해당 목록의 짧은 요약 :

  • Golomb의 순서
  • 이항 계수
  • Rencontres 번호
  • 스털링 숫자
  • Eulerian 번호
  • 과식
  • 게 노시 숫자

각 시퀀스의 OEIS 페이지를 탐색하여 이러한 시퀀스의 "속성"에 대한 자세한 정보를 얻을 수 있습니다 (정확히 응용 프로그램은 아니지만 가장 관심이있는 경우).

또한 알고리즘 분석에서 이러한 시퀀스의 실제 사용을보고 싶다면 Knuth의 컴퓨터 프로그래밍 기술 지수를 통해 뒤집어 주면 이러한 시퀀스의 "응용 프로그램"에 대한 많은 참조를 찾을 수 있습니다. John D. Cook은 이미 Fibonacci 및 Harmonic Numbers의 응용을 언급했습니다. 다음은 더 많은 예입니다.

스털링 사이클 번호 찾는 표준 알고리즘의 분석에서 발생합니다. 배열의 최대 요소 (TAOCP SEC. 1.2.10) : 최대 값을 찾을 때 현재 최대 값을 몇 번이나 업데이트해야합니까? 최대 값을 업데이트해야 할 확률이 밝혀졌습니다. k 배열에서 최대 값을 찾을 때 n 요소입니다 p[n][k] = StirlingCycle[n, k+1]/n!. 이것으로부터, 우리는 평균적으로이를 대략적으로 도출 할 수 있습니다. Log(n) 업데이트가 필요합니다.

게 노시 숫자 수를 계산하는 것과 관련하여 발생합니다 BDDS 그것은 "얇은"것입니다 (TAOCP 7.1.4 연습 174).

다른 팁

고조파 숫자는 거의 모든 곳에 나타납니다! 뮤지컬 하모니, QuickSort의 분석 ... 스털링 숫자 (첫 번째 및 두 번째 종류)는 다양한 조합 및 분할 문제에서 발생합니다. Eulerian 숫자는 또한 여러 곳에서 발생하며, 특히 폴리로 게라리트 기능의 순열 및 계수에서 발생합니다.

당신이 언급 한 많은 숫자는 알고리즘 분석에 사용됩니다. 코드에 이러한 숫자가 없을 수도 있지만 코드가 실행되는 데 걸리는 시간을 추정하려면 필요합니다. 코드에서도 볼 수 있습니다. 이 숫자 중 일부는 조합과 관련이 있으며 어떤 일이 발생할 수 있는지 계산합니다.

때때로 당신이 필요하기 때문에 얼마나 많은 가능성이 있는지 아는 것만으로는 충분하지 않습니다. 세다 가능성에 대한. Knuth 's Taocp의 4 권, 진행중인 알고리즘을 제공합니다.

다음은 사용의 예입니다 피보나치 번호 수치 적 통합 문제의 일부로.

고조파 숫자는 로그의 개별 아날로그이므로 로그가 미분 방정식으로 등장하는 것처럼 차이 방정식으로 나타납니다. 다음은 다음과 같습니다 고조파 수단의 물리적 응용, 고조파 수와 관련이 있습니다. 책을 참조하십시오 감마 행동중인 고조파 수의 많은 예, 특히 "고조파 세계입니다."

이 특별한 숫자는 여러면에서 계산 문제에 도움이 될 수 있습니다. 예를 들어:

  • 2 숫자의 GCD를 계산하는 프로그램이 가장 긴 시간이 걸리는시기를 알아 보려면 2 연속 Fibonacci 번호를 시도하십시오.

  • 당신은 많은 수의 계승에 대한 대략적인 추정치를 원하지만, 당신의 계승 프로그램은 너무 오래 걸리고 있습니다 : 사용 스털링의 근사.

  • 당신은 소수를 테스트하고 있지만 일부 숫자의 경우 항상 잘못된 답을 얻습니다. Fermat의 주요 테스트를 사용하는 것일 수 있습니다. Carmicheal 번호 당신의 범인입니다.

내가 생각할 수있는 가장 일반적인 일반적인 사례는 루핑입니다. 대부분의 경우 (start;stop;step) 구문의 유형,이 경우 관련된 숫자의 속성을 사용하여 실행 시간을 줄일 수 있습니다.

예를 들어, 루프에서 N이 크면 1에서 N까지의 모든 숫자를 합산하는 것이 신원을 사용하는 것보다 확실히 느립니다. sum = n*(n + 1)/2.

이와 같은 많은 예가 있습니다. 그들 중 많은 사람들이 암호화에 있으며, 때때로 정보 시스템의 보안이 의존합니다 이와 같은 트릭에. 또한 성능 문제, 메모리 문제를 도와 줄 수 있습니다. 공식을 알면 실제로 관심이있는 다른 것들을 계산하는 더 빠르거나 효율적인 방법을 찾을 수 있기 때문입니다.

자세한 내용은 Wikipedia를 확인하거나 Project Euler를 사용해보십시오. 당신은 패턴을 꽤 빨리 찾기 시작할 것입니다.

반드시 a 마법 번호 당신이 언급했지만 그럼에도 불구하고 -

0x5f3759df

- Newton 's에 좋은 추정치를 제공하여 숫자의 역 제곱근을 계산하는 데 사용되는 악명 높은 마법 번호 뿌리의 근사, 종종 John Carmack의 작품에 기인합니다. 더 많은 정보는 여기에 있습니다.

프로그래밍과 관련이 없습니까? :)

이것은 직접 프로그래밍과 관련이 있습니까? 확실히 관련이 있지만 얼마나 가깝게도 모르겠습니다.

E, PI 등과 같은 특별한 숫자가 사방에 나옵니다. 나는 누군가 가이 두 가지에 대해 논쟁 할 것이라고 생각하지 않습니다. 그만큼 Golden_ratio 또한 ART에서 다른 특수 숫자 자체에 이르기까지 놀라운 주파수로 나타납니다 (연속 피보나치 숫자의 비율을보십시오.)

다양한 시퀀스와 숫자의 가족도 수학의 여러 곳에서, 따라서 프로그래밍에도 나타납니다. 볼 수있는 아름다운 곳은 정수 시퀀스의 백과 사전.

나는 이것이 경험이라고 제안 할 것이다. 예를 들어, 수년 전에 선형 대수를 받았을 때, 나는 매트릭스의 고유 값과 고유 벡터에 대해 배웠습니다. 나는 다양한 장소에서 사용되는 것을 볼 때까지 고유 값/고유 벡터의 중요성을 전혀 이해하지 못했다는 것을 인정할 것입니다. 통계에서, 공분산 매트릭스의 추정 불확실성, 신뢰 타원의 크기와 모양, 주요 구성 요소 분석 또는 Markov 프로세스의 장기 상태에 대해 말한 내용의 관점에서. 수치 적 방법에서는 방법의 수렴에 대해 최적화 또는 ODE 솔버에 대해 알려줍니다. 기계 공학에서 주요 스트레스와 균주로 간주합니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top