1. Decidable and Undecidable
Undecidable
An undecidable problem means no algorithm can be constructed that will always provide a correct yes/no answer for all possible inputs.
- No algorithm can always provide a correct answer.
- Some problems may have a solution, but an algorithm can’t solve all instances.
Example: Halting problem
Decidable
A decidable problem means an algorithm can always be written to provide a correct yes/no output for any input.
- An algorithm exists to solve the problem.
2. Graphs and Heuristics
Graphs
A graph is a data structure used to represent the relationship between objects. A graph consists of nodes (the entities being connected) and edges (the connections or relationships between nodes).
Types of Graphs
- Undirected Graphs: Edges are bidirectional.
- Unweighted Graphs: All edges are considered equal.
- Directed Graphs: Edges have direction.
- Weighted Graphs: Edges have values, such as distance or cost.
Applications of Graphs
- Social Networks: Connecting users and their relationships.
- Navigation Systems: Finding the shortest route in Google Maps.
- Recommendation Systems: Netflix suggests movies based on connections between viewers and genres.
Heuristic
A heuristic is a problem-solving approach that simplifies the solution process using rules of thumb.
Real-World Examples
- Brute Force: Check every shelf for a science book.
- Heuristic: Look for the science section of the library to find the science book.