Karice의 여행 & 코딩 블로그

1.1 Problem Description

-Problem

: May contain variables that are assigned specific values in the statement of the problem description

-Prarmeters 

: 방금 말한 변수를 parameter라고 한다. 예를 들어 search를 하려면 S, n , x의 3개의 parameter가 필요

-Instance 

: parameters 가 specified되면 우리는 Instance라고 부른다. 예를 들어 S = [1,2], n = 6, x = 8 

1.2 Algorithm Description

-Natural languages

-programming languages

-Pseudo-code

: java,c랑 비슷하지만 같지는 않음 코드를 간단하게 나타낸다고 생각하면된다. 

이제 부터 작성하는 모든 코드는 Pseudo-code이다.

ex) low <= x <= high이렇게 써도 되고 x와 y의 값을 바꿀때는 exchange x and y라고 하면 된다.

1.3 Sequential Search

쉽게 말해서 첫번째 부터 일일이 같나 계산하는 알고리즘이다.

Worst Case n번 계산하기 때문에 별로 좋은 Search 알고리즘이 아니다.

1.4 Binary Search

쉽게 말해서 반을 쪼개고 정렬이 되있으니 중앙값이 더 작으면 오른쪽 크면 왼쪽으로 가는 것을 반복한다.

S는 미리 Sort가 되있어야만 가능하다.

Worst Case Log(n) + 1이 나오기 때문에 꽤 좋다고 할 수 있다.

두 Search 알고리즘을 비교해 보자

1.5 Fibonacci Sequence

1st Version (Recursive)

그냥 원하는 숫자를 더하기 위해 중복된 것도 다 계산하는 것이다 매우 비효율적이다

Worst Case와 Best Case 모두 2의 2분의 n승이다 

시간이 너무 오래걸리는데 재귀식말고 다른 방법을 알아보자

위 그림에서 보면 fib(3)을 두번이나 구하는 모습이다. 매우 비효율적

*Counting the number of calls needed in fib(n)

Theroem 1.1 T(n) > 2 **n/2

2nd Version (Iterative)

Iterative 버전이 Recursive 버전 보다 더 빠르다는 것을 알수있다. 왜그럴까? 어떻게 해서 빨라졌을까?

--> Iterative버젼은 배열에 f(1)부터 차근차근 저장을 한다. 그래서 중복된 값을 계산하지 않아서 빨라짐

Time Complexity : T(n) = n + 1

두 알고리즘을 비교해 보자

1.6 Analysis of Algorithms

Every-case analysis

Worst-case analysis 

Average-case analysis

Best-case analysis

결론

Analysis of Correctness

알고리즘의 효율을 따지기 이전에 우선 알고리즘이 맞아야한다!!

3.6 Null Values

Null : an unknown value or that a value does not exist

Null과 수학적 계산 을 하면 모두 null이 나온다  ex) 5 + null = null

is null : Null이 있는 지 체크한다

Null에 부등호나 등호를 씌우면 모두 unknown이 된다.

*중요! (true와 or을 하면 무조건 true, false 와 and를 하면 무조건 False, not unknown = unknown)

3.7 Aggregate Functions

These functions operate on the multiset of values of a column of a relation, and return a value.

-avg : average value

-min : minimum value

-max : maximum value

-sum: sum of values

-count : number of values

Group By

Having

count(*) 빼고 모든 operation이 null을 만나면 NULL이 나온다.

3.8 Nested Subqueries

-중첩하의 질의 쉽게 말해 if 문안에 if문 같은거

• Set Membership

* in == 교집합  not in == 교집합

• Set Comparison

*Some의 의미란

<some에서는 그 중 최댓값을 뜻함

>some에서는 그 중 최솟값을 뜻함

쉽게 말해서 1개만 만족해도 됨

*All의 의미란

모든게 다 되야됨

• Test for Empty Relations

• Exists

둘 다 존재하는지

• Not Exists

• Unique

결과가 없거나 하나인 경우에만 True

• Subqueries in the From Clause 

from 안에는 보통 Table이 나오는데 이중 query를 쓰면 from 안쪽에 table을 select로 다시 지정하고 그 table 안에서 select를 하는 형식이 나오게 된다.

• With Clause

• Scalar Subquery

3.1 Overview of the SQL Query Language

SQL language의 종류

• Data-Definition Language :Defining, deleting, modifying relation schemas 데이터 정의언어

• Data-Manipulation Language : ability to query information from the database 테이터정의언어

• Integrity

• View definition

• Transaction control

• Embedded SQL

• Authorization

• Basic Types in SQL DDL

• Basic Schema Dfinition - Create Table

