computation-theory

3열

1답변

저는 기본 Primitive Recursive 함수들을 작성하고 있습니다. 그 중 하나는 빼기 함수입니다. 나는 전임자에 대한 정의를 제공하지 않았고, eval Pred [x] = x-1으로 정의 할 수 없다고 생각합니다. 아래는 PR에 대한 나의 정의이며 시간, AND, OR, NOT, PW, TRUE, FALSE 및 ITE와 같이 정의 된 몇 가지 다른

1열

2답변

원시적 인 재귀 만약 그렇다면 실제로 Else가 실행된다면 Then

나는 나의 정의에있는 투영에 문제가있다. 실제로 If-Else-Then으로 실행 중입니다. import Prelude hiding (pred,and,or,not) data PR = Z | S | P Int | C PR [PR] | PR PR PR deriving Show eval :: PR -> [Integ

1열

1답변

Big Theta Notation은 예상 입력 크기가 작은 경우 알고리즘 효율을 효과적으로 측정합니다.

나는 Big-Theta에 관한 정보를 둘러 보았고, 나는 그것에 대해 예의 바르게 이해했다고 생각한다. 그러나 예상되는 입력 크기가 작을 때 Big Theta Notation이 알고리즘 효율성을 효과적으로 측정합니까? 예상되는 입력 크기가 작을 때 Big Theta Notation이 알고리즘 효율성을 효과적으로 측정하지 못한다고 생각합니다. 빅 세타에 대한

0열

1답변

무한대 확인 루프

흥미로운 이론적 인 문제가 발생했습니다 : 프로그램 A와 프로그램 B가 TCP 소켓 또는 명명 된 파이프와 같은 IPC를 통해 연결된 것으로 가정 해 봅니다. 프로그램 A는 프로그램 B에 일부 데이터를 보내고 데이터 전달의 성공 여부에 따라 A와 B 모두 일부 작업을 수행합니다. 그러나 A가 배달 확인을 받았다고 확신하는 경우에만 B가 작업을 수행해야합니다

-1열

1답변

NP-hard의 비주기적인 정의는 무엇입니까?

위키 피 디아에 따르면 NP, NP complete 및 NP hard의 개념을 이해하려고합니다. 내가 올바르게 지정된 텍스트 inderstand 경우 편집 : 수정 데이비드 NP 대답 (솔루션 제공) 다항식 시간에 검증 할 수 == 의사 결정 문제에 따라 NP 완료 == NP 및 NP 하드 NP 하드 == 거기에 NP 완료 문제는 다항식 시간 Turing

2열

2답변

어떤 입력 문자가 정규식의 어느 부분과 일치하는지 확인할 수 있습니까?

문자열에서 패턴을 찾기 위해 정규식과 같은 것을 사용하는 도구를 만들려고합니다 (텍스트 문자열이 아니지만 지금은 중요하지 않습니다). 저는 automata 이론에 익숙합니다. 즉, 기본 정규식을 구현하는 방법을 알고, 문자열이 내 정규식과 일치하는 경우 true 또는 false를 출력합니다. 교과서 방식으로 자동 연산을 시뮬레이트합니다. 이 정규식을 나는

5열

1답변

임의의 정규식에서 문맥 자유 문법을 생성하는 알고리즘

누구나 주어진 정규식을 동일한 CFG 규칙 집합으로 변환 할 수있는 알고리즘을 설명 할 수 있습니까? 나는 등의 기본 재료를 해결하는 방법을 알고 (A | B) * : S -> a A S -> a B S -> b A S -> b B A -> a A A -> a B A -> epsilon B -> b A B -> b B B -> epsilon

0열

2답변

모든 무한 언어가 결정 불가능합니까?

나는 무한한 언어가 모두 결정 불가능한가? 무한한 언어를 결정하려고하는 TM이 영원히 반복 될 것이기 때문에 TM은 결정자가 아닌 기억 장치가됩니다. 감사합니다.

1열

1답변

튜링 기계와 아이디어가 떠오른다

나는 튜링 기계에 대해 많은 것을 읽었고 그것이 어떻게 작동하는지 이해하지만 내가 이해할 수없는 것은 무엇을 가르쳐 주려고 하는가? 내가 풀어야 할 문제에 접근 하는가? 내 말은 : 단어가 회문인지 확인하는 것은 예를 들어 내가 배운 책의 11 개 주로 구성됩니다. 나의 현재 지식 상태에서, 빈 종이 위에 앉아서이 모든 주를 떠올리는 것만으로도 불가능할 것

0열

1답변

바이너리 힙 우선 순위 큐에 대한 deleteMin 액세스의 외부 메모리 블록 수는 몇 개입니까?

우선 우선 큐를 연구 중이며이 우선 순위 큐는 내부 데이터 구조로 바이너리 힙을 사용합니다. 블록 크기 M의 외부 메모리 모델을 고려할 때 슬라이드는 deleteMin이 약 2log(n/M) 블록 액세스가 필요하다고 주장합니다. 왜 이런가요? 나는 밑바닥 위로 발견 적 (Wegener 93)을 설명하는 원본 종이에있는 설명을 발견 할 수없고 미끄러짐에서.