본문 바로가기

전체 글

 (174)
[Lec.Halting] Undecidability, Halting Problem - 11주차 2강 (전공/프로그래밍 언어 및 컴파일러) 2024. 12. 9. 18:29 11월 13일 - 11주차 2강정지 문제를 대학 전공 수업에서 한 번도 다루지 않았다는 사실에 충격을 받은 교수님...급기야 추가 렉쳐를 기획하게 되는데....* 개인 공부를 위해 정리한 것입니다. 정확한 내용은 꼭 본인이 공부하는 교재를 참고하시기 바랍니다. 예, 아니오로 대답할 수 있는 문제유한 오토마타가 문자열을 인식하는가? CFG가 ambiguous 한가?결정 가능 문제: 모든 입력에 대한 올바른 답(예/아니오)를 유한 시간 내에 출력 가능한 알고리즘 존재결정 불가능 문제: 모든 입력에 대해 항상 올바른 답을 출력할 수 있는 알고리즘을 만드는 것이 불가능한 문제TSP 외판원 문제 -  다른 문제로부터 결정 문제로 변가능최적화 문제: 모든 도시를 정확히 한 번씩 방문하고 시작 지점으로 돌아오는 최단..
Lec11. Semantic Analysis (2) - 11주차 2강, 12주차 2강 (전공/프로그래밍 언어 및 컴파일러) 2024. 12. 9. 15:39 11주차 2강, 12주차 2강 11/13, 11/2011/18은 휴강 lec10에서 언급한 내용임Abstract Interperetation의 주요 단계abstract domain: 변수는 구체적인 값 대신 추상화된 값으로 표현 됨변수의 값이 가질 수 있는 범위 또는 특성을 정의, 구간 / 옥타곤, 짝홀 등구체적인 의미로는 7에 2를 더하면 9가 되지만, 추상적인 의미로는 홀수에 2를 더하면 홀수이다연산, 불리안 판별, command 처리에 대한 simple language 만드는 과정추상 도메인 개요새로운 기호들이 등장하는데, 본문 슬라이드 내용과 같고이상하게 생긴 육각형은 맨위의 any부터 시작해서 아래로 뻗어나오는 tree처럼 생각하면 됨any: 모든 값 포함non-pos: 0 또는 음의 정수, n..
Lec10. Semantic Analysis (1) - 11주차 1강 (전공/프로그래밍 언어 및 컴파일러) 2024. 12. 9. 15:24 11월 11일, 11주차 1강* 개인 공부를 위해 정리한 것입니다. 정확한 내용은 꼭 본인이 공부하는 교재를 참고하시기 바랍니다.  soundness: 정확성분석기가 p가 안전하다고 생각하면, 실제로 p는 안전해야 한다만약 p가 안전하지 않다면, 분석기는 반드시 unsafe로 판단해야 한다분석기가 error를 놓치지 않아야 한다. no false negativecompleteness: 완전성p가 실제로 안전하다면, 분석기는 반드시 p의 안전성을 증명해야 하낟분석기가 p를 unsafe로 판단했다면, p는 실제로 안전하지 않음분석기가 안전한 프로그램을 위험하다고 판단하지 않아야 한다. no false positive이상적인 분석기: no false negative, no false positivehard l..

티스토리툴바