In: Computer Science
Describe the three types of problems that can be solved on computers and provide one example for each problem.
Types Of Problem That can be solved on computer is :-
Decision Problems
A choice issue is an issue for which the response for each substantial info is yes or no. Choosing whether a number is prime, odd or even are the two instances of choice issues.
Example :-
A choice issue is a computational issue where the response for each case is either yes or no. A case of a choice issue is primality trying:
"Given a positive integer n, determine if n is prime."
A choice issue is regularly spoken to as the arrangement of all examples for which the appropriate response is yes. For instance, primality testing can be spoken to as the unbounded set
L = {2, 3, 5, 7, 11, ...}
Search Problems
A pursuit issue is an issue which requires the recognizable proof of an answer from inside a conceivably unbounded arrangement of potential arrangements. The appropriate response is a string or the like - or a string portrayal of other information types. For instance, finding the variables of a number or finding the nth prime number.
Example :-
In an inquiry issue, the appropriate responses can be self-assertive strings. For instance, considering is a pursuit issue where the occasions are (string portrayals of) positive whole numbers and the arrangements are (string portrayals of) accumulations of primes.
A hunt issue is spoken to as a connection comprising of all the occasion arrangement sets, called a pursuit connection. For instance, calculating can be spoken to as the connection
R = {(4, 2), (6, 2), (6, 3), (8, 2), (9, 3), (10, 2), (10, 5)...}
which consist of all pairs of numbers (n, p), where p is a nontrivial prime factor of n.
Counting Problems
A counting problem requires a total of the solutions to a search problem. For example, 'how many of the first 100 integers are prime?'.
Example :-
A counting problem asks for the number of solutions to a given search problem. For example, a counting problem associated with factoring is
"Given a positive integer n, count the number of nontrivial prime factors of n."
A counting problem can be represented by a function f from {0, 1}* to the nonnegative integers. For a search relation R, the counting problem associated to R is the function
fR(x) = |{y: R(x, y) }|.