대화:2만족도

위키프로젝트 컴퓨터 과학 (정격 GA급, 중간중간)
WikiProject icon 글은 위키백과에서 컴퓨터 과학 관련 기사의 취재를 개선하기 위한 공동 노력인 위키프로젝트 컴퓨터 과학의 범위 내에 있다. 참여하려면 프로젝트 페이지를 방문하여 토론에 참여하고 열려 있는 태스크 목록을 확인하십시오.
GA 이 기사는 프로젝트의 품질 규모에서 GA-Class로 평가되었다.
중앙의 이 기사는 그 프로젝트의 중요도에 대한 중간 평가로 평가되었다.
WikiProject Computer Science에 도움이 되는 사항:

다음은 대기 중인 몇 가지 작업:

모순

SAT 해결사 기사에는 다음과 같이 명시되어 있다.

SAT는 공식이 분리 정규 형태, 즉 각 용어가 리터럴의 결합(AND)인 용어의 분리(OR)로 제한되는 경우(아마도 부정 변수)가 더 쉽다.

CNF를 고집하는 이 페이지의 소개와 정면으로 모순되는 것이 분명해! 누군가 고쳐줄 수 있을까? 리나 (토크) 17:36, 2008년 3월 31일 (UTC)[]

그것은 모순이 아니다. 이분법적인 정상적인 형태의 Sat는 사소한 것이다. 각 용어는 만족스러운 과제를 준다. 일반적으로 접속 정상형 Sat는 딱딱하지만, 2-sat은 DNF만큼 사소하지는 않지만 더 쉬운 (DNF만큼 사소하지는 않지만) 특수한 경우다.David Eppstein (talk) 17:40, 2008년 3월 31일 (UTC)[]

다이어그램이 텍스트와 일치하지 않는 사소한 문제

다이어그램은 변수 v0, v1 등을 사용하는 반면 공식은 x0, x1 등을 사용한다. 다이어그램의 소유자는 이해하기 쉽도록 변수를 v가 아닌 x로 변경할 수 있는가? 텍스트는 v1, v2 등으로 바꿀 수 있지만 x가 오히려 더 전형적이다. 로스 프레이저 (토크) 22:49, 2008년 8월 3일 (UTC)[]

완료. —David Eppstein (대화) 23:05, 2008년 8월 3일 (UTC)[]

임의 2만족도 인스턴스의 오류

본문의 다음 문장은 "m/n이 상수 α α α 1로 고정되어 있으면 만족의 확률은 n이 무한대로 가는 것처럼 한계에 도달하는 경향이 있고, α < 1이 되면 한계는 0인 반면, α > 1이 되면 한계는 1이다."라는 결론을 뒤집은 것 같다. α < 1(변수보다 작은 절)의 경우 한계는 1(대부분 모든 것이 만족스러운 경우)인 반면, α > 1의 경우 한계는 0(대부분 만족스러운 것은 거의 없다)이다. 로스 프레이저 (토크) 22:50, 2008년 8월 3일 (UTC)[]

고쳤어, 잡아줘서 고마워David Eppstein (대화) 23:00, 2008년 8월 3일 (UTC)[]

1979

1979년까지 2SAT가 P에 있는 것이 정말 알려져 있지 않았던가? 놀랐어. 69.111.192.233 (대화) 08:39, 2010년 11월 19일 (UTC)[]

알고리즘 섹션은 1971년과는 다른 다항 시간 알고리즘을 인용하기도 한다. 그러나 1979년의 일이 우선인 것은 이러한 것들을 해결하는 더 좋은 방법이기 때문이다. 그 절에서 강조되는 것은 어떻게 해결할 것인가에 관한 것이지, 적절한 역사적 질서에 사물을 집어넣는 것에 관한 것이 아니다.David Eppstein (토크) 16:43, 2010년 11월 19일 (UTC)[]
Knuth의 컴퓨터 프로그래밍 기술에 따르면, 아스팔 외 연구진(1979년)이 관측한 것은 멜벤 크롬(1967년) 때문이다. 나는 그 기사에 해당하는 참고자료를 추가했다. 이제 우리는 올바른 역사적 질서와 그것을 해결하는 방법에 대한 간결한 설명을 둘 다 가졌으면 한다. 허멜 (토크) 2010년 11월 19일 (UTC)[]
이걸 찾아줘서 고마워. 나는 이미 알지 못한 것을 배웠다.David Eppstein (대화) 20:10, 2010년 11월 19일 (UTC)[]
고마워. 69.111.192.233 (대화) 02:14, 2010년 11월 20일 (UTC)[]
나는 최근에 알고리즘 부분을 업데이트하여 이러한 기여에 대해 좀 더 자세히 설명하였다. 크누스는 잘못 알고 있는 것 같다: 크롬은 강하게 연결된 부품에 대해서는 아무 말도 하지 않는다. 크롬의 논문은 대신, 크롬이 러닝타임에 대해 명시적인 말을 하지는 않지만, 다항식이지만 비선형인 분해능 증명(또는 전이성 폐쇄)과 본질적으로 같은 기법을 사용한다. 1971년 논문(쿡)에서도 같은 기법을 언급하고 있으며 다항식 시간이라고 한다. 그리고 1976년 논문도 있는데, 선형 시간 알고리즘이 아스팔 외 1편보다 훨씬 더 복잡하다. (이것은 두 개의 평행한 나사산을 인터리빙하는 것을 포함하기 때문이다.)David Eppstein (대화) 20:41, 2011년 2월 5일 (UTC)[]

