KEMBAR78
Problem PDF | PDF | Mathematical Optimization | Algorithms
Scribd
Upload
8 views2 pages

Problem PDF

The document defines problems and problem instances, explaining that a problem is a general task needing a solution, while a problem instance is a specific example with defined inputs and outputs. It also discusses generalization and specialization, illustrating how broader concepts can be derived from or broken down into specific types. Additionally, it categorizes computational problems into decision, search, counting, and optimization problems, each with distinct characteristics and examples.

Uploaded by

ritu
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
8 views2 pages

Problem PDF

The document defines problems and problem instances, explaining that a problem is a general task needing a solution, while a problem instance is a specific example with defined inputs and outputs. It also discusses generalization and specialization, illustrating how broader concepts can be derived from or broken down into specific types. Additionally, it categorizes computational problems into decision, search, counting, and optimization problems, each with distinct characteristics and examples.

Uploaded by

ritu
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

Problems And Problem Instances

Problem:
A problem is a general question or task that needs a solution, defined by its inputs, processing
operations, and outputs.

Problem Instance:
A problem instance is a concrete example of a problem with specific values for its inputs and a
particular desired output.

Example: The problem of "finding the area of a rectangle" has inputs (length and width) and an
output (area). A specific instance is "finding the area of a rectangle with a length of 5 units and a
width of 3 units," which yields an output of 15 square units.

Generalization and Specialization

Generalization:
Definition: A bottom-up process where common characteristics are extracted from several
lower-level entities or instances to create a single, higher-level entity or concept.

Example: Combining specific vehicle types (car, truck, motorcycle) into the general concept of a
"Vehicle," which shares common attributes like having wheels and an engine.

Specialization:
Definition: A top-down process where a broader, generalized entity is broken down into more
specific sub-types or instances, each with its unique features.

Example: The general concept of a "Vehicle" can be specialized into specific types like "Car,"
"Bus," or "Motorcycle," each with distinct characteristics such as seating capacity or engine size.

Computational Problems

A computational problem is a problem that can be solved step-by-step with a computer


(Program). These problems usually have a well-defined input, constraints, and conditions that
the output must satisfied.

Types of computational problems:

• Decision Problem: A decision problem is one where the answer is yes or no. For instance,
"given a number n, is n even?" is a decision problem.
• Search Problem: A search problem is one where the solution consists of one or more values
that satisfies a given condition. For instance, we may want to compute a path from one
geographical location to another on a map.

• Counting Problem: A counting problem is one where the answer is the number of solutions to
a search problem. For instance, how many paths from one geographical location to another on
a map. Another instance , how many red balls in a bag filled with balls of different colours.

• Optimization Problem: An optimization problem is one where the solution is the "best"
possible solution, where the "best" can be defined in a different way. For instance, we may
want to compute the fastest route from one location to another.

You might also like