다차원 문제는 당연히 1차원 문제보다 더 복잡하고 시간이 많이 걸리며, 일반적으로 차원이 커질수록 문제 해결의 어려움도 커집니다. 이를 더 잘 느끼기 위해 함수의 가장 작은 값을 찾는 가장 간단한 개념의 대략적인 방법을 생각해 보겠습니다. 고려 중인 영역을 h 단계(그림 10.8)의 그리드 G로 덮고 해당 노드에서 함수 값을 결정해 보겠습니다. 얻은 숫자를 서로 비교하여 그중 가장 작은 숫자를 찾아 대략 전체 영역에 대한 함수의 가장 작은 값으로 간주합니다.

쌀. 10.8.

위에서 말했듯이 이 방법은 1차원 문제를 해결하는 데 사용됩니다. 때로는 2차원 문제를 해결하는 데에도 사용되며 덜 자주 3차원 문제를 해결하는 데에도 사용됩니다. 그러나 더 큰 차원의 문제에서는 계산에 소요되는 시간이 너무 길어서 현실적으로 부적합합니다. 실제로, 목적 함수가 5개의 변수에 의존하고, 정의 영역 G가 5차원 큐브이고, ​​그리드를 구성할 때 각 변이 40개 부분으로 나누어진다고 가정합니다. 그러면 그리드 노드의 총 개수는 와 같습니다. 한 지점에서 함수 값을 계산하려면 1000번의 산술 연산이 필요합니다(5개 변수로 구성된 함수에는 그리 많지 않습니다). 이 경우 총 작업 수는 10 11이 됩니다. 초당 100만 개의 작업 속도를 가진 컴퓨터를 사용할 수 있다면 이 방법을 사용하여 문제를 해결하려면 10 5초가 필요하며 이는 하루 연속 작업을 초과합니다. 다른 독립변수를 추가하면 이 시간이 40배 증가합니다. 평가 결과, 대규모 최적화 문제에는 철저한 검색 방법이 적합하지 않은 것으로 나타났습니다. 때로는 전체 검색이 무작위 검색으로 대체되기도 합니다. 이 경우 그리드 포인트는 연속적으로 표시되지 않고 임의의 순서로 표시됩니다. 결과적으로 목적 함수의 가장 작은 값을 찾는 속도가 훨씬 빨라지지만 신뢰성이 떨어집니다.

4. 좌표하강법