• Integrity Constraint in Create Table

• Drop and Alter Table Constructs

3.3 Basic Structure of SQL Queries

SQL DML은 Query 정보를 넣고 지우고 업데이트할 수 있게 해준다.

** SQL에서는 대문자 소문자 구별이 없다!! ex) NAME = name = NaMe

• The Select Clause

SELECT cluased에는 + - / * 를 다 쓸수 있다. (*은 전체라는 뜻이다) 

• The From Clause

• The Where Clause

• Joins

• Natural Join 

3.4 Additional Basic Operations -Rename Operation

SQL allows renaming relations and attributes using the as clause       ex) old-name as new-name

*instructor as T == instructor T

String Operations

SQL includes a string-matching operator for comparisons on character strings. "like"랑 같이 쓰인다ㅡ

-Percent (%) : The % character matches any substring.

-Underscore (_) : The _ character matches any character.

고급 표현

-intro% : intro로 시작하는 모든 String

-%Comp% : Comp가 들어가는 모든 String

-___ : 정확히 3글자인 String

-___% : 최소 3글자인 String

차순

Default : 오름차순

-오름 차순 : asc

-내림 차순 : desc

ex)Order by **** asc

Between

*not Between도 있음

Union

Intersect

Except

문제!!! 풀어보기

일단 SQL의 종류가 많지만 지금은 Oracle SQL* Plus를 쓸것이다.

먼저 Oracle 홈페이지에 들어가서 다운을 받은 다음 내용이다.

이런 이름을 가진 것을 실행시키면

Command Line이 뜰겁니다.

그리고 처음에는 Connect를 쓰고

User-name에는 system이라고 쓰고 password에는 아까 정한 password를 씁니다. (Password는 입력되도 표시는 안됩니다.)

연결이 된다면 Connected라고 뜹니다.

2.1 Structure of relational Database

table == Relation

Attribute : Column of talbe

Tuple : row in table

*Attribute types

-Domain : the set of allowed vlaues for each attribute

-Attribute values are required to be atomic, that is indivisible

-Null 값이 들어갈수도 있다

*NULL 값이란?

-값이 무엇인지 정의할 수 없는 경우 사용될 수 있다. : 알려지지 않은 값

-값이 무엇인지 알 수 없는 경우

-적용 불가능한 값

-보류된 값

2.2 Database Schema

데이터베이스는 여러 Relation으로 이루어져있다

• Database Schema : Logical design of the database

• Database instance : A snapshot of the data in the database at a given instant in time

• Relation schema : Logical design of a table (Attribute와 연관된 Domains)

• Relation instance : A snapshot of the data in a table at a given instant in time

1. Selection
2. Project
3. Union
4. Difference
5. intersection
6. Join
1. Cartesian product
2. Natural Join

ex) SELECT Product Name Where Unit Price > 4000

2.Projection

Extract data Vertically(as a column)

Choses some of the attributes of the relation

ex) PROJECT Product Name

3.Union

합집합이다 중복된 것은 제거한다

4.Difference

차집합니다. 

5.Intersection

교집합이다.

6.Cartesian Product

행렬 곱하기 이다 3줄 x 3줄 = 9줄 이렇게

7.Natural Join

Relation R과 S에 공통적으로 존재하는 속성들을 이용하여 공통 속성들의 값들이 서로 같은 Tuple들을 조인하는 것이다. 쉽게 말해 같은 부분을 기준으로 두 Relation을 하나로 합침

전체 요약

1.1 DataBase Management System(DBMS)

1. Data redundancy and inconsistency
2. Difficulty in accessing data
3. Data isolation - multiple files and formats
4. integrity problems
5. Atomicity of updates
6. Concurrent access by multiple users
7. Security problems

• Physical level : describes how a record is stored.
• Logical level : describes data stored in database and the relationships among the data
• View level : application programs hide details of data types. can also hide information for security

• Schema : the logical structure of the database

  Analogous to type information of a variable in a program

-Physical Schema : database desigan at the physical level

-Logical Schema : database design at the logical level

• Instance : the actual content of the database at a particular point in time 

  Analogous to the value of a variable

• Physical Data Independence : Ability to modify the physical shema without changing the logical schema

- 하지만 대부분 심각하게 영향을 주지는 않는다.

• Data Models  

1. Relation model
2. Entity-relationship data model
3. Object-based data models
4. Semistructured data model (XML) ETC..

• Data Definition Language(DDL) : Specify the database schema

• Data Mnipulation Language(DML) : Express database queries and updates

-Data Dictionary contains metadata

Database schema

Integrity constraints

§Primary key (ID uniquely identifies instructors)

