M1 Flashcards
is a sequence of unambiguous instructions for solving a problem, i.e., for obtaining a required output for any legitimate input in a finite amount of time.
algorithm
is any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output. This is thus a sequence of computational steps that transform the input into the output.
algorithm
AN ALGORITHM…
Can be represented in various forms
Recipe, process, method, technique, procedure, routine,… with
the following requirements:
ü Finiteness ü Definiteness ü Clearly specified input ü Clearly specified/expected output ü Effectiveness
Before you start to work on the the solution the developer, programmer must be able to understand fully the problem statement
Problem definition
Problem statements often have three elements:
• the X, stated clearly and with enough contextual detail to establish X;
• the X, often stated as a X or a working thesis;
• the X, statement of X of the document the writer is preparing.
problem itself
why it is important
method of solving the problem
claim
purpose
objective and scope
involves the definition of model objectives, conceptualization of the problem, translation into a computational model, and model testing, revision, and application.
Model development
Model development is an X process, in which many models are derived, tested and built upon until a model fitting the X is built
iterative
desired criteria
X may need to begin the search at the X as the original model building began, rather than where it finished. This may be for a number of reasons, a common one being that the model currently in service is X suited for reuse because it is poorly understood
Subsequent modeling work
same place
poorly
All algorithms must satisfy the following criteria:
• X. An algorithm has X, taken from a specified set of objects.
• X. An algorithm has X, which have a specified relation
to the inputs.
• X. Each step must be X; Each instruction is clear and unambiguous.
• X. The algorithm must always X after a finite number of steps.
• X. All operations to be performed must be X that they can be done exactly and in finite length.
Input,,, zero or more inputs
Output,,, one or more outputs
Definiteness,,, precisely defined
Finiteness,,, terminate
Effectiveness,,, sufficiently basic
In theoretical computer science, the X of an algorithm is asserted when it is said that the algorithm is correct with respect to a X. X refers to the input-output behavior of the algorithm.
correctness
specification
Functional correctness
A distinction is made between X correctness, which requires that if an answer is X it will be correct, and X correctness, which additionally requires that the algorithm X
partial
returned
total
terminates
Since there is no general solution to the X problem, a total correctness assertion may lie much deeper. A X is a type of mathematical proof that plays a critical role in formal verification because total correctness of an algorithm depends on X
halting
termination proof
termination
X is the determination of the amount of time and space resources required to execute it.
Usually, the X of an algorithm is stated as a function relating the input length to the number of steps, known as X, or volume of memory, known as X
Analysis of algorithms
efficiency or running time
time complexity
space complexity
- X is the process of executing a program with the intent of finding errors.
- A good test is one that has a high probability of X.
- X cannot show the absence of errors. It can only show if X.
- It is possible to write the tests X the program
Program testing
finding an error
Program testing,,, errors are present
before
For a programmer X is always a must. The presence of documentation helps X of all aspects of an application and it X on the quality of a software product. Its main focuses are development, maintenance, and knowledge transfer to other developers
reliable documentation
keep track
improves