두 변수의 함수를 생각해 봅시다. 그 일정한 레벨 라인은 그림 1에 나와 있습니다. 10.9이며 최소값은 해당 지점에 있습니다. (상수 레벨 라인은 매개변수 공간(이 경우 평면 (x1, x2)에서 상수인 함수 값)의 2차원 섹션에 있는 곡선이라는 점을 기억하세요. 가장 간단한 검색 방법은 다음과 같습니다. 좌표 하강법. 점 A에서 x1 축 방향을 따라 최소값을 검색하여 일정한 레벨 라인의 접선이 x1 축과 평행한 점 Bat를 찾습니다. 그런 다음 x2 축 방향으로 점 B를 검색하면 점 C를 얻고, x1 축과 평행하게 검색하면 점 D를 얻습니다. 따라서 우리는 최적의 지점에 도달합니다. 이전 장에서 설명한 모든 1차원 방법을 여기에서 축을 따라 검색하는 데 사용할 수 있습니다. 분명히 이 아이디어는 n개 변수의 함수에 적용될 수 있습니다.

쌀. 10.9.

특정 대상 함수의 예를 사용하여 이 방법을 더 자세히 살펴보겠습니다.

목적 함수 u=f(M)=f(x 1 ,x 2 ,...,xn) 의 가장 작은 값을 찾아야 합니다. 여기서 M은 좌표가 있는 n차원 공간의 한 점을 나타냅니다. x 1 ,x 2 ,...,xn:M=(x 1 ,x 2 ,...,xn). 몇 가지 시작점을 선택하고 첫 번째 변수를 제외한 모든 변수의 고정 값에 대한 함수 f를 고려해 보겠습니다. . 그러면 하나의 변수 x 1의 함수로 변합니다. 이 변수를 변경하면 함수가 감소하는 방향으로 시작점에서 최소값에 도달할 때까지 이동한 후 증가하기 시작합니다. 좌표가 있는 점을 M 1로 표시하고, .

이제 변수를 수정하고 함수 f를 하나의 변수의 함수로 생각해 보겠습니다. x 2를 변경하면 에서 최소값에 도달할 때까지 초기 값에서 함수 감소 방향으로 다시 이동합니다. 좌표가 있는 점을 M 2로 표시하고, . 변수 x 3 , x 4 ,...,xn 에 대해 목적 함수의 동일한 최소화를 수행해 보겠습니다. 변수 xn에 도달한 후 다시 x1로 돌아가서 프로세스를 계속해 보겠습니다.

이 절차는 메서드 이름을 완전히 정당화합니다. 그것의 도움으로 우리는 일련의 점 M 0 , M 1 , M 2 ,...을 구성할 것입니다. 함수 값의 단조로운 시퀀스가 ​​해당합니다. 특정 단계 k에서 이를 종료하면 함수 f(M k)의 값을 고려 중인 영역에서 가장 작은 값으로 사용할 수 있습니다(그림 10.10). .

이 방법은 여러 변수의 함수 중 가장 작은 값을 찾는 문제를 1차원 최적화 문제를 반복적으로 해결하는 문제로 줄입니다. 목적 함수 f(x 1 ,x 2 ,\ldots,x n이 명시적 공식으로 주어지고 미분 가능하다면, 부분 도함수를 계산하고 이를 사용하여 각 변수에서 함수의 감소 방향을 결정하고 탐색할 수 있습니다. 해당 1차원 최소값에 대해.

그림에서. 10.10. 두 변수 u=f(x,y) 의 특정 함수의 수준선을 보여줍니다. 이 라인을 따라 함수는 1, 3, 5, 7, 9와 같은 상수 값을 유지합니다. O 지점에서 달성되는 가장 작은 값을 검색하는 궤적은 다음을 사용하여 표시됩니다.

무차별 대입 방식은 모든 문제를 해결하는 가장 간단한 방법입니다. 가장 간단한 방법은 아마도 선택 방법일 것입니다. (즉시) 답을 즉시 선택할 수 없고, 주어진 조건보다 문제에 알려지지 않은 것이 더 많다면, 완전 검색 방법이 딱 맞습니다. 물론 먼저 다른 모든 솔루션 옵션이 적합하지 않은지 확인해야 하며 모든 명시적 및 암시적 조건이 적용되어 시도되는 조합을 제한해야 합니다. 그렇지 않으면 가능한 모든 옵션을 시도하는 데 걸리는 시간이 무한정이 됩니다.

다양한 문제를 해결하기 위해 무차별 대입 방법을 사용하는 몇 가지 예를 살펴보겠습니다.

서열 검색

일련의 숫자 141526418을 발견했고 특정 단어가 라틴 문자로 암호화되어 있다는 것을 알고 있다고 가정해 보겠습니다. 단어를 암호화하는 가장 쉬운 방법은 무엇입니까? 물론 대체 암호를 사용하세요! 자릿수가 홀수입니다. 즉, 최소한 하나의 문자가 단 한 자리로 인코딩된다는 의미입니다. 그러나 두 자리 숫자로 인코딩된 처음 10개의 문자를 다음 문자와 분리하는 방법은 무엇입니까? 서기 14년은 N인가? 무차별 대입 방법이 유용한 곳입니다. 범위에서 한 자리 또는 두 자리 숫자의 모든 조합을 살펴 보겠습니다.

시퀀스 141526418에서 조건을 충족하는 다음 조합을 구별할 수 있습니다: 1,2,4,5,6,8,14,15,18,26. 이 숫자는 문자 A,B,D,E,F,H,N,O,R,Z에 해당합니다. 41, 52, 64 조합은 우리에게 적합하지 않습니다. 라틴 알파벳에는 26개의 글자만 있기 때문입니다.

우리는 그것을 다음과 같이 정리할 것입니다: 먼저 모든 문자가 처음 10부터인 가장 확장된 시퀀스를 선택한 다음 사용되는 숫자를 하나씩 증가시킵니다. 즉, 시퀀스 1-4를 14로 대체합니다. , 1-5는 15, 1-8은 18, 2-6은 26, 가능한 모든 조합을 거칩니다.

1-4-1-5-2-6-4-1-8 = ADAEBFDAH

1-4-1-5-2-6-4-18 = ADAEBFDR

1-4-1-5-26-4-1-8 = 아데아즈다

1-4-1-5-26-4-18 = ADAEZDR

1-4-15-2-6-4-1-8 = ADOBFDAH

1-4-15-2-6-4-18 = ADOBFDR

1-4-15-26-4-1-8 = 아도즈다

1-4-15-26-4-18 = ADOZDR

14-1-5-2-6-4-1-8 = NAEBFDAH

14-1-5-2-6-4-18 = NAEBFDR

14-1-5-26-4-1-8 = 나에즈다

14-1-5-26-4-18 = NAEZDR

14-15-2-6-4-1-8 = NOBFDAH

14-15-2-6-4-18 = NOBFDR

14-15-26-4-1-8 = 노즈다

14-15-26-4-18 = 노즈드르

총 16개의 옵션이 제공되었습니다. 유일하게 읽을 수 있는 단어 NOZDR(어떤 사람은 읽을 수 있고 다른 사람은 읽을 수 없음)이 맨 끝에 나왔습니다. 이것이 답이 될 것입니다. 이제 맨 처음에 시퀀스 141526418이 5개의 문자를 생성해야 한다는 힌트가 있다면 문제는 명확하게 해결될 것입니다. 그리고 141526418 시퀀스를 5개의 문자로 분할하는 방법은 한 가지뿐이므로 무차별 대입은 필요하지 않습니다. 하지만 그런 힌트는 없었고, 무차별 대입 방식이 유용했습니다.

조건이 충분하지 않은 경우 솔루션 열거

수학에는 정면으로 풀 수 없을 것 같은 문제가 나올 때가 있다. 이러한 문제는 올림피아드 및 대회에서 해결하기 위해 종종 제공되므로 퀘스트에 적합합니다. 예를 들어, 여기에 문제가 있습니다.

수학시간에 선생님이 학생들에게 다음과 같은 문제를 내셨습니다. “어머니에게는 세 딸이 있습니다. 딸의 나이 = 40, 나이의 합은 학급의 학생 수와 같습니다. 딸들은 각각 몇 살입니까?”글쎄요, 학생들은 학급에 몇 명이 있는지 재빨리 계산하고 문제를 해결하기 시작했습니다. 결정하고 결정하고... 결정할 수 없습니다. 우리는 선생님에게 힌트를 요청했습니다. 선생님은 생각하고 이렇게 말했습니다. “아, 바로 그거야! 막내는 파란 눈을 가지고 있어요!”. 학생들은 기뻐하며 문제를 해결했습니다. 이제 질문이 있습니다. 딸들은 각각 몇 살입니까?

문제를 정면으로 해결하면(AxBxC=40, A+B+C=D, 작은 파란 눈) 즉시 알 수 없는 문제와 조건 부족에 직면하게 됩니다. 4개의 미지수, 2개의 방정식, 심지어 작은 파란 눈까지!!! 아시다시피 미지수가 많으면 독립된 조건도 많아야 합니다. 우리 문제에는 두 가지 정상적인 조건과 하나의 이해할 수 없는 조건이 있습니다. 어떻게 해결하나요?

그리고 무차별적으로! 첫째, 이러한 문제는 기본적으로 정수로 해결됩니다. 세 정수의 모든 조합을 찾아 봅시다. 그 곱은 40이 됩니다. 동시에 이 숫자들의 합을 계산해 봅시다. 그러한 조합은 그리 많지 않고 단지 6개에 불과하다는 것이 밝혀졌습니다.

1x1x40=40, 1+1+40=42

1x2x20=40, 1+2+20=23

1x4x10=40, 1+4+10=15

1x5x8=40, 1+5+8= 14

2x2x10=40, 2+2+10= 14

2x4x5=40, 2+4+5=11

학급에 42명, 23명, 15명, 11명의 학생이 있으면 즉시 문제를 해결합니다. 그러나 그들은 어려움을 겪었습니다. 그중 14 개가 있었고 1-5-8 또는 2-2-10 옵션 중 어느 것이 적합한 지 선택할 수 없었습니다. 하지만 선생님이 파란 눈에 대해 말씀하셨을 때, 그것이 그들이 결정하는 데 도움이 되었습니다. 막내는 파란 눈, 즉 막내 딸이 있었고, 2-2-10 버전에는 막내 두 명이 있었다. 이는 네 번째 옵션인 1-5-8만이 우리에게 적합하다는 것을 의미합니다.

현실적으로 해결하기 어려운 문제처럼 보이지만 무차별 대입 방식을 사용하면 매우 빠르게 문제를 해결할 수 있습니다. 그러므로 무차별 대입으로 문제를 해결하는 것을 두려워해서는 안됩니다. 가능한 옵션의 수가 처음에 보이는 것만큼 많지 않은 경우가 많습니다.

이 섹션에서는 정보 검색 문제와 관련된 몇 가지 문제를 살펴보겠습니다. 이것은 프로그래밍에 관한 고전 문헌(예를 들어 N. Wirth, D. Knuth 등의 책 참조)에 충분히 자세히 설명되어 있는 거대한 종류의 문제입니다.

검색 작업의 일반적인 의미는 다음과 같이 요약됩니다. 컴퓨터 메모리에 저장된 주어진 정보에서 특정 조건(기준)을 충족하는 필수 정보를 선택합니다.

우리는 이미 비슷한 문제를 고려했습니다. 예를 들어, 숫자 배열에서 최대 수를 검색하는 것, 데이터 파일에서 원하는 레코드를 검색하는 것 등이 있습니다. 이러한 검색은 데이터 구조의 모든 요소를 ​​열거하고 검색 조건을 만족하는지 확인하여 수행됩니다. 구조의 모든 요소를 ​​검사하는 열거형을 전체 열거형이라고 합니다.

완전 검색은 무차별 검색 방법이며, 분명히 항상 최고는 아닙니다.

예를 살펴보겠습니다. 1차원 배열 X에는 실수 축에 있는 n개 점의 좌표가 제공됩니다. 포인트에는 번호가 매겨져 있습니다. 해당 번호는 X 배열의 시퀀스에 해당합니다. 원점에서 가장 먼 첫 번째 지점의 번호를 결정합니다.

이는 배열 X의 가장 큰 모듈로 요소의 수를 결정하는 익숙한 문제라는 것을 이해하기 쉽습니다. 이는 다음과 같은 철저한 검색을 통해 해결됩니다.

1차원 배열 요소의 완전한 열거는 하나의 순환 구조를 사용하여 수행됩니다.

이제 다음 작업이 수행됩니다. 초기 데이터는 이전 데이터와 동일합니다. 두 점 사이의 거리가 가장 큰 한 쌍의 점을 결정해야 합니다.

열거 방법을 사용하면 이 문제는 다음과 같이 해결될 수 있습니다. Ladanny의 모든 점 쌍을 열거하고 그 사이의 거리가 가장 큰 점의 수(좌표 차이의 가장 큰 계수)를 결정합니다. 이 철저한 검색은 두 개의 중첩 루프를 통해 구현됩니다.

문제에 대한 그러한 해결책이 비합리적이라는 것은 명백합니다. 여기서 각 점 쌍은 예를 들어 i = 1, j = 2 및 i = 2, j= 1인 경우 두 번 검사됩니다. n = 100인 경우 루프는 100 x 100 = 10000번 실행을 반복합니다.

반복이 제거되면 프로그램 실행 속도가 빨라집니다. i값과 j값이 일치하는 경우도 배제되어야 한다. 그러면 루프의 반복 횟수는 다음과 같습니다.

n = 100이면 결과는 4950입니다.

반복을 제거하려면 이전 프로그램에서 내부 루프의 시작을 1에서 i +1로 변경해야 합니다. 프로그램은 다음과 같습니다:

우리는 알고리즘의 고려된 버전을 반복 없이 무차별 대입이라고 부를 것입니다.

논평. 물론 이 문제는 다른 방법으로 해결될 수도 있었지만 이 경우 우리는 무차별 대입 알고리즘에 관심이 있었습니다. 직선이 아닌 평면이나 공간에 위치한 점의 경우 이러한 알고리즘에 대한 대안을 찾는 것이 매우 문제가 됩니다.

다음 문제에서는 배열 X에서 합이 10인 반복이 없는 세 개의 숫자를 모두 선택해야 합니다.

이 경우 알고리즘은 세 개의 중첩 루프로 구성됩니다. 내부 루프의 길이는 가변적입니다.

I의 경우:=l To N Do

J의 경우:=I+1 To N Do

K:=J+1 To N Do

X[I]+X[J]+X[K]=10인 경우

그런 다음 WriteLn(X[I],X[J],X[K]);

이제 배열 X에서 합계가 10인 숫자 그룹을 모두 선택해야 한다고 상상해 보세요. 그룹에는 1~n개의 숫자가 포함될 수 있습니다. 이 경우 검색 옵션의 수가 급격히 증가하고 알고리즘 자체가 사소해집니다.

그럴 것 같으니 어쩌죠? 기계가 빨리 작동해요! 그래도 세어 봅시다. n개 객체(빈 항목 포함)로 구성된 서로 다른 그룹의 수는 2n개입니다. n = 100인 경우 2100 ≒ 1030이 됩니다. 초당 10억 번의 작업 속도로 작동하는 컴퓨터는 약 10년 동안 이 검색을 수행합니다. 순열 반복을 제거하더라도 이러한 철저한 검색 알고리즘이 실제로 실현 가능하지는 않습니다.

이러한 문제를 실질적으로 해결하는 방법은 문제 조건의 관점에서 볼 때 유망하지 않은 검색 옵션을 제외하는 방법을 찾는 것입니다. 일부 문제의 경우 다음 섹션에 설명된 알고리즘을 사용하여 이를 수행할 수 있습니다.

반품으로 과잉. 미로 통과 문제의 예를 사용하여 역추적 알고리즘을 고려해 보겠습니다(그림 52).

미로가 주어지면 그 안에서 탈출구를 찾아야 합니다. 수평 및 수직 방향으로만 이동할 수 있습니다. 그림은 미로의 중앙 지점에서 나오는 출구 경로에 대한 모든 옵션을 보여줍니다.

이 문제를 해결하기 위한 프로그램을 얻으려면 두 가지 문제를 해결해야 합니다.

데이터를 정리하는 방법

알고리즘을 구축하는 방법.

우리는 N x N 크기의 기호 유형의 정사각 행렬 LAB에 미로의 모양에 대한 정보를 저장할 것입니다. 여기서 N은 홀수입니다(중심점이 있으므로). 미로의 윤곽에 격자가 겹쳐져 각 셀에 벽이나 통로가 있습니다.

행렬은 그리드 채우기를 반영합니다. 통로에 해당하는 요소는 공간과 같고 벽은 일부 기호(예: 문자 M)와 같습니다.

미궁을 통과하는 경로는 + 기호로 표시됩니다.

예를 들어 위 그림(가운데)은 다음 LAB 매트릭스 완성에 해당합니다.

초기 데이터 - 미로의 프로필(십자가 없는 초기 LAB 매트릭스) 결과는 미로의 중심점에서 가능한 모든 출구 궤적입니다(각 경로에 대해 LAB 매트릭스는 십자형으로 표시된 궤적으로 표시됩니다).

역추적 알고리즘은 시행법이라고도 합니다.

그 본질은 다음과 같습니다.

1. 궤적의 각 연속 지점에서 가능한 이동 방향이 동일한 순서로 표시됩니다. 우리는 시청이 매번 시계 반대 방향(오른쪽 위-왼쪽-아래)으로 발생한다는 데 동의합니다. 첫 번째로 검출된 자유 이웃 셀로 이동하는 단계입니다. 단계가 수행되는 셀에는 십자 표시가 표시됩니다.

3. 단계를 밟은 다음 셀이 미로의 가장자리(출구)에 있는 경우 발견된 경로가 인쇄됩니다.

순차적인 디테일링 방법을 사용하여 프로그램을 구축해보겠습니다. 세부화의 첫 번째 단계:

GO 프로시저는 x, y 좌표를 사용하여 셀 안으로 들어가려고 합니다. 이 셀이 미로의 출구에 있으면 이동 경로가 인쇄됩니다. 그렇지 않은 경우 위에 설정된 순서에 따라 인접한 셀로 단계가 진행됩니다. 셀이 막다른 골목에 있으면 한 단계 뒤로 이동합니다. 위에서부터 절차는 본질적으로 재귀적입니다.

먼저 세부사항 없이 절차의 일반적인 개요를 적어 보겠습니다.

발견된 궤적을 출력하기 위해 PRINTLAB 프로시저가 컴파일됩니다.

최종 프로그램은 다음과 같습니다:

재귀 프로시저 정의를 사용한 아름다운 프로그램의 또 다른 예입니다(하노이 타워를 기억하세요!).

이 프로그램의 알고리즘은 역추적 방법에 일반적입니다. 예를 들어 체스판 주위에서 조각을 이동하거나 체스판에서 조각이 서로 "충돌"하지 않도록 배열하는 일반적인 문제를 해결하는 데 유사한 알고리즘이 사용됩니다. 일련의 최적 선택 문제(여행하는 외판원 문제, 최적 도로 건설 문제 등).

논평. GO 프로시저에서 LAB 배열을 값 매개변수로 사용하기 때문에 컴퓨터에서 프로그램을 구현할 때 메모리 문제가 발생할 수 있습니다. 이 경우 글로벌 어레이 전송을 진행할 수 있습니다.

무차별 대입 방법을 기반으로 하는 이 방법은 가장 보편적이지만 가장 길기도 합니다.

백과사전 유튜브

1 / 5

✪ 과잉. 그리디 알고리즘: 루프를 사용한 무차별 대입. Foxford 온라인 학습 센터

✪ #82. 산술 진행, 가분성 및 옵션의 철저한 열거! 통합 상태 시험의 수 이론

✪ C++ 알고리즘 무차별 대입(파트 1)

✪ #84. 2개 소대 병사에 대한 문제! 엄격하고 명확한 솔루션. 수학 통합 상태 시험(프로필)

✪ 과잉. 탐욕스러운 알고리즘: 코인 교환 문제. Foxford 온라인 학습 센터

자막

소진방법

술어

영어에서 이 기사에서 논의되는 "brute-force"라는 용어는 일반적으로 일종의 해커 공격을 나타냅니다. 동시에, 문제에 대한 해결책을 찾기 위해 가능한 모든 옵션을 소진하는 수학적 방법인 보다 일반적인 개념은 "소진에 의한 증명"이라는 용어에 해당합니다.

설명

"고갈 방법"에는 다양한 방법의 전체 클래스가 포함됩니다. 일반적으로 문제의 공식화에는 각 상태에 대한 독립적인 분석을 통해 논리적 진술의 진실을 식별하기 위해 주어진 논리 시스템의 유한한 수의 상태를 고려하는 작업이 포함됩니다. 진술을 증명하는 방법은 두 부분으로 구성됩니다.

1. 시스템의 모든 상태를 소진시킬 가능성을 증명합니다. 시스템의 특정 상태(예: 증명되는 논리식의 값)가 고려 중인 후보 솔루션 중 적어도 하나와 일치함을 보여주는 것이 필요합니다.
2. 각 옵션을 확인하고 고려 중인 옵션이 문제에 대한 해결책인지 아닌지를 증명합니다.

철저한 검색 방법으로 해결되는 일반적인 문제

대부분의 응용 문제(특히 암호 해독과 관련되지 않은 문제)에서는 철저한 검색이 실제로 사용되지 않지만 몇 가지 예외가 있습니다. 특히, 완전 검색이 여전히 최적인 것으로 판명되거나 첫 단계알고리즘 개발 과정에서 그 사용이 정당화됩니다. 완전 검색의 최적성의 예로는 행렬의 연쇄 곱을 계산하는 시간을 추정하는 알고리즘이 있는데, 이는 무차별 대입 방식에 기반한 알고리즘에 비해 속도를 높일 수 없습니다. 이 알고리즘은 동적 프로그래밍의 고전적인 문제를 해결하는 데 사용됩니다. 즉, 다음 형식의 행렬 곱 계산 우선 순위를 결정합니다. A 1 A 2 A 3 ⋯ An (\displaystyle A_(1)A_(2)A_(3)\cdots A_(n)).

무차별 대입 사용의 예

초기 문제는 최소한의 시간 내에 주어진 체인(행렬 곱)을 계산하는 것입니다. 필요한 제품을 계산하는 간단한 순차 알고리즘을 구현하는 것이 가능합니다. 행렬 곱은 결합 연산이므로 체인의 요소 쌍을 무작위로 선택하여 체인 곱을 계산할 수 있습니다. (A i A i + 1) , i = 1..n − 1 (\displaystyle (A_(i)A_(i+1)),i=1..n-1)그리고 이를 결과 행렬로 대체합니다. A i 1: A i 1 = (A i A i + 1) (\displaystyle A_(i)^(1)\colon A_(i)^(1)=(A_(i)A_(i+1)) ). 설명된 절차를 반복하면 n − 1 (\displaystyle n-1)횟수를 곱하면 나머지 결과 행렬은 다음과 같습니다. A k n − 1 (\displaystyle A_(k)^(n-1))대답은 다음과 같습니다. A k n − 1 = (A k n − 2 A k + 1 n − 2) = … = A 1 A 2 A 3 ⋯ A n , k = 1.. n − 1 (\displaystyle A_(k)^(n- 1)=(A_(k)^(n-2)A_(k+1)^(n-2))=\ldots =A_(1)A_(2)A_(3)\cdots A_(n), k=1..n-1). 이 공식은 다음과 같이 설명할 수 있습니다. 매트릭스 체인을 고려해보세요: ⟨ A 1 , A 2 , A 3 , A 4 ⟩ (\displaystyle \left\langle A_(1),A_(2),A_(3),A_(4)\right\rangle ). 이 체인에 해당하는 제품을 계산하는 방법은 다음과 같습니다. A 1 A 2 A 3 A 4 (\displaystyle A_(1)A_(2)A_(3)A_(4)):

(A 1 (A 2 (A 3 A 4))) , (\displaystyle (\color (보라색)()A_(1)(\color (번트오렌지)()A_(2)(\color (벽돌빨간색)() A_(3)A_(4)(\color (빨간 벽돌)))(\color (번트오렌지)))(\color (보라색))),) (A 1 ((A 2 A 3) A 4)) , (\displaystyle (\color (Violet)()A_(1)(\color (BurntOrange)()(\color (BrickRed)()A_(2) A_(3)(\color (빨간 벽돌)))A_(4)(\color (번트오렌지)))(\color (보라색))),) ((A 1 A 2) (A 3 A 4)) , (\displaystyle (\color (보라색)()(\color (벽돌빨간색)()A_(1)A_(2)(\color (벽돌빨간색))) (\color (번트오렌지)()A_(3)A_(4)(\color (번트오렌지)))(\color (보라색))),) ((A 1 (A 2 A 3)) A 4) , (\displaystyle (\color (보라색)()(\color (번트오렌지)()A_(1)(\color (브릭레드)()A_(2) A_(3)(\color (빨간 벽돌)))(\color (번트오렌지)))A_(4)(\color (보라색))),) (((A 1 A 2) A 3) A 4) . (\displaystyle (\color (보라색)()(\color (번트오렌지)()(\color (빨간색 벽돌)()A_(1)A_(2)(\color (빨간색)))A_(3)(\color (번트오렌지)))A_(4)(\color (보라색))).)

올바른 계산 순서를 선택하면 계산 속도를 크게 높일 수 있습니다. 이를 확인하려면 3개의 행렬 체인의 간단한 예를 살펴보겠습니다. 크기가 각각 같다고 가정합시다. 10 × 100, 100 × 5, 5 × 50 (\표시 스타일 10\times 100,100\times 5.5\times 50). 두 행렬에 크기를 곱하는 표준 알고리즘 p × q , q × r (\displaystyle p\times q,q\times r)숫자에 비례하는 계산 시간이 필요함 p q r (\displaystyle pqr)(계산할 스칼라 곱의 수) 따라서 체인을 순서대로 계산합니다. ((A 1 A 2) A 3) (\displaystyle ((A_(1)A_(2))A_(3))), 우리는 얻는다 10 ⋅ 100 ⋅ 5 = 5000 (\displaystyle 10\cdot 100\cdot 5=5000)계산할 내적 (A 1 A 2) (\displaystyle (A_(1)A_(2))), 게다가 추가 10 ⋅ 5 ⋅ 50 = 2500 (\displaystyle 10\cdot 5\cdot 50=2500)두 번째 행렬 곱을 계산하기 위한 내적. 총 스칼라 곱 수: 7500. 계산 순서를 다르게 선택하면 다음을 얻습니다. 100 ⋅ 5 ⋅ 50 = 25000 (\displaystyle 100\cdot 5\cdot 50=25000)...을 더한 10 ⋅ 100 ⋅ 50 = 50000 (\displaystyle 10\cdot 100\cdot 50=50000)내적, 즉 75,000개의 내적입니다.

따라서 이 문제를 해결하면 행렬 체인을 계산하는 데 소요되는 시간을 크게 줄일 수 있습니다. 이 솔루션은 철저한 검색을 통해 얻을 수 있습니다. 가능한 모든 계산 순서를 고려하고 체인을 계산할 때 가장 적은 수의 스칼라 곱을 차지하는 순서를 선택해야 합니다. 그러나 이 알고리즘 자체에는 지수적인 계산 시간이 필요하므로 긴 행렬 체인의 경우 가장 효율적인 방법(최적 전략)으로 체인을 계산하여 얻을 수 있는 이득은 이를 찾는 데 걸리는 시간에 의해 완전히 손실될 수 있다는 점을 고려해야 합니다. 전략.

'분할 정복' 개념과의 연관성

알고리즘 이론의 기본 개념에 대한 또 다른 놀라운 예는 "분할 및 정복"의 원리입니다. 이 개념은 시스템이 원래 시스템과 구조가 유사한 여러 하위 시스템으로 분할될 수 있는 경우에 적용 가능합니다. 이러한 경우 하위 시스템은 분리될 수도 있고 사소할 수도 있습니다. 이러한 시스템의 경우 처음에 제기된 문제는 사소한 것입니다. 따라서 “분할 정복” 개념의 구현은 본질적으로 반복적입니다.

재귀는 철저한 검색의 한 유형입니다. 따라서 재귀는 다음에만 적용 가능합니다. 개별 시스템. 그러나 이 요구 사항은 특정 시스템의 상태가 아니라 해당 시스템의 상태에 적용됩니다. 기초 공사. 모든 수준에 대한 일관된 고려는 전체 개별 시스템에 제기된 문제에 대한 포괄적인 솔루션을 제공합니다.

완전 검색의 다른 예와 비교할 때 재귀 방법의 특징은 최종 솔루션이 하나의 사소한 하위 시스템에 의존하지 않는다는 것입니다. 일반적인 경우 솔루션은 전체 하위 시스템 세트를 기반으로 구성됩니다.

고전적인 분할 정복 문제에 대한 다음 예의 경우, 철저한 검색은 알려진 유일한 해결 방법이거나 더욱 최적화된 원래 구현입니다.

무차별 공격

문자 수	옵션 수	내구성	검색시간
1	36	5비트	1초 미만
2	1296	10비트	1초 미만
3	46 656	15비트	1초 미만
4	1 679 616	21비트	17초
5	60 466 176	26비트	10 분
6	2 176 782 336	31비트	6 시간
7	78 364 164 096	36비트	9일
8	2,821 109 9x10 12	41비트	11개월
9	1.015 599 5x10 14	46비트	32년
10	3.656 158 4x10 15	52비트	1,162년
11	1.316 217 0x10 17	58비트	41,823년
12	4,738 381 3x10 18	62비트	1,505,615년

따라서 최대 8자 길이의 비밀번호는 일반적으로 강력하지 않습니다. 최신 컴퓨터의 경우 이 수치는 훨씬 더 높습니다. 그래서 64비트 키(비밀번호)는 현대의 컴퓨터에서 약 2년이면 검색이 가능하고, 그 검색은 여러 컴퓨터에 쉽게 분산될 수 있다.

공격수단

최신 개인용 컴퓨터를 사용하면 위 표에 설명된 효율성으로 무차별 대입 방법을 사용하여 비밀번호를 해독할 수 있습니다. 그러나 병렬 컴퓨팅을 기반으로 한 무차별 대입 최적화를 사용하면 공격의 효율성을 크게 높일 수 있습니다. 이를 위해서는 멀티스레드 컴퓨팅에 적합한 컴퓨터를 사용해야 할 수도 있습니다. 최근에는 Nvidia Tesla와 같은 GPU를 사용한 컴퓨팅 솔루션이 널리 보급되었습니다. Nvidia가 2007년에 CUDA 아키텍처를 만든 이후 CUDA, FireStream, OpenCL과 같은 기술을 사용하여 키 선택을 가속화할 수 있는 많은 솔루션이 나타났습니다(예: Cryptohaze Multiforcer, Pyrit 참조).

무차별 대입 공격에 저항

무차별 공격과 관련된 정보 보안 시스템을 개선하는 과정에서 두 가지 주요 방향을 구분할 수 있습니다.

1. 보호된 정보의 액세스 키에 대한 요구 사항이 증가하고 있습니다.
2. 보안 시스템의 모든 구성 요소의 신뢰성을 높입니다.

따라서 이러한 매개변수 중 하나만 개선하여 높은 수준의 보호를 달성하는 것은 불가능합니다. . 최적의 비밀번호 복잡성을 기반으로 한 인증 시스템이 공격자의 로컬 컴퓨터에 데이터베이스를 복사하는 데 취약한 것으로 밝혀진 후 원격으로는 사용할 수 없는 로컬 최적화 및 컴퓨팅 도구를 사용하여 무차별 대입 공격을 받은 사례가 있습니다. 암호 분석. 이러한 상황으로 인해 일부 컴퓨터 보안 전문가는 비밀번호를 최대한 오래 유지하는 것과 같은 표준 보안 지침에 대해 보다 비판적인 관점을 취할 것을 권장했습니다. 다음은 무차별 대입 공격과 관련하여 암호화 시스템의 신뢰성을 높이기 위해 실제로 사용되는 몇 가지 방법 목록입니다.

무차별 최적화 방법

분기 및 바인딩 방법

계산의 병렬화

키 선택 속도를 높이는 방법 중 하나는 계산 병렬화입니다. 병렬화에는 두 가지 접근 방식이 있습니다.

• 첫 번째 접근 방식은 파이프라인을 구축하는 것입니다. 비율 알고리즘을 보자 E k (x) = y (\displaystyle E_(k)\ (x)=y)간단한 작업(작업)의 체인으로 표현될 수 있습니다. 오 1, 오 2, . . . , O N (\표시스타일 (O_(1)\ ,O_(2),...,O_(N))). 해 보자 N (\디스플레이스타일 N\ )프로세서 A 1 , A 2 , . . . , A N (\표시스타일 (A_(1)\ ,A_(2),...,A_(N))), 순서를 설정하고 다음과 같이 가정하겠습니다. 나는 (\디스플레이스타일 i\ )- 번째 프로세서는 동시에 세 가지 작업을 수행합니다. 그런 다음 파이프라인은 N (\디스플레이스타일 N\ )직렬 연결, 병렬 및 동기식 작동 프로세서가 빠른 속도로 작동합니다. v / 3 (\displaystyle v/3\ ), 어디 v (\디스플레이스타일 v\ )- 하나의 프로세서로 하나의 작업을 실행하는 속도.
• 두 번째 접근 방식은 세트입니다. K (\디스플레이스타일 K\ )가능한 모든 키는 분리된 하위 집합으로 나뉩니다. 케이 1 케이 2 , . . . , K N (\표시스타일 (K_(1)\,K_(2),...,K_(N))). 시스템의 Q (\디스플레이스타일 Q\ )자동차는 열쇠를 분류하여 나는 (\디스플레이스타일 i\ )- 기계는 세트에서 키를 검색합니다. K i , i = 1.. Q (\displaystyle K_(i)\ ,i=1..Q). 기계 중 하나가 키를 찾으면 시스템 작동이 중지됩니다. 가장 어려운 것은 키 세트를 나누는 것입니다. 그러나 각 프로세서가 임의의 키를 사용하여 계산을 시작하면 검색 시간이 늘어나고 회로가 크게 단순화됩니다. 이 경우 평균 걸음 수는 다음과 같습니다. | 케이 | / N (\표시스타일 |K|/N\ ), 어디 | 케이 | (\디스플레이스타일 |K|\ )키 세트의 요소 수입니다. N (\디스플레이스타일 N\ )- 프로세서 수.

레인보우 테이블

외모의 전제 조건

인증을 위해 비밀번호를 사용하는 컴퓨터 시스템은 입력된 비밀번호가 올바른지 여부를 어떻게든 확인해야 합니다. 이 문제에 대한 간단한 해결책은 각 사용자의 유효한 모든 비밀번호 목록을 저장하는 것이지만 이 접근 방식은 안전하지 않습니다. 선호되는 접근 방식 중 하나는 암호에서 암호화 해시 함수를 계산하는 것입니다. 레인보우 테이블은 이 방법을 최적화한 것입니다. 주요 장점은 사용되는 메모리 양이 크게 감소한다는 것입니다.

용법

레인보우 테이블은 가능한 비밀번호 체인을 구성하여 생성됩니다. 각 체인은 무작위 후보 비밀번호로 시작한 다음 해시 함수와 감소 함수를 거칩니다. 이 함수는 해시 함수의 결과를 가능한 암호로 변환합니다. 예를 들어 암호의 길이가 64비트라고 가정하면 축소 함수는 해시의 처음 64비트를 가져와 모든 64비트 해시 블록을 추가할 수 있습니다. 비트 단위 등) . 체인의 중간 비밀번호는 삭제되고 체인의 첫 번째 요소와 마지막 요소만 테이블에 기록됩니다. 이러한 테이블을 생성하려면 일반 조회 테이블을 생성하는 데 걸리는 시간보다 더 많은 시간이 필요하지만 메모리는 훨씬 적습니다(최대 수백 기가바이트, 일반 테이블의 볼륨은 N 단어인 반면 레인보우 테이블에는 약 N 2/3만 필요함). 동시에 원래의 비밀번호를 복구하는 데 (기존 방법에 비해) 더 많은 시간이 필요하지만 실제로는 더 실현 가능합니다(바이트 문자로 6자 비밀번호에 대한 일반 테이블을 구축하려면 256 6 = 281,474,976,710,656 메모리 블록) 무지개의 경우에는 256 6·⅔ = 4,294,967,296 블록만 필요합니다.

비밀번호를 복구하기 위해 이 해시값을 축소 함수에 적용하여 테이블에서 조회합니다. 일치하는 항목이 없으면 해시 함수와 축소 함수가 다시 적용됩니다. 이 작업은 일치하는 항목을 찾을 때까지 계속됩니다. 일치하는 항목이 발견되면 이를 포함하는 체인이 재구성되어 버려진 값(검색된 비밀번호가 됨)을 찾습니다.

그 결과, 높은 확률로 단시간에 비밀번호를 복구할 수 있는 테이블이 탄생했다.

사건

정보 시스템의 모든 보호는 우선 무차별 대입 공격에 대해 안정적이어야 하지만 공격자가 이 공격을 성공적으로 사용하는 경우는 매우 일반적입니다.

수수께끼 공격

1918년에 발명된 Enigma라는 암호화 기계는 1929년부터 독일 해군에서 널리 사용되었습니다. 그 후 몇 년에 걸쳐 시스템이 수정되었으며, 1930년부터 제2차 세계 대전 중에 독일군과 정부가 적극적으로 사용했습니다.

Enigma 코드로 암호화된 메시지를 최초로 가로채는 것은 1926년으로 거슬러 올라갑니다. 그러나 그들은 오랫동안 메시지를 읽을 수 없었습니다. 제2차 세계 대전 내내 폴란드와 독일의 암호 해독가들 사이에 대립이 있었습니다. 독일 암호 시스템을 해킹하여 또 다른 결과를 얻은 폴란드인들은 Enigma 시스템을 지속적으로 현대화하는 독일 엔지니어들에 의해 도입된 새로운 어려움에 직면했습니다. 1939년 여름, 폴란드 침공의 불가피성이 명백해지자 국은 작업 결과를 영국과 프랑스 정보부에 넘겼습니다.

Bletchley Park에서 추가 해킹 작업이 조직되었습니다. 암호 분석가의 주요 도구는 폭탄 암호 해독 기계였습니다. 그 프로토타입은 폴란드 국방부를 위해 제2차 세계 대전 직전에 폴란드 수학자에 의해 만들어졌습니다. 이러한 개발과 제작자의 직접적인 지원을 바탕으로 영국에서 보다 "고급" 장치가 설계되었습니다.

작업의 이론적 부분은 Alan Mathieson Turing이 수행했습니다. Enigma 암호 기계에 구현된 알고리즘의 암호 분석에 대한 그의 작업은 폴란드 암호 분석가 Marian Rejewski가 1938년에 수행한 이 기계의 이전 버전에 대한 초기 암호 분석을 기반으로 했습니다. Turing이 개발한 디코더의 작동 원리는 암호 키의 가능한 변형을 열거하고, 해독되는 메시지의 구조나 일반 텍스트의 일부가 알려진 경우 텍스트를 해독하려고 시도하는 것이었습니다.

현대적인 관점에서 볼 때 에니그마 암호는 그다지 신뢰할 수는 없었지만, 이 요소와 가로채는 많은 메시지, 코드북, 정보 보고서, 군사적 노력의 결과, 심지어 테러 공격까지의 조합만이 가능했습니다. 암호를 깨십시오.

WASP를 이용한 홈 네트워크 대규모 해킹

또한보십시오

노트

문학

• Reid, D.A.et al.  수학 교육: 연구, 학습, 및 교육. - John Wiley & SSense 출판사, 2010. - P. 266. - ISBN 978-9460912443.
• Paar, Christofet al.,.

3) 수학적 장치의 선택. 모델을 구성하는 데 사용되는 수학적 장치는 모델 유형에 따라 다릅니다. 따라서 계산 모델을 알고리즘화하기 위해 복잡한 분석 공식, 선형 또는 미분 방정식 시스템(Kirchhoff의 법칙, 노드 전류 및 루프 전압 방법)이 사용됩니다.

