Conceptos basicos algoritmos
Páginas: 11 (2694 palabras)
Publicado: 10 de septiembre de 2012
De nitions Some Applications of Algorithms Speci c Algorithmic Problems Exercise
ALGORITHMS CLASS
Basic Concepts Juan Mendivelso, PhD(c)
Department of Computer and Industrial Engineering National University of Colombia
February 28, 2012
Juan Mendivelso PhD(c)
Algorithms
De nitions Some Applications of Algorithms Speci c Algorithmic Problems Exercise
Outline
1
De nitionsComputer Program Computational Problem Algorithm Data Structure E ciency NP-Complete Problems Analysis of Algorithms Some Applications of Algorithms Speci c Algorithmic Problems Exercise
Juan Mendivelso PhD(c) Algorithms
2 3 4
De nitions Some Applications of Algorithms Speci c Algorithmic Problems Exercise
Program Computational Problem Algorithm Data Structure E ciency NP-CompleteProblems Analysis of Algorithms
Outline
1
De nitions Computer Program Computational Problem Algorithm Data Structure E ciency NP-Complete Problems Analysis of Algorithms Some Applications of Algorithms Speci c Algorithmic Problems Exercise
Juan Mendivelso PhD(c) Algorithms
2 3 4
De nitions Some Applications of Algorithms Speci c Algorithmic Problems Exercise
Program ComputationalProblem Algorithm Data Structure E ciency NP-Complete Problems Analysis of Algorithms
Program
Sequence of instructions written to perform a speci ed task with a computer. A computer requires programs to function. Computer source code is written by computer programmers. Source code is written in a programming language. Source code may be converted into an executable le by a compiler.
JuanMendivelso PhD(c)
Algorithms
De nitions Some Applications of Algorithms Speci c Algorithmic Problems Exercise
Program Computational Problem Algorithm Data Structure E ciency NP-Complete Problems Analysis of Algorithms
Outline
1
De nitions Computer Program Computational Problem Algorithm Data Structure E ciency NP-Complete Problems Analysis of Algorithms Some Applications of AlgorithmsSpeci c Algorithmic Problems Exercise
Juan Mendivelso PhD(c) Algorithms
2 3 4
De nitions Some Applications of Algorithms Speci c Algorithmic Problems Exercise
Program Computational Problem Algorithm Data Structure E ciency NP-Complete Problems Analysis of Algorithms
Computational Problem
Relationship between a set of instances (input) and a set of solutions (output). Formallyestablishes the relationship between the input and the output of an algorithm. Example Sorting Problem Input: A sequence of n numbers a1 , a2 , . . . , a . Output:A permutation (reordering) a1 , a2 , . . . , a input such that a1 ≤ a2 ≤ . . . ≤ a .
n n
n
of the
Juan Mendivelso PhD(c)
Algorithms
De nitions Some Applications of Algorithms Speci c Algorithmic Problems Exercise
ProgramComputational Problem Algorithm Data Structure E ciency NP-Complete Problems Analysis of Algorithms
Outline
1
De nitions Computer Program Computational Problem Algorithm Data Structure E ciency NP-Complete Problems Analysis of Algorithms Some Applications of Algorithms Speci c Algorithmic Problems Exercise
Juan Mendivelso PhD(c) Algorithms
2 3 4
De nitions Some Applications ofAlgorithms Speci c Algorithmic Problems Exercise
Program Computational Problem Algorithm Data Structure E ciency NP-Complete Problems Analysis of Algorithms
Algorithm
Well-de ned computational procedure that takes some set of instances and produces some set of solutions. Sequence of computational steps that transform the input into the output. Tool for solving a well-speci ed computational problem.Example For the instance 31, 41, 59, 26, 41, 58 , a sorting algorithm must produce 26, 31, 41, 41, 58, 59 .
Juan Mendivelso PhD(c) Algorithms
De nitions Some Applications of Algorithms Speci c Algorithmic Problems Exercise
Program Computational Problem Algorithm Data Structure E ciency NP-Complete Problems Analysis of Algorithms
Correctness
Correct Algorithm An algorithm is correct...
ALGORITHMS CLASS
Basic Concepts Juan Mendivelso, PhD(c)
Department of Computer and Industrial Engineering National University of Colombia
February 28, 2012
Juan Mendivelso PhD(c)
Algorithms
De nitions Some Applications of Algorithms Speci c Algorithmic Problems Exercise
Outline
1
De nitionsComputer Program Computational Problem Algorithm Data Structure E ciency NP-Complete Problems Analysis of Algorithms Some Applications of Algorithms Speci c Algorithmic Problems Exercise
Juan Mendivelso PhD(c) Algorithms
2 3 4
De nitions Some Applications of Algorithms Speci c Algorithmic Problems Exercise
Program Computational Problem Algorithm Data Structure E ciency NP-CompleteProblems Analysis of Algorithms
Outline
1
De nitions Computer Program Computational Problem Algorithm Data Structure E ciency NP-Complete Problems Analysis of Algorithms Some Applications of Algorithms Speci c Algorithmic Problems Exercise
Juan Mendivelso PhD(c) Algorithms
2 3 4
De nitions Some Applications of Algorithms Speci c Algorithmic Problems Exercise
Program ComputationalProblem Algorithm Data Structure E ciency NP-Complete Problems Analysis of Algorithms
Program
Sequence of instructions written to perform a speci ed task with a computer. A computer requires programs to function. Computer source code is written by computer programmers. Source code is written in a programming language. Source code may be converted into an executable le by a compiler.
JuanMendivelso PhD(c)
Algorithms
De nitions Some Applications of Algorithms Speci c Algorithmic Problems Exercise
Program Computational Problem Algorithm Data Structure E ciency NP-Complete Problems Analysis of Algorithms
Outline
1
De nitions Computer Program Computational Problem Algorithm Data Structure E ciency NP-Complete Problems Analysis of Algorithms Some Applications of AlgorithmsSpeci c Algorithmic Problems Exercise
Juan Mendivelso PhD(c) Algorithms
2 3 4
De nitions Some Applications of Algorithms Speci c Algorithmic Problems Exercise
Program Computational Problem Algorithm Data Structure E ciency NP-Complete Problems Analysis of Algorithms
Computational Problem
Relationship between a set of instances (input) and a set of solutions (output). Formallyestablishes the relationship between the input and the output of an algorithm. Example Sorting Problem Input: A sequence of n numbers a1 , a2 , . . . , a . Output:A permutation (reordering) a1 , a2 , . . . , a input such that a1 ≤ a2 ≤ . . . ≤ a .
n n
n
of the
Juan Mendivelso PhD(c)
Algorithms
De nitions Some Applications of Algorithms Speci c Algorithmic Problems Exercise
ProgramComputational Problem Algorithm Data Structure E ciency NP-Complete Problems Analysis of Algorithms
Outline
1
De nitions Computer Program Computational Problem Algorithm Data Structure E ciency NP-Complete Problems Analysis of Algorithms Some Applications of Algorithms Speci c Algorithmic Problems Exercise
Juan Mendivelso PhD(c) Algorithms
2 3 4
De nitions Some Applications ofAlgorithms Speci c Algorithmic Problems Exercise
Program Computational Problem Algorithm Data Structure E ciency NP-Complete Problems Analysis of Algorithms
Algorithm
Well-de ned computational procedure that takes some set of instances and produces some set of solutions. Sequence of computational steps that transform the input into the output. Tool for solving a well-speci ed computational problem.Example For the instance 31, 41, 59, 26, 41, 58 , a sorting algorithm must produce 26, 31, 41, 41, 58, 59 .
Juan Mendivelso PhD(c) Algorithms
De nitions Some Applications of Algorithms Speci c Algorithmic Problems Exercise
Program Computational Problem Algorithm Data Structure E ciency NP-Complete Problems Analysis of Algorithms
Correctness
Correct Algorithm An algorithm is correct...
Leer documento completo
Regístrate para leer el documento completo.