대화:2만족도
위키프로젝트 컴퓨터 과학 | (정격 GA급, 중간중간) | ||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
2-만족도에서 나온 사실이 위키피디아의 메인페이지에 실렸다. 알고 있었니? 2016년 10월 29일 칼럼(Check views) 기재 내용은 다음과 같았다. 이 항목의 기록은 위키백과에서 볼 수 있다.최근 추가/2016/10월. 지명 토론 및 검토는 템플릿에서 확인할 수 있다.후보/2-만족도를 아십니까? |
모순
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)[]
- 말이 되긴 하지만, 그건 말이 안 돼. 언급된 모든 것은 그 조항을 어떻게 만들 것인가 하는 것 뿐이며, 그것의 일관성은 동일하며, 그렇지 않으면 그것이 일관성이 없는 조항으로 축소되는 이유는 아니다. 내가 직접 덧붙이고 싶지만, 크롬이 자신의 논문에 접근할 수 없는(한 달 전이라면...)이라고 한 말인지 확신할 수 없다. 그래, 지금은 더 나은 알고리즘이 있지만, 쿡이 논문을 쓸 때 가장 빨리 보여지고 사용 중인 알고리즘이 역사적 이유로 중요한 것 같아. 그리고 만약 비슷한 공식들이 서술적 복잡성에 여전히 유용하다고 생각한다면. 트윈버드 (토크) 05:32, 2011년 6월 8일 (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)
- 그것이 "일관성 유지"가 의미하는 바는 무엇인가? 공식은 일관성이 있고, 새로운 공식에 만족스러운 과제가 있다면, 그 모든 조항들을 충족하는 것이어야 한다는 것을 쉽게 알 수 있다. 그러나 그것은 그 과제가 실제로 그것을 만족한다는 것을 보여주지는 않지만, 일관된 공식은 만족한다는 사실을 증명하려고 하는 것이 바로 이 단락의 이 부분인 것이다. 트윈버드 (토크) 23:17, 2011년 6월 3일 (UTC)[]
GA 리뷰
- 이 리뷰는 Talk:2-만족성/GA1에서 벗어난다. 이 섹션의 편집 링크를 사용하여 검토에 주석을 추가할 수 있다.
검토자: Falcon Kirtaran (토크 · 기여) 04:52, 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)[]