주어진 입력 및 출력에 대한 함수 만들기

Question

두 개의 동일한 크기 세트가 있다고 가정 해보십시오.

함수를 생성하려면 입력 항목을 출력 항목에 정확하게 매핑하는 알고리즘 또는 서브 루틴을 만들 수 있습니까? 마찬가지로 :

Input = 1, 2, 3, 4 
Output = 2, 3, 4, 5 

및 기능은 다음과 같습니다이 유용 할 것

f(x): 
    if x == 1: return 2 
    if x == 2: return 3 
    if x == 3: return 4 
    if x == 4: return 5 

:

f(x): return x + 1 

그리고 "기능"에 의해

I [1]보다 뭔가 조금 더 comlex을 의미 특수 해시 함수 또는 함수 근사를 작성합니다.

---

업데이트 :

내가 부탁하려고하는 것은 찾을 것입니다이 압축 할 수있는 방법이 있는지입니다 위에서 사소한 매핑 예 [1].

Answer 1

일부 문자열 (순서, 함수 등)을 출력하는 가장 짧은 프로그램을 찾는 것은 결정할 수없는 Kolmogorov complexity을 찾는 것과 같습니다.

"불가능"이 만족스러운 대답이 아니라면 문제를 제한해야합니다. 모든 적절히 제한된 경우 (다항식, 합리적인 함수, 선형 반복) 최적의 알고리즘을 찾는 것은 자신이하는 일을 이해하는 한 쉽습니다. 예 :

• 다항식 - Lagrange interpolation

• 유리 함수 - Pade approximation

• 부울 식 - Karnaugh map

• 근사해 - regression 선형 경우 : linear regression

• 데이터의 일반적인 패킹 - data compression; run-length 인코딩과 같은 일부 기술은 무손실이며 일부는 그렇지 않습니다. 다항식 서열 경우

는 종종 N _{는 N + 1} -a N = B를 순서를 고려하는 데 도움; 이것은 선형 관계에 대한 이차 관계를 줄이고, 선형 관계를 일정한 순서 등에 줄입니다.하지만 은색 글 머리 기호는 없습니다. 유전 알고리즘, 무작위 추측, 많은 내장 시퀀스와 그 합성 등을 사용하여 몇 가지 발견 적 방법 (예 : Mathematica에 FindSequenceFunction -이 페이지가 얼마나 복잡한 지에 대한 인상을 갖도록 확인)을 만들 수 있습니다. 이론적으로 어떤 프로그램이든 Kolmogorov의 복잡성의 결정 불가능 성으로 인해 완벽하게 멀어집니다. 실제로는 만족스러운 결과를 얻을 수 있지만, 많은 인력이 필요합니다.

도 참조하십시오. another SO question 애플리케이션에 OEIS에 대한 래퍼를 구현할 수도 있습니다.

분야 :

대부분,

• 복잡성 이론에서 설명 할 수있는 일의 한계 - 그래프에서 최단 경로를 찾는처럼 문제 "빠른"해결 될 수 있는지 설명하고, 체커의 일반화 된 버전을 재생하는 것 (EXPTIME 완료)과 같이 할 수 없습니다.

• 정보 이론 - 얼마나 많은 "정보"가 임의의 변수에 의해 운반되는지 설명합니다. 예를 들어 동전 던지기. 일반적으로 결과를 인코딩하는 데 1 비트, n 개의 결과를 인코딩하는 데 n 비트가 사용됩니다 (긴 0-1 시퀀스 사용). 꼬리에 시간의 90 %를주는 바이어스 된 동전이 있다고 가정 해보십시오. 그런 다음 평균적으로 훨씬 짧은 시퀀스를 제공하는 n 개의 결과를 설명하는 다른 방법을 찾는 것이 가능합니다. 최적의 코딩 (이 경우 1 미만!)에 필요한 비트 당 비트 수는 entropy입니다. plot in that article은 얼마나 많은 정보가 전달되는지 보여줍니다 (1/2-1/2는 1 비트, 바이어스 된 코인은 1보다 작고 코인은 항상 같은쪽에 위치 함).

