Software Enginnering
Table of Contents
1. Compiler
1.1. Components
1.1.1. Lexer
- Source -> Tokens
1.1.2. Parser
- Tokens -> AST(Abstract Syntax Tree)
- This step takes care of the syntactic aspect of the language
1.1.3. Semantic analysis
- AST -> Correct AST
- Semantic corrections
1.1.4. Lowering
- AST -> IR -> ASM -> Binary
- This part is called the back-end in contrast to the front-end.
- An example of this is .
2. Concurrency
2.1. Kernel Mode
Initially, all processors runs the same code and at some point it diverges based on the ID of the core.
3. Design Patterns
The gang of four design pattern(Erich Gamma and Richard Helm and Ralph Johnson and John Vlissides, 1994) are the foundational.
3.1. Creational
How objects are created
3.1.1. Singleton
Globally unique object
3.1.2. Prototype
Clone the prototype object with modification
3.1.3. Builder
Build object step by step using methods.
3.1.4. Factory
Use function to create a new object.
3.2. Structural
How objects relate to each other
3.2.1. Facade
An object that provides simplified API to underlying complex systems.
It often contains the subsystem object as its property.
3.2.2. Proxy
Proxy object that overrides or intercepts the activity.
3.3. Behavioral
How objects communicate with each other
3.3.1. Iterator
- Pull-based system
An object or pattern that traverse through a collection of object.
3.3.2. Observer
- Push-based system
Observer are notified when the data that they are subscribed to changes.
3.3.3. Mediator
An object that coordinate other objects.
3.3.4. State
Object that provides different functionalities based on its internal state, often defined as finite state machines.
Each states can be separate objects that implements the same methods.
3.3.5. Manipulator
std::cout << std::setw(5) << std::setprecision(2) << std::endl;
std::setw(5) returns an manipulator struct of type _Smanip which then implements
friend operator<< that takes std::cout and modify it and return std::cout back.
4. Coding Theory
- Study the fitness of code, which is a system of rules to convert information into another form.
- Data Compression, Cryptography, Error Detection and Correction,Data Transmission, Data Storage.
4.1. Kraft-McMillan Inequality
- Related to the equivalent condition for the existence of a uniquely decodable code.
5. Complexity Theory
- Computational Complexity Theory
5.1. Big-O notation
- See
5.1.1. Calculation
- Just calculate the length of execution concretely. Consider the worst case scenario.
5.2. Complexity classes
5.2.1. Time
5.2.1.1. P
- Polynomial time
- \[ t=O(\operatorname{poly}(n)). \]
5.2.1.2. NP
- Non-deterministic Polynomial time
- \[ t_{c}=O(\operatorname{poly}(n)). \]
- It takes polynomial time to check the answer.
5.2.1.3. NP-complete
- It contains all the hard parts of NP.
5.2.1.4. Co-NP
- It is easier to rule out the wrong answers.
5.2.1.5. Co-NP-complete
- P vs NP is one of this.
5.2.1.6. NP-hard
- Contains NP-complete and everything harder.
5.2.1.7. EXP
- It takes exponential time to even check the answer.
5.2.2. Space
5.2.2.1. PSPACE
- It takes polynomial space to solve given infinite amount of time
5.3. P vs NP
- P stands for Polynomial time, and NP is for Non-deterministic Polynomial time.
5.3.1. SAT
- https://youtu.be/6OPsH8PK7xM?si=0zhu3xBnFJWM6LBe
- The satisfiability problem (SAT) is one of the NP problem.
- One can always reduce an algorithm into a set of propositions for the SAT problem
- A problem can be reduced into a set of propositions that must be satisfied for the solution. The SAT algorithm can also find the conditions for a given solution.
- If a polynomial time solution for the SAT problem is found, then P=NP.
5.4. P = BPP
6. Type Theory
6.1. Covariant and Contravariant Type
A type is covariant if \(AAnimal, then List<Cat> is subtype of
List<Animal>.