예측 모델을 알고리즘화하기 위해 잘 알려진 계산 모델 알고리즘이 사용되어 시스템의 초기 데이터와 예측 매개변수를 강조합니다.

최적화 모델의 수학적 설명을 위해 특별한 수학적 방법, 즉 최적화 방법이 사용됩니다.

3. 세 번째 단계는 구성된 모델 알고리즘을 컴퓨터에 구현하는 것입니다.

4. 수치 모델링 결과, 적절성 평가 및 사용을 위한 모델의 일반적인 적합성을 연구합니다.

5. 모델링 결과를 해석하고 수학적 모델의 사용 또는 개발 필요성에 대한 결정을 내립니다. 여기서 모델의 수명주기와 모델 업데이트 필요성, 즉 작동 조건 변경으로 인한 매개변수 변경이 결정됩니다.

최적화 방법

사람들은 활동을 시작하기 시작할 때 결과를 평가하고 결정을 내리며 활동과 프로세스를 구성하는 방법에 따라 달라지는 매개 변수를 선택합니다. 결정 이론은 최적화 모델을 사용하고 최적화 문제를 해결합니다.

최적화의 목표는 프로세스에 대한 조건을 선택하거나 일부 시스템 매개변수를 선택하여 모델링된 시스템 또는 프로세스의 일부 지표를 개선하는 것입니다.

