학은제 1학기 6주차 3교시

💽 디지털 공학 개론

POS 표현

• POS
• 특징
  • POS형 함수의 OR-AND 회로 구현 예
  • SOP형 부울 함수를 POS형으로 변형하는 방법
• 정규형 POS
  • 정규형 POS 표현이 아닌 함수의 예
  • 정규형 POS 표현으로의 변환 방법
  • 진리표 작성 방법

정규형 SOP 표현과 POS 표현 간의 변환

• 정규형 SOP >> 정규형 POS 표현 변환 절차
• 정규형 POS >> 정규형 SOP 표현으로 변환하는 방법
• 정규형 표현들 간의 다른 변환 방법
  • 정규형 SOP >> POS 변환 예
  • 정규형 POS >> SOP 변환 예

💻 마이크로프로세서

효율적인 프로그램

• 인터럽터(Interrupt)
  • 인터럽터 발생원
  • ISR 위치
  • EIMSK
• 외부 인터럽터
• 언제 인터럽터가 발생하는가?
  • 3가지 모드
  • EICRA
  • 각각의 INT를 MASK 할 수 있다
  • SREG

입장객 계수기

• 코드

타임 카운트

• 코드

💾 시스템 프로그래밍

프로세스 동기화

• 부모 프로세스와 자식 프로세스의 종료절차
• 동기화 필요 이유
  • 좀비 프로세스 종료
  • 고아 프로세스 종료

프로세스 동기화 함수

• 프로세스 동기화: wait
  • stat_loc: 상태 정보를 저장할 주소
  • wait 함수 사용하기
• 특정 자식 프로세스와 동기화: waitpid
  • pid에 지정할 수 있는 값
    • -1보다 작은 경우
    • -1인 경우
    • 0인 경우
    • 0보다 큰 경우
  • options: waitpid 함수의 리턴 조건
    • WCONTINUED
    • WNOHANG
    • WNOWAIT
    • WUNTRACED
  • waitpid 함수 사용하기

📠 운영체제

단편화

• 내부 단편화
• 외부 단편화
  • 고정 분할
  • 가변 분할

단편화 해결 방법

• 통합 기법
• 압축 기법

📺 전산 개론

정렬 알고리즘

• 정렬(Sorting) 알고리즘
• 비교 정렬 알고리즘
  • 버블 정렬(Bubble Sort)
    • 시간 복잡도: 평균 O(N^2), 최악 O(N^2)
  • 삽입 정렬(Insertion Sort)
    • 시간 복잡도: 평균 O(N^2), 최악 O(N^2)
  • 합병 정렬(Merge Sort)
    • 시간 복잡도: 평균 O(N logN), 최악 O(N logN)
  • 퀵 정렬(Quick Sort)
    • 시간 복잡도: 평균 O(N logN), 최악 O(N^2)
  • 버블, 삽입, 퀵 정렬의 처리 시간 비교

탐색 알고리즘과 문제 해결 방식

• 탐색(Searching) 알고리즘
  • 탐색
• 탐색 알고리즘의 종류
  • 순차 탐색(Sequential Search)
    • 시간 복잡도: 평균 O(N), 최악 O(N)
  • 이진 탐색(Binary Search)
    • 시간 복잡도: 평균 O(logN), 최악 O(logN)
• 문제 해결 방식
  • 다항식 시간 복잡도
  • N-P 완전(NP-Complete) 문제
  • 분할 정복(Devide-and-Conquer) 알고리즘
  • 그리디(Greedy) 알고리즘
  • 동적 계획(Dynamic Programming) 알고리즘
  • 근사(Approximation)
  • 백트래킹(Backtracking) 알고리즘
  • 분기 한정(Branch-and=Bound) 알고리즘