§Referential integrity(references constrint in SQL )

DML

-Accessing and manipulating the data organized by the appropriate data model

-DML은 Query Language이다

-Two classes of languages

§Procedural - user specifies what data is reuired and how to get those data

§Declarative(nonprocedural) - user specifies what data is required without specifying how to get those                               data

1.5 Relation Model

2장에서 다시 언급하겠다

*SQL : widely used non-procedural language

보통 프로그램은 데이터베이스에 접근하기 위해 다음 것들 중하나를 이용한다

-Language extensions to allow embedded SQL

-Application program interface which allow SQL queries to be sent to a database

1.6 Database Design

Logical Design : Deciding on the database schema. Database design requires that we find a "good" collection                 of relation schemas

Physical Design : Deciding on the physical layout of the database

*The Entity-relationship Model

- Models an enterprise as a collection of entities and relationships

entity : a thing or object in the enterpries that is distinguishable from other objects

relationship : an association among several entities

*Object-relational Data Model

-Extend the relational data model by including object orientation and constructs to deal with added data   types

1.7 Storage Management

-a program module that provies the interface between the low-level data stored in the database and the   application programs and queries submitted to the system

1.8 Query Processing

1. Parsing and translation
2. Optimization
3. Evaluation이 이상은 이해가 안됬습니다.

1.9 Transaction Management

Transaction : a collection of operations that perfoms a single logical function in database application

1.10 Database Architecture

전체구상도

세부구상도

3.1 Using Arrays

모든 배열은 일단 null로 되어있다 

삽입기능 - 숫자를 추가하는데 모음이 꽉찼으면 작은수보다 더 크고 큰수보다 더 작은 곳에 넣어야한다 null이면 넣는다

Code

public void add(GameEntry e)

{

int newScore = e.getScore();

// is the new entry e really a high score

if(newEntries == maxEntries)

{

if(newScore <= entries[numEntries-1].getScore())

return;

}

else

numEntries++;

int i = numEntries-1;

for(; (i>=1) && (newScore > entries[i-1].getScore()); i--)

entries[i] = entries[i-1]

entries[i] = e;    

}

제거기능 - 지우고 나서 지운것 다음 정렬도 해야됨

Code 

public GameEntry remove(int i ) throws IndexOutOfBoundsException

{

if ((i<0) || (i >= numEntries))

throw new IndexOutOfBoundsException("Invalid index :" + i);

GameEntry temp = entries[i];

for(int j = i; j <numEntries - 1; j++)

entries[j] = entries[j+1];

entries[numEntries - 1] = null;

numEntries--;

return temp;

}

정렬기능

3.2 Singly Linked Lists

2.2 Basic Operations

-AND   :     .     직렬 : 두개다 1이여야함

-OR    :     +    병렬 : 둘중 하나만 1이여도 됨

-NOT   :     '

2.3 Boolean Expressions and Truth Tables

간소화, 도면, truth table을 모두 그릴줄 알아야한다

가능한 가짓수는 2(n)개이다

2.4 Basic Theorems

X + 0 = X

X Ο 1 = X

X + 1 = 1

X Ο 0 = 0

idempotent laws

X + X = X

X Ο X = X

involution law

(X')' = X

Laws of complementarity

X + X' = X

X Ο X' = 0

증명할때 X 가 0일때랑 1일때로 나누어서 증명

2.5 Commutative Associative, and distributive laws

XY = YX 

X + Y = Y + X

교환법칙 결합법칙이 성립한다

증명은 truth table을 이용

XYZ = 1  === X = 1, Y = 1, Z = 1

X + Y + Z = 0 === X = 0, Y = 0, Z = 0

A + BC = (A + B)(A + C) 진짜 중요

2.6  Simplification Theorems

XY + XY' = X

(X + Y)(X + Y') = X

X + XY = X

X(X + Y) = X

(X + Y')Y = XY

XY' + Y = Y + X

EX) Z = A'BC + A'

X = A'

Y = BC

X +XY = X = A'

EX2) Z = [A + B'C + D +EF][A + B'C + (D + EF)']

2.7 MULTIPLYING OUT AND FACTORING

*SOP

이게 뭐냐하면 식안의 모든 결합이 SUM(+)으로 되있어야된다 예를 들어 AB' + CDE + EF같이 모두 +로 연결

(A + B)C + DE'도 sop이다 전개해야 SOP이다

*POS

얘는 모든 결합이 모두 곱하기로 되있으면 된다 (A+ B')(C + D+ E)같이 되면 된다

(A + B+ C)EF'도 POS이다

2.8  DeMorgan's Laws

(X + Y )' = X'Y'

(XY)' = X' + Y'

CF) (X1 + X2 + X3 ---) = X1'X2'X3' ----

(X1X2X3X4X5---) = X1' + X2' ----

1.2  Number Systems and Conversion

보통은 10진수를 쓰지만 컴퓨터는 2진수, 8진수, 16진수 등이 있다.

ex) 953.78(10)

1011.11(2) = 1 x  2(3) + ... 소수점 뒤에는 1 x 2(-1) + 1 * 2(-2) = 11.75(10)

8진수는 숫자가 0에서부터 7까지 밖에 없다 R진수는 0<= a <= R-1 까지 숫자가 있다

8진수는 base 8라고 영어로한다

16진수에서는 10이 A 11이 B 12가 C >>> F가 15이다

ex) 0.625(10)을 2진수로 바꾸려면 