목적 함수라고 불리는 특정 함수 F(x)가 최적성 기준으로 사용됩니다. 목적 함수는 제어된 매개변수라고 불리는 값이 변경될 수 있는 일부 매개변수 x에 대한 최적화된 지표의 의존성을 분석적으로 표현합니다.

xi, i = 1,2,...,n.

제어된 매개변수 xi는 서로 독립적이며 최적화 프로세스 중에 알려진 한계(허용 영역) Dx 내에서 변경될 수 있습니다. 분석적으로 허용 가능한 값의 범위는 일련의 함수 형태로 분석적으로 지정될 수 있습니다.

Ψ k (x 1 ,...,xn )= 0

일반적으로 수학적 최적화 문제는 다음과 같이 공식화될 수 있습니다.

제어되는 변수에 대한 제한을 고려하여 목적 함수를 최소화(최대화)합니다.

주어진 세트 Dx에서 n 변수 F(x)=F(x1, ... ,xn)의 함수를 최소화(최대화)한다는 것은 주어진 세트 Dx에서 이 함수의 전역 최소값(최대값)을 결정하는 것을 의미합니다.

제어되는 매개변수의 허용 가능한 변경 범위는 항상 볼록한 것은 아니며 단순히 연결되지 않을 수도 있습니다. 비선형 제약 조건 시스템을 분석적으로 풀고 복잡한 비선형 목적 함수의 극점을 분석적으로 찾는 것은 종종 불가능합니다.