크롬의 알고리즘에 대한 증거가 불명확해?

그리고 그것이 일관성이 있다면 공식은 한 번에 양식(xx x 또는 (( 의 한 절을 반복적으로 추가하여 모든 변수에 대한 그러한 조항을 포함할 때까지 각 단계의 일관성을 유지할 수 있다. 이러한 각 확장 단계에서 이 두 조항 중 하나는 일관성을 유지하면서 항상 추가될 수 있다. 그렇지 않을 경우 추론 규칙을 사용하여 다른 조항이 생성될 수 있기 때문이다. 모든 변수가 공식에 이 형식의 절을 포함하면, 공식에 해당 조항 x)이 포함된 경우 변수 을(를 true로 설정하고 공식에 cla가 포함된 경우 이를 false로 설정하면 모든 변수의 만족스러운 할당이 생성될 수 있다.( x) x x)}을를) 사용하십시오

이것은 분명 만족스러운 숙제가 무엇인지 보여주지만, 그것이 원래의 모든 조항을 해결한다는 것은 확실하지 않다. 연결된 논문이 유료 데이터베이스 안에 있어서 그의 표현을 찾아볼 수가 없다. 이거 도와줄 사람 있어? 트윈버드 (토크) 20:54, 2011년 6월 3일 (UTC)[]

그게 바로 "일관성 유지" 부분이 의미하는 것이다. 그러나 나는 그것이 확장 조항을 찾는 방법을 설명하지 않는다는 것에 동의한다. 크롬 알고리즘보다 더 효율적인 알고리즘이 나중에 개발되었다는 사실을 감안하면 알고리즘의 모든 세부사항을 설명하는 것은 중요하지 않아 보였다.David Eppstein (대화) 21:05, 2011년 6월 3일 (UTC)[]
그것이 "일관성 유지"가 의미하는 바는 무엇인가? 공식은 일관성이 있고, 새로운 공식에 만족스러운 과제가 있다면, 그 모든 조항들을 충족하는 것이어야 한다는 것을 쉽게 알 수 있다. 그러나 그것은 그 과제가 실제로 그것을 만족한다는 것을 보여주지는 않지만, 일관된 공식은 만족한다는 사실을 증명하려고 하는 것이 바로 이 단락의 이 부분인 것이다. 트윈버드 (토크) 23:17, 2011년 6월 3일 (UTC)[]
크롬의 절차를 따르고 각 변수에 대해 절(x v x) 또는 (~x v ~x)이 있는 일관된 공식을 갖는다고 가정합시다. Then the unique truth assignment determined by these clauses must also satisfy every clause (x v y), for otherwise (if we had the three terms P:(~x v ~x), Q:(x v y), R:(~y v ~y)) applying the inference rule gives QR: (x v ~y), QRQ: (x v x), inconsistent with P. —David Eppstein (talk) 18:17, 4 June 2011 (UTC)[]
말이 되긴 하지만, 그건 말이 안 돼. 언급된 모든 것은 그 조항을 어떻게 만들 것인가 하는 것 뿐이며, 그것의 일관성은 동일하며, 그렇지 않으면 그것이 일관성이 없는 조항으로 축소되는 이유는 아니다. 내가 직접 덧붙이고 싶지만, 크롬이 자신의 논문에 접근할 수 없는(한 달 전이라면...)이라고 한 말인지 확신할 수 없다. 그래, 지금은 더 나은 알고리즘이 있지만, 쿡이 논문을 쓸 때 가장 빨리 보여지고 사용 중인 알고리즘이 역사적 이유로 중요한 것 같아. 그리고 만약 비슷한 공식들이 서술적 복잡성에 여전히 유용하다고 생각한다면. 트윈버드 (토크) 05:32, 2011년 6월 8일 (UTC)[]
나는 더 이상 원래의 크롬 종이에 접근할 수 없을 것 같으니까(옛날에는), 내가 그렇게 하기 전까지는 네가 얻을 수 있는 전부야; 미안.David Eppstein (대화) 05:23, 2011년 6월 11일 (UTC)[]

