00:00:00
[Música]
00:00:15
Hola pesoal sean benvidos a nosa primera
00:00:18
aula de análisis proyecto y análisis de
00:00:21
algoritmos n Esa primera aula vamos a
00:00:24
presentar algunos conceptos
00:00:25
introductorios para
00:00:28
disciplina
00:00:30
apres presentaremos algun conitos como
00:00:32
que algoritmo o que que un problema o
00:00:35
que una instancia y apr presentaremos
00:00:38
también comoera de correción de
00:00:40
algoritmo y como medir consumo de tiempo
00:00:44
de un
00:00:46
algoritmo así como acontece con engeros
00:00:49
civ el tcnicas y algas mtricas que usan
00:00:55
para prever comportamento estruturas
00:00:58
antes de construirlas asim comoes elesen
00:01:02
nos tambén como engeros da computación a
00:01:06
gente precisa prever como que será
00:01:10
comportamento de un algoritmo antes de
00:01:15
implementarlo esa disciplina nos ayudar
00:01:17
aer exatamente ISO ent primero vamos ver
00:01:20
alguns conceitos importantes para para
00:01:23
poder traballar yer anális su algoritmos
00:01:26
primero precisamos definir o que que un
00:01:29
algoritmo un algoritmo un procedimiento
00:01:32
computacional que está bien definido que
00:01:35
recebe algun valores como entrada y
00:01:38
producir dar como resposta alg valores
00:01:41
como
00:01:43
saída otra defini simples ferr para
00:01:47
resol problemas
00:01:51
computacion un algoritmo res un problema
00:01:54
y que un problema un problema definido
00:01:57
por una descrición parámetros
00:01:59
tanto de entrada como de saída una
00:02:02
descrición sobre propriedades que a
00:02:04
resposta de
00:02:06
satisfer y o que que una instancia una
00:02:09
instancia de un problema eh se obt a
00:02:13
fixar alguns valores a fixar verdad
00:02:15
valores para todos os parmetros problema
00:02:18
de aquí a pqu vamos ver un exemplo aquí
00:02:21
temos un exemplo vamos suos un problema
00:02:24
de ordenar una secia de elementos a1 a2
00:02:28
at a
00:02:30
Y esa secia que ser ordenada de manea
00:02:33
crescente precisamos definir con que ser
00:02:36
entrada son saídas como que ser a saída
00:02:40
y cu propriedades que esa saída de
00:02:43
cumprir a entrada esa secia a1 a2 a n cu
00:02:48
que a saída a saída tamb secia a L A l a
00:02:54
L que cumpre seguintes propriedades esa
00:02:58
secia permut secia original certo
00:03:02
permuta t que a un l se menor que a do
00:03:08
L y así sucesivamente y todasas se menor
00:03:13
que a n l aquí un exemplo decia acia de
00:03:18
entrada por exemplo sera secia aquí
00:03:24
10544 y a segda sería secuencia ordenada
00:03:28
de manea crescente 4 5 10 20 40 nesta
00:03:32
disciplina vamos ver varias formas Deer
00:03:36
ISO de ordenar una secuencia de
00:03:40
elementos aquí temos un otro exemplo eh
00:03:44
de problema o problema o seguinte
00:03:47
encontrar o camino
00:03:48
mínimo desde un punto inicial at un
00:03:52
punto
00:03:53
final certo ent cualqu entrada entrada
00:03:57
entrada ser por exemplo coordenadas
00:04:00
punto inicial y coordenadas de es punto
00:04:03
final y que serda saída ser cam que mea
00:04:09
desde pto inicial atto final y al
00:04:13
propedades esam de ser
00:04:17
mínimo disciplina también vamos ver alg
00:04:21
algoritmos que per res es problema
00:04:23
problema cam mínimo por exemplo usando
00:04:28
grafos
00:04:30
cuando a gente proyet un algoritmo
00:04:33
primero queos que ver es si algoritmo
00:04:35
está correto un algoritmo correo si
00:04:38
resolve
00:04:40
problema para toda instancia de entrada
00:04:43
o algoritmo termina característica
00:04:45
importante que algoritmo termine no fi
00:04:48
infinitamente un
00:04:49
Loop intermin y produz saída que satisf
00:04:54
propiedades que for definidas para
00:04:56
problema Ah primero paso es demostrar si
00:05:00
algoritmo está correcto si f o que
00:05:05
promete para Fer a proba de correción
00:05:09
algoritmo existen algumas técnicas
00:05:12
cuando estamos trabando con un algoritmo
00:05:15
interativo que usa lazos usada a técnica
00:05:19
de invariante do lazos o que que un
00:05:21
invariante dos lazos una propriedad que
00:05:24
debe ser verdadeira antes durante y após
00:05:27
execu do lazo
00:05:30
usando ISO a gentee mostrar provar que
00:05:34
algoritmo está correto no caso de
00:05:36
algoritmos interativos no caso de
00:05:38
algoritmos
00:05:41
recursivos usada a técnica de inducción
00:05:44
matemática
00:05:45
eho instas veremos de aquí a un
00:05:51
exemplo fechamos ese exemplo de
00:05:54
algoritmo un algoritmo simples que
00:05:57
Calcula un máximo de una secuencia a
00:05:59
gente decidió un algoritmo recursivo
00:06:02
poderíamos feo un algoritmo interativo
00:06:06
también que que ent recebe como
00:06:09
parámetro un vector
00:06:11
a deo n y encontrar cu que máximo Dee
00:06:17
vector si n igual a un o se sio de
00:06:21
vector un ent ya que un máximo prio
00:06:24
elemento que único que está n vector que
00:06:28
sería caso contrario a gente Lamar
00:06:32
recursivamente algoritmo para calcular
00:06:34
que máximo vector a con n men Un
00:06:38
elementos o se desde posición un
00:06:41
posición n men ent es ese método de
00:06:44
aquí calcular que máximo desde de a
00:06:49
desde 1 n yver un valor que valor x
00:06:55
certo aquí aquí ya valor má máximo de un
00:07:00
vector de un a tn men 1 cuando obtiver
00:07:05
ese valor único que ficara para resolver
00:07:07
es perguntar si ese máximo encontrado es
00:07:12
mayor a un elemento que está faltando
00:07:14
que sería o a posición n si mayor a
00:07:19
posición n ent qui un mayor es x caso
00:07:22
contrario un mayor e a
00:07:26
de Okay ya Pro estamos o noso algoritmo
00:07:31
o próximo paso verificar se algoritmo
00:07:34
está correto estamos vendo que un
00:07:36
algoritmo recursivo ent vamos usar a
00:07:40
técnica de inducción matemática noo que
00:07:43
sería n para demostrar que algoritmo
00:07:46
está correcto ent Cómo que usamos esa
00:07:49
técnica primero falamos si algoritmo
00:07:52
está correcto para un instancia pequena
00:07:54
n ese caso para nahu después asumimos
00:07:57
para una instancia de tamaño n men
00:08:00
verificamos si está correcta y despu
00:08:02
mostramos para n
00:08:04
si que debeer ent vamos ver pasos para
00:08:08
demar cor algoritmo
00:08:12
máximo si n ig 1 Vamos ver algoritmo dev
00:08:16
a respa correta si n ig 1 sí un elemento
00:08:21
devolve a dev resposta correta
00:08:26
s por hipótesis a supor que para n mayor
00:08:31
igual a do o
00:08:33
algoritmo a llamada
00:08:36
máximo con un parámetro a y n - 1 produ
00:08:39
un resultado esperado pues n - 1 es
00:08:42
menor a n Enton supondo que esa Lía de
00:08:46
aquí Me devolve resultado correcto me
00:08:49
devolve realmente cu que máximo de
00:08:53
vector a desde posición atn - 1 tambo
00:08:57
Mostrar agora que o algoritmo está
00:09:01
correcto cóm ent H aquí a gente ya sabe
00:09:05
que me devolve a respesta respuesta
00:09:08
correcta para un vector de un atn men 1
00:09:12
considerando ISO vamos ver si lneas cuat
00:09:16
a se calculan correctamente un máximo
00:09:20
vector a de 1 n supondo que un x Está
00:09:23
correcto que un máximo de un atn men 1
00:09:27
único que estaría faltando ver
00:09:30
a última posición vector mayor menor que
00:09:34
xo exatamente que estamos
00:09:38
l cer cono demra que algoritmo realment
00:09:43
está
00:09:47
coro desp de ver algoritmo Está correcto
00:09:50
próximo paso
00:09:52
calcular que
00:09:57
cons para
00:09:59
vamos estimar cuá tempo a máquina gastar
00:10:02
o cu de memoria será necesar para
00:10:04
resolver una instancia de
00:10:06
problema forma simples deero ser
00:10:09
simplesmente colocar colocar algoritmo
00:10:12
no inicio y colocar que peg horario de
00:10:17
inicio horario de yer a diferen no prio
00:10:21
programa vamos estimar tempo de manea
00:10:25
experimental vamos suos aquí do algoros
00:10:30
ese verm y ese otro aquí de ponchos son
00:10:33
do algoritmos que resolv un mismo
00:10:36
problema aquí est mostrando tempo que
00:10:39
demora para resolver varias
00:10:42
instancias aquí
00:10:47
instancias varias instancias yo es do
00:10:50
algoritmos est mostrando aquí
00:10:53
tempo que
00:10:57
cons vemos Que o
00:11:00
vermelin consue resolver todos problemas
00:11:04
todas instancias desp todas instancias
00:11:07
ese problema enant de punos ve no consue
00:11:12
resolver problema noo máximo determinado
00:11:15
aquí significa que no terminó did not
00:11:18
Finish DEA forma veces comparamos
00:11:22
algoritmos de manea
00:11:24
experimental a gentea de saber
00:11:27
cuor que real cons enmos de entrada es
00:11:31
de aquí de manea
00:11:33
experimental
00:11:36
simples
00:11:39
veamos novamente pas de para problema de
00:11:44
ordena queremos ordenar un vector a de
00:11:47
una n de manea crescente y no entrada
00:11:52
esencia de números 23 21 28 etc y a
00:11:57
saída acia
00:11:59
ordenada certo vamos ver primero agora o
00:12:03
algoritmo de ordenación por inser o que
00:12:06
que y para eso vamos Mostrar como que
00:12:10
funciona con una instancia en particular
00:12:14
eh posición J en algú momento algoritmo
00:12:18
de ordenación por inser que que posición
00:12:22
J men Un vectores ordenado si vedes
00:12:26
observan
00:12:27
aquí toda esa parte en amarelo está
00:12:31
ordenada está y vamos tentar inserir
00:12:35
toda esa parte aquí no está ordenada
00:12:37
Vamos tentar inserir o valor que está
00:12:39
posición J no lugar
00:12:42
certo eso de aquí ese elemento que
00:12:45
deseamos inserir no lugar certo ISO o
00:12:48
que o algoritmo que tenter o algoritmo
00:12:51
de ordena por inser por eso que se Chama
00:12:54
de inser porque tenta inserir un
00:12:57
elemento no lugar certo
00:13:00
c vamos guardar esa
00:13:03
posición eh ese valor
00:13:07
verd Chave esa vari Chave est guardando
00:13:12
es2 que
00:13:15
desira parte
00:13:17
vor y
00:13:19
guardamos vari
00:13:21
Chave Okay aquí estamos
00:13:25
como un problema que queremos resolver
00:13:29
que que
00:13:30
vamos
00:13:32
que2 queer colar lugar certo Okay o que
00:13:37
queos vamos ir comparando con todos
00:13:39
elementos y empurrando elementos que son
00:13:43
mayores a vamos
00:13:46
perguntar aave mayor
00:13:49
que no emp elemento yamos vamos comparar
00:13:57
con7 a
00:13:59
que2 mayor
00:14:01
que7 no
00:14:05
emp con3 aave mayor que 23 no
00:14:12
amos con 21 aave que
00:14:16
22 mayor que 21
00:14:19
samos empar elementos y
00:14:24
colamos lug
00:14:26
y cer
00:14:29
O 22 lugar certo y que queora
00:14:33
noo parte vector ordenado yotra parte
00:14:38
vector que no está ordenado certo yora
00:14:42
mmo proco para próximo elemento que serí
00:14:47
25 colocamos ji
00:14:51
jalando a
00:14:53
posición posición está elemento 2
00:14:56
guardamos 25 variável Chave y vamos
00:15:00
tentar o mesmo yos mesmas perguntas a
00:15:04
Chave mayor que 28 no empur aave mayor
00:15:08
27 no emp aave mayor que
00:15:14
23 ent
00:15:19
25i certo se aquí cu que proco que a
00:15:24
gente a gente está comparando 25 con
00:15:27
todos elementos que est antes del y
00:15:29
empurrando elementos que son mayores no
00:15:32
pior dos casos a gente que empurrar
00:15:35
todos es elementos que est aquí certo y
00:15:39
ahí continuamos agora
00:15:42
queos parte vector ordenado continuamos
00:15:45
con próximo elemento que ser colocar o
00:15:47
24 no lugar certo y agora vamos o mesmo
00:15:51
con 24 empur 2 empur 2 empur 25 pergamos
00:15:57
si aave mayor que 23 no os 24 lugar
00:16:02
certo de noos agora parte que está
00:16:06
ordenada está faltando 29 o 29 ahos o
00:16:12
mesmo pergamos con cada un elementos not
00:16:14
que seos n elementos a gente prisar no
00:16:19
pior casos vamos que aquí temos elemento
00:16:23
no lugar de
00:16:25
2os noor casos a gente que empurrar n -
00:16:29
1 elementos certo es importante notar
00:16:32
depois para anális algoritmo n caso a
00:16:35
gente no preciser nada porque femos
00:16:38
apenas pergunta o 29 mayor que 28 s ent
00:16:43
coloca posición y+ pronto y acabó
00:16:47
finalmente vetor
00:16:50
ordenado completamente desde posición
00:16:54
posición n Aquí está
00:16:56
pudo algoritmo ordena por ehos aquí ent
00:17:02
rece como parmetro vector y n que sero
00:17:06
vector estamos trando con vectores desde
00:17:10
n importante notaro parición do
00:17:15
atn que ir guardando Chave elemento que
00:17:19
desar lugar
00:17:22
certo esa parte de aquí
00:17:25
cu se queer
00:17:29
perguntar aave mayor que elemento
00:17:33
posición
00:17:34
y seave mayor empurrando elementos es de
00:17:40
aquí Ur
00:17:42
elementos que simula con es inst y final
00:17:47
cuandoo no se verd aoca aave posición
00:17:53
yto es aquí algoritmo de ordena por
00:17:57
inser
00:18:02
test ese algoritmo no verdad se joda ese
00:18:06
algoritmo o
00:18:08
pensa Cuántas veces son feitas voy botar
00:18:11
un poquillo aquí Cuántas Cuántas compara
00:18:15
es
00:18:15
algoritmo que
00:18:18
compara compara aquí aquí y aquí si por
00:18:23
exemplo garía de contar Cuántas compares
00:18:26
algoritmo a podería ese gráfico aquí
00:18:31
eh aquí para un vector deño n de uno n
00:18:35
fixo un suor deo eh 60 cuas compara
00:18:42
realiza algoritmo anterior a gente poder
00:18:46
rodar con instancias diferentes claro de
00:18:48
mesmo 60 un número de compara a conta de
00:18:53
algo número de compara a encontrar por
00:18:57
exemplo de aquí que aquí a gente no para
00:19:01
un problema deo 40 por exemplo 60 para
00:19:08
unmo un número de compar
00:19:11
diferente aquí gente
00:19:16
aquí pior
00:19:20
caso y también un mellor
00:19:24
caso que sería es de
00:19:27
aquí
00:19:32
cierto y también teng un caso medio
00:19:44
medo mesmo para una
00:19:46
instancia
00:19:48
mesmo comportamentos verdad un número de
00:19:52
comparaciones diferentes a gente podería
00:19:55
medir otras cosas por exemplo no somente
00:19:57
un número de
00:19:58
podería ser un número de atribui en
00:20:02
número de linas que son executadas os
00:20:06
varias formas de medir cu que consumo
00:20:10
deo
00:20:12
algoritmo vamos que queremos contar un
00:20:15
número máximo de
00:20:17
atribu número máximo de atribu que
00:20:21
atribu
00:20:23
aquí
00:20:25
aquí aquí aquí
00:20:29
noer
00:20:30
atribu aquí atribu aquí tamb y aquí
00:20:35
tambén vamos contar cuas que número máx
00:20:40
de algoritmo
00:20:43
eh es de
00:20:45
aquí es prima
00:20:50
lerri verd por que n n para contaras
00:20:55
atrion aquí men
00:20:59
do má ser número de atri
00:21:03
que
00:21:06
certo que cont que má para
00:21:10
pod aquí má que igual a n a gente está
00:21:15
contando atribu por atribui que trab
00:21:19
cuantas atribu
00:21:22
doer menos que l un a do a TR men
00:21:29
atribu cuas atribu
00:21:33
cuero yora es par de aquí importante
00:21:37
Cuántas ve empurra aquí Cuántas atribu
00:21:40
son feitas aquí que enas palas sertas ve
00:21:45
que empurra elemento no pior casos a a
00:21:49
máxima cuantidad quee empurrar ser que
00:21:54
vi exemp que para último elemento pior
00:21:58
casos podería empurrar n-1
00:22:01
elementos certo ahí pueder n-2 etc etc y
00:22:06
para posiciones iniciales vaer do y 1 no
00:22:12
máximo eso de aquí dar
00:22:16
que
00:22:17
eh n por n 1 sobre 2 es somatoria eh da
00:22:23
es resultado o mesmo acontecer cona se y
00:22:28
depois a L s ser o mesmo que a L do 3
00:22:31
que n - 1 se a gente a somat deo ISO o
00:22:35
resultado ser n 3n -
00:22:40
3 número máximo de atribu menor ig n 3n
00:22:46
- 3 not que a gente un cálculo a atribu
00:22:51
que for
00:22:54
realizad pens en Consumo de de consumo
00:22:58
de tempo por cada l de ex a gente contar
00:23:02
Cuántas ve executada cada l considerando
00:23:06
que cada l cons unid
00:23:10
deo vamos contaro esa l de aquí ser ex n
00:23:15
ve de aquí ser n ve n n a sa que n tamb
00:23:23
y
00:23:25
a ser
00:23:28
desp vamos pasor a c y a que vies
00:23:32
n n etc
00:23:36
etc certo
00:23:38
[Música]
00:23:39
aer ve a porque que verificar má ve para
00:23:45
poro que aquí
00:23:47
má
00:23:49
considerando c aquí ser do
00:23:56
finala deoo
00:23:58
dar ese total de aquí 3n mán -8 porora
00:24:04
estamos calculando cu que cons
00:24:08
considerando que cada l cons unid
00:24:12
deo
00:24:14
eh tambén podemos considerar ser má
00:24:18
detal aí y considerar que cadaa y de có
00:24:22
consum unidades de tiempo Cada deas
00:24:25
consum unidades de tiempo diferente
00:24:29
ISO aar n expr no Mostrar como que feo
00:24:33
es
00:24:34
cálculo multiplicar
00:24:37
cada cada un valores que tamos slide
00:24:40
anterior
00:24:41
por no final vamos expr tipo ser expr C2
00:24:46
n c1 c en que C2 c y
00:24:51
C constantes Que depend
00:24:54
ti verdad a gente varos cálculos
00:24:58
diferentes formas de calcular o consumo
00:25:00
de tempo de algoritmo cuando calculamos
00:25:02
número de atribui chegamos n ese result
00:25:06
cuando consideramos que amos computar
00:25:09
todas linas que foron executadas no
00:25:11
algoritmo considerando que cada una
00:25:14
consume una unidad de tempo lamos n ese
00:25:16
resultado y cuando consideramos que cada
00:25:18
una consume ti unidades de tempo lamos n
00:25:21
otro resultado má será que para un n
00:25:25
Grand diferencia Fer una contag t
00:25:29
deter esa de aquí muo má
00:25:32
detal será que diferen a gente Vero de
00:25:37
aquí a ent n noas análises vamos ficar
00:25:41
satisfeitos anális má aproximadas
00:25:44
pretendemos medir apenas a ordem de
00:25:46
grandeza función de tempo algoritmo cu
00:25:49
consum algoritmo Queremos saber para n
00:25:53
grandes parao vamos introducir alguns
00:25:56
conitos que
00:25:59
son n ese caso anotación o teta y ega o
00:26:05
oma y teta es conitos será apresentados
00:26:09
Noa próxima
00:26:11
aula ent espero quean gostado de esa
00:26:14
aula y no percan a nua aula número
00:26:19
[Música]
00:26:26
do
00:26:27
[Música]
00:26:39
[Música]
00:26:49
[Música]
00:26:56
ah
00:26:59
[Música]
00:27:05
Oh