• 알고리즘 정보 이론 - 복잡성 이론과 정보 이론에 합류하려고 시도합니다. 콜 모고 로브의 복잡성이 여기에 속합니다. Kolmogorov의 복잡도가 클 경우 "임의"문자열을 고려할 수 있습니다. aaaaaaaaaaaa는 임의의 문자열이 아니며, 아마도 f8a34olx입니다. 따라서 임의의 문자열은 압축 할 수 없습니다 (Volchan's What is a random sequence은 매우 읽기 쉬운 소개입니다). Chaitin의 algorithmic information theory 도서를 다운로드 할 수 있습니다. 인용구 : "[...] 우리는 정수와 덧셈, 곱셈 및 지수 화만 포함하는 방정식을 만듭니다. 속성이 하나의 매개 변수를 변경하고 솔루션 수가 유한 또는 무한대인지 묻는 질문에 대한 대답은 다음과 같습니다. 공정한 동전의 독립적 인 토스 (tosses)의 결과와 구별 할 수 없다. " (즉, 어떤 알고리즘도 확률> 1/2 인 결과를 추측 할 수 없습니다). 나는 그 책을 읽지 않았으므로 그것을 평가할 수는 없다.

정보 이론과 관련이있는 것은 코딩 이론으로 오류 수정 코드를 설명합니다. 예시 결과 : 임의의 단일 오류를 검출 및 정정하거나 2 개의 오류 (Hamming(7,4))를 검출 할 수 있도록 4 비트 내지 7 비트를 부호화 할 수있다.

은 "포지티브"측

은 :

라그랑주 보간 Pade 근사위한

• 기호 알고리즘 computer algebra/symbolic computation의 일부이고; Gerhard "Modern Computer Algebra"는 좋은 참고 자료입니다.

• 데이터 compresssion는 - 여기 당신은 더 나은 신경망에 대해 정확히 입력 및 출력 데이터에서 기본지도를한다 엄선한 참조에 대한 다른 사람 :

Answer 2

나는 당신이 hashtable을 원한다고 생각합니다. 이들은 해시 함수를 기반으로하며, 예상 입력 및 원하는 출력에 따라 다른 것보다 잘 작동하는 알려진 해시 함수가 있습니다.

임의의 입력을 임의의 출력에 매핑하는 알고리즘 방식을 원한다면 일반적으로 입/출력 세트에 따라 다르므로 일반적인 경우에는 실현할 수 없습니다.

예를 들어, 당신이 거기에있는 간단한 예제에서, 그 기능은 즉각적으로 명백합니다, f(x): x+1. 맵핑을 설명하는 정확한 함수를 생성하는 것은 매우 어려울 수도 있고 불가능할 수도 있습니다. 맵을 대략적으로 또는 직접 사용해야합니다.

Answer 3

좋아, 나는 당신의 질문을 이해하지 못한다. 그러나 나는 그것을 한방에 줄 것이다.

숫자가 2 개인 경우 y = f (x) 인 f를 찾으려면 curve-fitting을 사용하여 대략적인 "지도"를 얻을 수 있습니다.

이 경우 선형이므로 커브 피팅이 작동합니다. 다른 모델을 시도해 가장 잘 작동하는지 확인하고 오류 측정 기준을 최소화하여 선택할 수 있습니다.

당신이 염두에 두었던 것이 이것입니까? linear regression, (예 : 예로서) 어떤 경우에는

Linear fitting http://www.aip.org/tip/INPHFA/vol-9/iss-2/images/p24-1.gif

Answer 4

또는 유사한 통계 모델은 입력 및 출력 세트 사이의 관계를 찾을 수 : 여기

는 그 기사에서 curve-fitting 또 다른 링크 및 이미지의 .

Answer 5

일반적으로이 작업을하는 것은 임의로 어렵습니다. 예를 들어, ECB 모드에서 사용되는 블록 암호를 생각해보십시오. 입력 정수를 출력 정수로 매핑하지만, 의도적으로 특정 예제의 일반적인 매핑을 파생시킬 수는 없습니다. 사실, 좋은 암호의 경우, 입력 블록과 출력 블록 사이의 완전한 매핑 세트를 사용하더라도 여전히 일반적인 매핑을 계산하는 방법을 결정할 수 없습니다.

명백히 암호는 극단적 인 예이지만 분명히 묻는 것을 수행하기위한 (알려진) 일반 절차가 없음을 보여줍니다.

Answer 6

물어 것! 당신은 모르는 사이에 컴퓨터 과학 분야의 훌륭한 연구 분야를 우연히 발견했습니다.