목적 함수(F(x) -> max)를 최대화하는 것은 반대 수량(−F(x) -> min)을 최소화하는 것과 동일하므로 최소화 문제만 고려할 수 있습니다.

비선형 최적화 문제를 해결하는 보편적인 방법은 없지만 개발되었습니다. 많은 수의 1차원 단봉, 다차원 단봉, 1차원 다중 모드 또는 다차원 다중 모드 목적 함수의 최적화 문제를 해결하는 데 사용되는 방법입니다.

1차원 최적화 문제를 해결하기 위한 수치적 방법

1차원 최소화 문제는 목적 함수가 하나의 변수에 의존하고 허용 가능한 집합이 실수 축의 세그먼트인 가장 간단한 수학적 최적화 모델을 나타냅니다.

F(x) -> min , x 는 에 속합니다.

하나의 제어 변수에 적용된 최적화 문제는 1차원 최소화의 수학적 문제로 이어집니다. 또한 더 복잡한 최적화 문제를 해결하기 위한 일부 방법을 구현할 때 한 변수의 기능을 최소화해야 할 필요성이 발생합니다.

세그먼트에서 함수 F(x)를 최소화하는 문제를 해결하기 위해 실제로는 근사 방법이 일반적으로 사용됩니다. 세그먼트의 일부 지점에서 함수 F(x)와 그 파생어의 유한한 수의 값을 결정하여 필요한 정확도로 이 문제에 대한 해결책을 찾을 수 있습니다. 함수의 값만 사용하고 도함수 계산이 필요하지 않은 방법을 직접 최소화 방법이라고 합니다.

