Computational Methods (OCR A-Level Computer Science): Revision Notes

Computational Methods

Overview

In computer science, computational methods refer to techniques and approaches used to solve problems using algorithms and computer systems. Not all problems are solvable computationally, and it's important to understand the features that make a problem suitable for computational methods. Key techniques include decomposition, abstraction, calculations, and data storage.

Features That Make a Problem Solvable by Computational Methods

Decomposition

• Definition: Breaking down a complex problem into smaller, more manageable sub-problems.
• Purpose: Simplifies the problem-solving process by focusing on individual components.
• Example:
  • Problem: Develop a traffic management system.
  • Decomposition:
  1. Detect vehicle presence.
  2. Control traffic lights.
  3. Analyse traffic patterns. Why It Works: Each sub-problem can be solved independently, making the overall problem easier to tackle.

Abstraction

• Definition: Ignoring irrelevant details to focus on the essential features of a problem.
• Purpose: Reduces complexity and highlights the core elements needed for a solution.
• Example:
  • Problem: Simulate a weather forecasting system.
  • Abstraction:
  • Focus on temperature, humidity, and wind speed.
  • Ignore details like individual raindrops or small variations in pressure. Why It Works: By simplifying the problem, abstraction helps in creating models that are easier to implement computationally.

Calculations

• Definition: Performing mathematical or logical operations to arrive at a solution.
• Purpose: Enables precise and repeatable problem-solving.
• Example:
  • Problem: Calculate the shortest route between two cities.
  • Solution: Use Dijkstra's algorithm to perform the necessary calculations. Why It Works: Problems that rely on mathematical operations can be efficiently solved using algorithms.

Storage of Data

• Definition: Storing and organising data in a way that it can be efficiently retrieved and processed.
• Purpose: Many computational problems involve managing large amounts of data, such as in databases or files.
• Example:
  • Problem: Create a student management system.
  • Solution:
  • Use a database to store student records.
  • Query the database for specific information, such as grades or attendance. Why It Works: Proper data storage allows for efficient access and manipulation, making it easier to solve data-centric problems.

Determining if a Problem is Solvable by Computational Methods

To determine if a problem can be solved computationally, consider the following questions:

1. Can the Problem Be Broken Down?

• If a problem can be divided into smaller tasks (decomposition), it is likely solvable computationally.

2. Can Irrelevant Details Be Ignored?

• If the problem can be simplified by focusing on essential details (abstraction), it is suitable for computational methods.

3. Can the Problem Be Represented Mathematically?

• Problems involving calculations, algorithms, or logical operations are ideal for computational solutions.

4. Does the Problem Involve Data?

• If data needs to be stored, retrieved, or processed, computational methods can provide efficient solutions.

Limitations of Computational Methods

1. Ambiguous Problems:

• Problems that lack clear rules or well-defined goals are difficult to solve computationally.
• Example: Writing a poem.

2. Non-Computable Problems:

• Some problems, like the Halting Problem, cannot be solved by any computational method.

3. Complexity and Resources:

• Problems with extremely high computational complexity may require more time or resources than are available.

Note Summary