알고리즘 공학

알고리즘 공학은 컴퓨터 알고리즘의 설계, 분석, 구현, 최적화, 프로파일링 및 실험 평가에 초점을 맞추며, 소프트웨어 공학에서 알고리즘 이론과 실제 적용 사이의 격차를 해소한다.^[1] 그것은 알고리즘 연구를 위한 일반적인 방법론이다.^[2]

오리진스

1995년, NSF가 후원한 워크샵의 "컴퓨팅 이론(TOC) 커뮤니티의 현재 목표와 방향을 평가하기 위한 목적으로"의 보고서는 실무자들의 이론적 통찰력 채택 속도가 느린 것을 중요한 이슈로 식별하고 대책을 제안했다.

• 특정 이론적 돌파구가 실무 분야에서 실질적인 이득으로 이어질지 여부를 실무자들에 의해 불확실성을 줄인다.
• 알고리즘 문제에 대해 안정적이고 버그 없는 잘 검증된 구현을 제공하고 라이브러리 소비자를 위한 사용하기 쉬운 인터페이스를 노출하는 사용 가능한 알고리즘 라이브러리의 부족을 해결한다.^[3]

그러나 또한, 수학적 분석의 어려움으로 인해 유망한 알고리즘 접근법이 무시되어 왔다.^[2]

"알고리즘 엔지니어링"이라는 용어는 주세페 F가 주관하는 제1회 알고리즘 엔지니어링 워크숍(WAE97)과 함께 1997년에 특수성으로 처음 사용되었다. 이태리노.^[4]

알고리즘 이론과의 차이

알고리즘 공학은 알고리즘 이론을 대체하거나 알고리즘 이론과 경쟁하려는 의도가 아니라 실험 알고리즘학(경험 알고리즘학이라고도 함)으로 형식적 접근방식을 풍부하게 하고 정제하고 강화하려고 한다.

이렇게 하면 다음과 같은 경우에 알고리즘의 효율성과 성능에 대한 새로운 통찰력을 제공할 수 있다.

• 당면한 알고리즘은 알고리즘 이론 분석에 덜 익숙하다.
• 형식 분석은 비관적으로 실제 관심의 투입물에 나타날 가능성이 없는 한계를 제시한다.
• 알고리즘은 알고리즘 이론에 사용된 기계 모델이 필요한 세부사항으로 포착할 수 없는 데이터 지역성, 분기 예측, 명령 스톨, 명령 지연과 같은 현대 하드웨어 아키텍처의 복잡성에 의존한다.
• 상이한 일정한 비용과 점증적 행동을 가진 경쟁 알고리즘 간의 교차점을 결정해야 한다.^[1][5]

방법론

일부 연구자들은 알고리즘 엔지니어링의 방법론을 알고리즘 설계, 분석, 구현 및 실험 평가로 구성된 사이클로서 기계 모델이나 현실적인 입력과 같은 추가 측면과 결합한다고 설명한다. 그들은 설계와 분석, 구현과 실험을 별도의 활동으로 보는 것은 알고리즘 엔지니어링의 요소들 사이의 중요한 피드백 루프를 무시하기 때문에 알고리즘 공학을 실험 알고리즘 공학과 동일시하는 것은 너무 제한적이라고 주장한다.^[2]

실제 모델 및 실제 입력

특정 애플리케이션은 알고리즘 엔지니어링의 방법론 밖에 있지만, 그것들은 문제와 기초 기계의 현실적인 모델을 형성하는 데 중요한 역할을 하며, 실험을 위한 실제 입력물과 다른 설계 매개변수를 제공한다.^[2]

디자인

보통 알고리즘의 점근거동에 초점을 맞춘 알고리즘 이론과 비교하면 알고리즘 엔지니어는 알고리즘의 단순성, 실제 하드웨어의 프로그래밍 언어의 구현성, 코드 재사용 허용 등 추가적인 요구사항을 염두에 둘 필요가 있다. 또한 알고리즘의 상수 인자는 실제 입력에 매우 큰 영향을 미치기 때문에 때로는 증상이 더 나쁜 알고리즘이 상수 인자의 감소로 인해 실제로 더 잘 수행되기도 한다.

분석

어떤 문제는 결정론적 알고리즘보다는 휴리스틱스, 무작위화된 알고리즘으로 더 단순하고 효율적으로 해결할 수 있다. 불행히도, 이것은 고려되어야 할 미묘한 의존성이 있기 때문에 단순한 무작위화된 알고리즘조차 분석하기 어렵게 만든다.^[2]

실행

이론적 통찰력, 공식화된 알고리즘, 프로그래밍 언어 및 하드웨어 사이의 큰 의미적 격차는 작은 구현 세부사항이 실행 동작에 파문을 일으킬 수 있기 때문에 간단한 알고리즘의 효율적인 구현에도 어려움이 있다. 알고리즘의 여러 구현을 비교할 수 있는 신뢰할 수 있는 유일한 방법은 조정과 프로파일링, 여러 아키텍처에서 알고리즘 실행, 생성된 머신 코드 검토에 상당한 시간을 소비하는 것이다.^[2]

실험

참고 항목: 실험 알고리즘

응용공학

실험에 사용되는 알고리즘의 구현은 응용 프로그램에서 사용할 수 있는 코드와 상당한 방식으로 다르다. 전자는 실험 중 측정을 위해 빠른 프로토타이핑, 성능 및 계측을 우선시하지만 후자는 특정 등급의 입력에 대한 철저한 테스트, 유지관리성, 단순성 및 조정이 필요하다.^[2]

알고리즘 라이브러리

LEDA와 같이 안정적이고 잘 테스트된 알고리즘 라이브러리는 애플리케이션에서 새로운 알고리즘의 채택을 가속화함으로써 기술 이전에서 중요한 역할을 한다. 이러한 도서관은 학술연구의 결과를 이해하고 이행해야 하는 부담을 덜어주기 때문에 실무자들에게 필요한 투자와 위험을 줄여준다.

컨퍼런스

알고리즘 엔지니어링에 관한 두 개의 주요 회의가 매년 개최된다.

• 1997년 설립된 SEA(실험 알고리즘) 심포지엄.
• 1999년에 설립된 알고리즘 엔지니어링 및 실험에 관한 SIAM 회의(ALENEX),

1997년 알고리즘 공학 워크숍(WAE'97)이 1997년 9월 11~13일 베니스(이탈리아)에서 개최되었다. 제3회 알고리즘 공학 국제 워크숍(WAE'99)이 1999년 7월 영국 런던에서 열렸다.^[6] 제1회 알고리즘 공학 및 실험 워크숍(ALENEX99)이 1999년 1월 15~16일 메릴랜드 주 볼티모어에서 열렸다.^[7] 이산수학과 이론컴퓨터과학센터(러터스대)인 DIMACS가 후원했으며, 알고리즘과 계산 이론에 관한 ACM 특별 이익 그룹, 산업 및 응용수학협회 SIAM의 추가 지원을 받았다.^[7]

참조