search

prosyslab-classroom / cs424-program-reasoning

42 stars 15 forks source link

readme

CS424: 프로그램 논증 (Program Reasoning)

계획 Logistics

강의 소개 Course Description

본 강의의 핵심 주제는 안전하고 믿을만한 소프트웨어를 만들기 위한 "명세와 구현 사이의 관계"입니다. 크게 아래와 같은 두 가지 세부 주제를 다룹니다:

  1. 프로그램 검증 (program verification): 주어진 구현이 해당 명세를 만족하는지 어떻게 자동으로 증명할 것인가?
  2. 프로그램 합성 (program synthesis): 주어진 명세를 만족하는 구현을 어떻게 자동으로 만들어낼 것인가?

학생들은 강의와 숙제를 통해 프로그램 검증과 합성의 이론과 실제를 배울 것입니다.

The main theme of this course is "the relationship between specification and implementation" for safe and reliable software. This course will cover two topics under the theme:

  1. program verification: how to automatically prove whether a given implementation satisfies the specification,
  2. program synthesis: how to automatically generate an implementation that satisfies the specification.

Students will learn theories and practices of program verification and synthesis through lectures, and assignments.

성적 Grading

P/NR 관련 공지 Note for P/NR

이 강의는 P/NR 성적을 허용하지 않습니다. 신입생은 반드시 교수에게 이메일을 통해 사전 승인을 받은 후 수강신청하길 바랍니다.

This course DOES NOT allow for P/NR grading. Freshmen can enroll in this course only if they have prior approval from the instructor. Send an email to the instructor for approval.

교재 Textbook

숙제 Homework

이 강의에서 학생들은 다양한 프로그래밍 숙제를 통해 프로그램 검증기와 합성기를 설계하고 구현하는 법을 배웁니다. 특히 여기에 있는 몇 가지 도구를 사용할 예정입니다.

모든 숙제 제출은 Github와 Gradescope 를 통해서 이루어집니다. 매 숙제마다 제출을 위한 GitHub Classroom 초대 URL이 게시판에 공지됩니다. 초대를 수락하면, 여러분의 숙제를 위한 비공개 개인 저장소가 만들어 질 것입니다. 여러분은 제출 기한 이전에 원하는 만큼 해당 저장소에 제출할 수 있고, 이 저장소를 Gradescope에 제출하여 채점결과를 확인할 수 있습니다.

기한을 넘겨서 제출할 시 아래와 같은 규정에 따라 채점합니다:

This course includes programming assignments through which students will learn how to design and implement program verifiers and program synthesizers. Students will use a few tools described here.

All submissions will be managed using GitHub and Gradescope. For each assignment, a unique invitation URL for GitHub Classroom will be posted in the Discussion board. Once you accept the invitation, a private repository for your assignment will be created. You can push as many commits as you want before the deadline. You can submit this repository to Gradescope to check your grading results.

The late homework policy is as follows:

학문 윤리 Academic Integrity

학문 윤리를 어긴 수강생은 F를 받습니다. 자세한 사항은 KAIST 전산학부 명예규정을 참고하십시오.

Students who violate academic integrity will get an F. See the KAIST CS honor code.

강의 계획 Schedule

Week Topics Reading Homework
0 Functional Programming in OCaml HW0: Hello-world, OCaml Programming
1 Introduction Undecidability
2 Operational Semantics HW1: SmaLLVM Interpreter
3 Concepts in Program Verification
4 Propositional Logic COC Ch1, Curry-Howard Correspondence
5 First-order Logic COC Ch2
6 First-order Theory COC Ch3 HW2: Automated Theorem Proving
7 Hoare Logic COC Ch5, CACM'21
8 Automated Program Verification HW3: SmaLLVM Verifier
9 Overview of Program Synthesis PS Ch1-2, IPS Lec1, Wired, IEEE Spectrum, CACM
10 Inductive Synthesis and Enumerative Search PS Ch4.1, IPS Lec2-4 HW4: LIA Synthesizer
11 Search Space Pruning
12 Search Space Prioritization CACM'18
13 Representation-based Search HW5: SLIA Synthesizer
14 Constraint-based Search
15 Functional Synthesis HW6: CEGIS
16 Program Synthesis as AI Trustworthy AI
- Final Exam

명예의 전당 Hall of Fame

지난 학기 수강생들이 남긴 멋진 작품을 여기서 감상해 보세요 (에세이, 그림 등).

Have fun with student artifacts from previous semesters here (distinguished essays, drawings, etc).

관련 강의 Related & Advanced Course

감사 Acknowledgement

이 강의의 자료는 아래 강의의 자료를 참고하여 작성하였습니다.

A large part of the slides is based on the lecture notes of similar courses:

참고 References

기본 Preliminaries

프로그램 검증 Program Verification

프로그램 합성 Program Synthesis