직접법의 가장 큰 장점은 목표 함수가 미분 가능하지 않아도 되며 분석 형식으로 지정되지 않을 수도 있다는 것입니다. 직접 최소화 방법의 알고리즘이 기반으로 하는 유일한 것은 주어진 지점에서 F(x) 값을 결정하는 능력입니다.

이러한 방법을 사용할 수 있는 함수 F(x)에 대한 가장 약한 요구 사항은 단봉성(허용 가능한 값 범위에 하나의 최소값이 존재함)입니다. 따라서 함수 F(x)가 구간에서 단봉이라고 가정합니다.

무차별 대입 방식

무차별 탐색 또는 균일 탐색 방법은 직접 최소화 방법 중 가장 간단하며 다음과 같이 구성됩니다.

분할점을 사용하여 세그먼트를 n개의 동일한 부분으로 나눕니다.

xi =A+i·(B − A)/n, i=0,...n

점 xi에서 F(x)의 값을 계산한 후 비교를 통해 점 xm을 찾습니다. 여기서 m은 0에서 n까지의 숫자입니다.

F(xm) = 0부터 n까지의 모든 i에 대한 최소 F(xi)입니다.

열거법을 사용하여 함수 F(x)의 최소점 xm을 결정할 때의 오류는 ε = (B − A)/n 값을 초과하지 않습니다.