F = 0.625 * 2 = 1.250 (a(-1) = 1) 

F1 = 0.250 * 2 = 0.5 (a(-2) = 0)

F2 = 0.5 * 2 = 1 (a(-3) = 1)

== 0.625(10) = 0.101(2)

0.7을 2진수로 바꾸려면 하다보면 알겠지만 0.1  0110 0110 0110  (0110이 반복됨)

2진수에서 16진수로 바꿀때는 4자리수마다 모아서 10진수 수로바꿔서 나열해주면 된다

1.3 Binary Arithmetic

2진수 덧셈 뺄셈 곱셈 나눗셈이 있다

덧셈 : 1 + 1 = 0 에다가 위의 값에 1을 더해준다 Carry라고 한다

뺄셈 : 0에서 1을 빼려면 위에있는 carry값을 내려서 계산해준다 위에있는 carry값을 내리면 위에꺼는 숫자 1이 줄고 밑에 숫자에는 2가 추가된다(헷갈림 주의)

곱셈 : 생각보다 단순하다 그냥 밑의 숫자의 1개씩 곱해주면된다 1자리씩 올리면서 간단하다

나눗셈 : 이것도 10진수랑 생각보다 비슷하다 나누는 수가 더크면 계속 자릿수 내리고 빼기를 잘하고 마지막 나머지가 나오는 것을 잊지말자

1.4 Representation of Negative Numbers

이건 표를 잘 봐야한다 2진수에서 첫번째 숫자는 부호를 뜻한다 0은 + 1은 -이다

음수를 표시하는 방법은 3가지 방법이있다.

1. 원래 양수였던 수의 2진수에다가 첫자리를 0에서 1로 바꾼다

2. 2's Complement  : N* = 2(n)- N 무슨 뜻이냐하면 1번을 위아래로 뒤집으면 나오는 숫자이다 0은 표시할수가 없다!

쉽게 아는 방법 2의 엔승에서 N을 빼는 거니 1을 N개 쓴 숫자에서 N을 2진수 빼기로 하면 바로 나온다

-덧셈법 그냥 더하면된다 but  범위가 2의 n-1승 보다 큰수가 나오면 overflow로 틀린 답이나온다  

l sum l <=2의 n-1승  그리고 범위안에 있는데 숫자의 자리수가 더 나오면 제일 앞에 있는 숫자를 무시하면 정답이 나온다

                       _

3. 1's Complement : N = ( 2(n) -1 ) - N 이것도 1번을 뒤집으면 나오는 건데 0부터 시작해서 마지막 숫자를 표시할수 없다 

-덧셈법 범위는 똑같다 이경우에는 자리수가 1개 더나오면 제일 첫 자리수에 그 숫자 1을 더하면 된다 그렇게 다시 덧셈을 계산하면 답이 나온다

2's에서 1을 빼면 1's 가 나온다 이걸 왜 쓰냐? arithmetic units are seasy to design using these systems

1.5 Binary Code

 10진수를 한숫자씩 그냥 2진수화시켜서 같다붙치는 것이다 보통은 BCD코드를 쓴다 

-BCD코드 (8-4-2-1) 그냥 말대로 숫자 4개가있으면 첫번째 수가 8이고 ... 이다

- 6 - 3 - 1 - 1 위랑 같은데 숫자만 좀 다르다

-Excess3 Code : BCD코드에서 3 더한 것이다 ㅋㅋㅋ

-2 out of 5 code는 에러 체크에 유용하다 because if any one of the bits in a code combination is changed due to a malfunction of the logic circitry, the number of 1 bits is no longer exactly two

-Gray Code : 연속된 숫자는 숫자차이가 1개만 난다 에러검사할때 유용하다 연속적인 10진수의 차이를 쉽게 알수 있다 translate an analog quantity 에 많이 사용한다