GA 리뷰

이 리뷰는 Talk:2-만족성/GA1에서 벗어난다. 이 섹션의 편집 링크를 사용하여 검토에 주석을 추가할 수 있다.

검토자: Falcon Kirtaran (토크 · 기여) 04:52, 2016년 10월 10일 (UTC)[]

GA 검토 – WP:기준에 대한 WIGA

  1. 쓰여졌니?
    A. 산문은 명확하고 간결하며, 철자법과 문법은 정확하다.
    B. 리드 섹션, 레이아웃, 시청할 단어, 픽션목록 통합에 대한 스타일 가이드라인 매뉴얼을 준수한다.
  2. 그것은 독창적인 연구 없이 검증 가능한가?
    A. 여기에는 레이아웃 스타일 지침에 따라 표시되는 모든 참조 자료(정보 출처)의 목록이 포함되어 있다.
    B. 모든 인라인 인용문은 직접 인용문, 통계, 발표된 의견, 반직관적이거나 논쟁의 소지가 있는 진술에 대한 인용문, 살아 있는 사람과 관련된 논쟁적 자료 등 신뢰할 수 있는 출처에서 인용한 인용문이며, 과학에 기반한 논문은 다음과 같은 과학적 인용 지침을 따라야 한다.
    C. 본 연구에는 다음과 같은 독창적인 연구가 포함되어 있지 않다.
    D. 저작권 위반이나 표절은 없다.
  3. 범위가 넓은가?
    A. 주제에서 주요 측면을 다룬다.
    B. 불필요한 세부 사항 없이 주제에 초점을 맞춘다(요약 스타일 참조):
  4. 중립인가?
    그것은 논설 편향 없이 공정하게 관점을 나타내며, 각 관점에 적절한 비중을 둔다.
  5. 안정적이야?
    편집 전쟁 또는 콘텐츠 분쟁이 진행 중이기 때문에 매일 크게 변화하지 않는다.
  6. 가능하다면 이미지로 삽화가 되었는가?
    A. 이미지는 저작권 상태태그가 지정되며, 비자유 콘텐츠에 대해 유효한 공정 사용 합리성이 제공된다.
    B. 이미지는 주제와 관련이 있으며 적절한 캡션을 가지고 있다.
  7. 전체:
    통과 또는 실패:
    • 흠잡을 데 없는 일! 이 일에는 단 한 가지도 잘못된 점이 없다. 나의 유일한 코멘트는 그것이 때때로 약간의 텍스트 벽이 될 수 있고, 특히 애플리케이션 섹션에 있는, 무슨 일이 일어나고 있는지를 보여주는 데 도움이 되도록 여기 저기 몇 개의 도표를 더 포함시킴으로써 이익을 얻을 수 있다는 것이다. 나는 이것을 GA로서 꽤 만족한다; FAX에서 행운을 빈다! FalconK (talk) 05:16, 2016년 10월 10일 (UTC)[]


Aspvall/Plass/Tarjan 잘못 표기

"강력하게 연결된 구성요소" 섹션의 위키피디아 기사는 아스팔/플라스/타르얀을 잘못 표현하고 있다.

특히 만족도를 확인하고 (변수에 대한 과제를 찾아내는 것 역시) 응축된 그래프를 구성할 필요가 없다(이 위키백과 기사가 그렇게 들리도록 하는 방법이다).

권장: "응축 구성..."에서 모든 항목 제거 스큐 대칭" — 2601:5C0추가된 선행 부호 없는 설명:C100:178E:E026:A06E:3FDA:33F3 (대화) 06:12, 2016년 10월 31일 (UTC)[]

해당 물질을 제거하면 부품이 위상학적 순서로 나열된다고 말하는 것은 더 이상 말이 되지 않기 때문에 절이 일관되지 않을 것이다. 그 자료를 무엇으로 대체하시겠습니까? 또한, 나는 응축과 같은 더 높은 수준의 개념을 사용하여 그 출처에서 알고리즘을 다시 쓰는 것은 문제가 되지 않는다고 생각한다; 그것은 여전히 본질적으로 동일한 알고리즘이다.David Eppstein (대화) 23:15, 2016년 10월 31일 (UTC)[]