Introduction of Computer Science Ch16. Security Ch17. Theory of Computation Ch18. Artificial Intelligence

# Introduction of Computer Science Ch16. Security Ch17. Theory of Computation Ch18. Artificial Intelligence NTNU 計算機概論 ##### [Back to Note Overview](https://reurl.cc/XXeYaE) ##### [Back to Introduction of Computer Science](https://hackmd.io/@NTNUCSIE112/SyU5Uuyhr) ###### tags: `NTNU` `CSIE` `必修` `Introduction of Computer Sciencce` {%hackmd @sophie8909/pink_theme %} {%hackmd @NTNUCSIE112/csabb %} {%hackmd @NTNUCSIE112/csch %} # Ch16 Security ## 16-1 Introduction ### Security goals - Confidentiality - Prevent **unauthorized people** from accessing information - Integrity - Denotes protection against unintentional or deliberate **destruction** or **alteration** of systems, programs and data - Availability - Means that information must be accessible to legitimate users ### Attack types to security goals - Security attacks - Threat to **Confidentiality** - Snooping - Traffic analysis - Threat to **Integrity** - Modification - Masquerading - Replaying - Repudiation - Threat to **Availability** - Denial of service ### Security Services - Standards have been developed to achieve information security and avoid security attacks - Five common security services - Data Confidentiality - Data Integrity - Authentication - Nonrepudiation - Access Control - Achieving information security goals requires cryptography - Symmetric-key cryptography - Asymmetric-key cryptography ## 16-2.1 Symmetric-Key Cryptography ### DES(Data Encryption Standard) - 1970s IBM develop - The plaintext are broken into segments of 64 bits. - Each section is encrypted using a 56-bit key. - Stages 1, 18, and 19 are permutation operations. - Stages 2 to 17 are identical stages. - The right 32 bits of a stage become the left 32 bits of the next stages. - The left 32 bits of a stage are scrambled with the key and become the right 32 bits of the next stage. - The scrambling is complex. ## 16-2.1 Asymmetric-Key Cryptography ### RSA - Proposed by Rivest, Shamir and Adleman in 1977 - Widely and most famous - The number of the keys is only twice of the number of users. - $p$, $q$, $n=p*q$ - The public kry is a pair of number(N,e) - The private key is a pair of numbers(N,d) - Encryption : $C$ = $F^e$ $mod$ $N$ - Decryption : $F$ = $C^d$ $mod$ $N$ - $N$ = $p*q$ ## 16-3 Other Security Services - Handwritten signature - Digital signature - When an author signs a document, it cannot be changed. - When you send a document electronically, you can also sign it. - Digital signature can be done in two ways - Method 1：Sign the whole document - It can provide integrity, authentication, and non-repudiation. - This method does not provide sevrevy. - This method is very inefficient. 1. Accreditation by impartial authorities to generate public and private keys 2. Encrypted by private key 3. send Message ans Digital signature 4. using public key decode - Method 2：sign a digest of the document - Sign method: - Message → Hash (get digest) - Digest : F - Private key : d - Digital signature : $S$ = $F^d$ $mod$ $N$ - The two most common hash functions - Message Digest 5 (MD5) - by Ron Rivest at MIT - Secure Hash Algorithm (SHA-1) - by the National Institute of Standard and Technology (NIST) - The properties of hash function - One-way - the digest can only be created from the message, but not vice versa - One-to-one - be very difficult to find two message that create the same digest - How can users prove their identity and public key? - Method 1 - Use a bulletin board that holds the user's public public key - Method 2 - Use the Internet to inform the other party - Method 3 - Use the Certificate Authority (CA) # Ch17 Theory of Computation ## Introduction - Intrinsic Questions - Which problems can be solved ? - How long it take to solve a problem ? - What language is better ? - What is shortest code ? - Halt or run forever ## 17-3 Turing Machine ### Alan Mathison Turing - 《Can Machine Think?》 - [Turing Test](##Turing-Test) - Crack the Enigma - WAR II won - [Turing Machine](###Turing-Machine) ### Turing Machine ![](https://i.imgur.com/wfiLJpS.png) - Introduced in 1936 by Alan M. Turing - **Components** - Tape - holds a sequence of characters form the set of characters acceptable by the machine - Read / Write head - Controller - The Turing machine's memory is infinite - **Informal Description** - Input written on left-most squares of tape - Rest of squares are blank - At each point, take a step determined b - current symbol of being read - current state of finite control - A step consists of - writing new symbol - moving read/write head left or right - changing state - Video {%youtube vo8izCKHiF0 %} ### Hilbert 10'th Problem - Is there a Algorithm to tell if a polynomial has an integer root ? - 1900 Hilbert ask " Can mathematics be mechanized ?" - 1936 Church - x-calculus ( logic ) - 1936 Turing - Turing Machine ( Machinery ) - [Church-Turing Thesis](###Church-Turing-Thesis) - Kleene - Recursive Function ( Function ) - 1970 Yuti Matijaseric - according to Church-Turing Thesis' algorithm definition - prove Hilbert 10'th Problem is unsolvable, undecidable - that is to say, cannot find a algorithm can tell if a polynomial has an integer root - but it still can using exhaustion to check - Hilbert 10'th Problem is - Turing-Recognizable, semi-decidable - Turing-Acceptable, recursively-enumerable ### Church-Turing Thesis - Any algorithm(computation) can using T.M. - But this thesis cannot be proved - Turing Machine's power is same with any other computer - Currently known computers, computability not more than Turing Machine ## 17-5 Halting Problem ### Halting problem is unsolvable (undecidable) - Proof by contradiction - Step 1: Assume that a program, called **Test**, exists. ```c= bool test() { if( P terminate ) return 1; if( P does not terminate ) retrun =0; } ``` - Step 2: Create another program called **Strange** that is made of two parts: - a copy of test at the beginning - an empty loop at the end ```c= void Strange () { bool x =test(); while( x ) { } } ``` - Step 3: Now having made the program Strange, we test this program with itself as input, we have the following contradictions: - **Strange** doesn't terminate if **Strange** terminates. - **Strange** terminates if **Strange** doesn't terminate. - Real programming halting problems - Odd perfect number search - Goldbach's Conjecture - The 3n+1 problem(Collatz conjecture) # Ch18 Artificial Intelligence ## 18-1 Introduction ### What is artificial intelligence? - 2000 B.C. Aristotle invented **the concept of logical reasoning** - Leibniz and Newton complete **logical language** - In 19th George Boole developing **Bollinger Algebra** - Laid the **foundation of the logic circuit** - **Think Machine** - Proposed by Alan Turing in [**Turing Test**](##Turing-Test) - The word **Artificial Intelligence** created by John McCarthy in 1956 ### Definition of Artificial Intelligence | | Fidelity | Rationality | | ------------------- | --------------------------------- | -------------------------------- | | Thought / Reasoning | System that **think like humans** | System that **think rationally** | | Behavior | System that **act like humans** | System that **act rationally** | ### Turing Test - 1950 by Alan Turing - Benchmarking progress in artificial intelligence - The test is for a program to have a conversation (via online typed messages) with an interrogator - The interrogator has to guess if the conversation is with a machine or a person - If the interrogator cannot definitely tell which set of responses has come from the computer ans which from the human, the computer has passed the Turing test for intelligent behavior. ## 18-2 Knowledge Representation From common methods for representing knowledge - Semantic networks - use directed graphs to represent knowledge - Frames - closely related to semantic networks - data structures (records) are used to represent the same knowledge - advantage：programs can handle frame more easily than semantic networks - Predicate logic (First-Order Logic) - assumes the world contains objects and relations - can express facts about some or all the objects in the universe - Syntax - BNF(backus-Naur form) grammar - Atomic Sentences - Complex Sentences - Negation ： ~ - Conjunction ： ∧ - Disjunction ： ∨ - Implication ： ⇒ - Universal Quantification ： ∀ - Existential Quantification ： ∃ - Rule-based systems - Represents knowledge using a set of rules that can be used to deduce new facts from know facts. - The rules express what is true if specific conditions are met. - A rule-based database is a set of __*if ... then ...*__ statements in the form - IF A then B - A → B - in which A is called the antecedent and B is called the consequent - each rule is handled independently without any connection to other rules - made up of three components - an interpreter (or inference engine) - a knowledge base - a fact database ## 18-3 Expert System use the knowledge representation languages discussed in the previous section to perform tasks that normally need human expertise ### The architecture of an expert system ## 18-4 Searching Searching can be described as solving a problem using a set of states(situation). A search procedure starts from an initial state, goes through intermediate states until finally reaching a target state. There are two general search methods: brute-force ans heuristic - Brute-force search - Breadth-First Search(BFS) - Depth-First Search(DFS) - Heuristic search ## 18-6 Neural networks ### Learning Algorithm - while not done: - Pick a random training example "(input,label)" - Run neural network on "input" - Adjust weights on edges to make output closer to "label" - Simple classification problem - Neural Network Training - [Neural Network Playground](https://reurl.cc/RdVeOD)