Flashcards
4) What exactly is a problem?
Cards in this deck (13)
- 1Give 3 different notions relating to general problem solving that are key concerns in Computer Science-the constructive nature of their solutions
-the repeated application of these solutions
-the concern with/measurement of the difficulty of solving problems - 2What is abstraction in relation to real-world problem solving?The problems solved in computer science aren't the real problems, but are abstractions where:
-the abstractions need to be represented and manipulated within a computer program
-the abstractions mirror reality sufficiently closely so any conclusions reached are sufficiently valid for the real life problem - 3What is the travelling salesman problem?A salesman wishes to compute the shortest tour of a given collection of cities so as to save time/fuel/ any resource of interest
- 4What is the real world map colouring problem?You are given a plane map of regions, each contained within a continuous border. What is the minimum number of colours required to colour the map so if any two regions touch they must be coloured differently?
- 5What is the real world scheduling problem?Suppose there is a list of jobs that need to be allocated to time slots. They can be scheduled in any time slot but some cannot clash e.g. lessons in the same classroom. Is there a schedule for minimum time t?
- 6What is the real world register allocation problem?One of the techniques of compiler optimisation is register allocation, where program variables are allocated to k CPU registers. Not all program variables are ‘in use’ at the same time. If two program variables are in use at the same time then they have to be assigned to different registers. Can we decide whether every program variable can be assigned to one of our k registers so that if two program variables are in use at the same time then they are necessarily assigned to different registers?
- 7What is the real world frequency assignment problem?Consider a network of radio transmitters, each of which must be assigned one of f operating frequencies. If two nearby transmitters are operating on the same frequency then they have the potential to interfere with each other. The frequencies assigned to such pairs of transmitters are required to be distinct. Can we decide whether we can allocate a frequency, from a set of f frequencies, to every transmitter so that any pair of nearby transmitters must have different frequencies?
- 8Give a precise definition of a decision problemA decision problem consists of:
-a set of instances I
-a subset Y sigma I of yes instances - 9What is the four colour theorem?Every map can be four coloured but not every map can be three coloured
- 10Give a definition of what it means for an algorithm to be greedyGreedy algorithms work through a list 'greedily' choosing the best thing to do
- 11What is a crown graph on 2n vertices?Crown graph=complete bipartite graph from which a perfect matching has been removed.
N is the number of colours used, the smallest number of colours that can be used is 2 - 12What is a brute force algorithm?Brute force means going through all possible solutions extensively
- 13What is the essential rule to bear in mind when developing an abstraction of a real-world problem?An abstraction should only include essential information and hide inessential information relating to the problem in hand
Information
- Description
- Degree Engineering Flashcards on 4) What exactly is a problem?, created by jeevanaujla97 on 30/05/2016.
- Created by
- jeevanaujla97
- Views
- 1
- Rating