Earticle

Home

0/1 Knapsack에 대한 서브-지수 함수 알고리즘
Sub-Exponential Algorithm for 0/1 Knapsack

첫 페이지 보기
  • 발행기관
    한국융합보안학회 바로가기
  • 간행물
    융합보안논문지 바로가기
  • 통권
    제14권 제7호 (2014.12)바로가기
  • 페이지
    pp.59-64
  • 저자
    이충세
  • 언어
    한국어(KOR)
  • URL
    https://www.earticle.net/Article/A244714

※ 기관로그인 시 무료 이용이 가능합니다.

4,000원

원문정보

초록

영어
We investigate p(n).2o() algorithm for 0/1 knapsack problem where x is the total bit length of a list of sizes of n objects. The algorithm is adaptable of method that achieves a similar complexity for the partition and Subset Sum problem. The method can be applied to other optimization or decision problem based on a list of numerics sizes or weights. 0/1 knapsack problem can be used to solve NP-Complete Problems with pseudo-polynomial time algorithm. We try to apply this technique to bio-informatics problem which has pseudo-polynomial time complexity.
한국어
이 논문에서는 고정된 개수를 가진 bin들을 이용하여 실행 복잡도가 p(n).2o() 인 알고리즘을 제시한다, 여기서 x는 ⑤n개의 객체들에 대한 리스트의 길이에 대한 총 비트 수를 나타낸다. 이러한 방법은 수치적 크기나 비중의 합 의 리스트를 이용하는 여러 가지 최적화 알고리즘이나 결정 문제등에 적용할 수 있다. 이 논문에서 제시한 알고리즘은 의사-다항식(pseudo-polynomial) 시간을 갖는 NP-Complete의 많은 문제들을 결정적인 서브-지수 시간에 해결할 수 있은 가능성을 제시한다. 여기서 제시한 알고리즘을 이용하여 생명공학의 유전자 분석에 적용하려고 한다.

목차

요약
 Abstract
 1. 서론
 2. 분할과 부분 집합의 합
 3. 일반화된 동적 할당에 의한 동적 프로그래밍
 4. 배낭-등(Knapsack) 문제
 5.. Bio-Brick과 Minimum Genome의 설계
 6. 결론
 참고문헌

저자

  • 이충세 [ Chung Sei Rhee | 충북대학교 소프트웨어학과 ]

참고문헌

자료제공 : 네이버학술정보

간행물 정보

발행기관

  • 발행기관명
    한국융합보안학회 [Korea Information Assurance Society]
  • 설립연도
    2001
  • 분야
    공학>전자/정보통신공학
  • 소개
    본 학회는 사이버테러 및 정보전에 관한 학문연구ㆍ기술 개발ㆍ기반 구축을 도모하고 국내ㆍ외 관계기관과 학술교류와 정보교환을 통하여 회원 상호간의 전문지식을 배양하고, 궁극적으로는 국가 중요 정보기반구조를 보호함을 그 목적으로 한다.

간행물

  • 간행물명
    융합보안논문지 [Jouranl of Information and Security]
  • 간기
    격월간
  • ISSN
    1598-7329
  • 수록기간
    2001~2018
  • 등재여부
    KCI 등재
  • 십진분류
    KDC 567.9 DDC 621.38

이 권호 내 다른 논문 / 융합보안논문지 제14권 제7호

    피인용수 : 0(자료제공 : 네이버학술정보)

    페이지 저장