이분법적 방법

이 방법은 비선형 1차원 단봉 목적 함수의 최대 극값 또는 최소 극값을 찾는 데 사용됩니다.

이 방법의 본질은 다음과 같습니다. 목적 함수 F(x)를 구간 A≤ x ≤ B에 지정합니다. 세그먼트는 각 단계에서 절반으로 나뉩니다. 처음 두 검색의 경우

x1, x2 지점에서 목적 함수 F(x)를 계산하면 검색 방향이 구체화됩니다. 극한-최소값을 구하고 F(x1)< F(х2 ), то смещается правая граница первоначального интервала неопределенности , т.е. полагается В = x2 , если F(х1 ) >F(x2)이면 왼쪽 경계 A = x1이 이동됩니다. 새로운 불확실성 구간 [В−А]가 주어진 해 오류 ε보다 큰 경우,

반감기는 계속된다. B−A ≤ ε이면 해는 x* =A + 2 B , F(x) = F(x*)입니다.

피보나치 방법

이분법은 불확실성 간격을 지속적으로 줄이는 동시에 식별 모델을 최적화할 때 일반적으로 복잡한 목적 함수의 두 값을 계산하거나 두 가지 검색 실험을 설정해야 합니다. 피보나치 검색에는 이러한 단점이 없습니다. 피보나치 방법은 일련의 피보나치 수열을 사용하여 해가 있는 불확실성 구간을 감소시키는 방식을 기반으로 합니다. 피보나치 수열은 반복 공식으로 표현됩니다.

Nn =Nn-1 +Nn-2, N1 =N2 =1.

초기 불확실성 구간 [В−А]은 다음과 같이 결정된 특정 피보나치 수 Fn에 비례하는 것으로 가정됩니다.