ejercicios: diseño de soluciones de simplificación y dyv · ejercicios 08: diseño de soluciones...

Ejercicios 08: Diseño de soluciones con Programación Voraz

1

Análisis de algoritmos

M. en C. Edgardo Adrián Franco Martínez http://www.eafranco.comedfrancom@ipn.mx@edfrancom edgardoadrianfrancom

1. 10020 - Minimal coverage

2

Diseño de soluciones con Programación Voraz

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=657&page=show_problem&problem=961

An

ális

is d

e al

gori

tmo

sEj

erc

icio

s 0

8:

Dis

eño

de

solu

cio

nes

Gre

ed

yP

rof.

Edga

rdo

Ad

rián

Fra

nco

Mar

tín

ez

2. 10382 - Watering Grass

3

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=657&page=show_problem&problem=1323

An

ális

is d

e al

gori

tmo

sEj

erc

icio

s 0

8:

Dis

eño

de

solu

cio

nes

Gre

ed

yP

rof.

Edga

rdo

Ad

rián

Fra

nco

Mar

tín

ez

3. 12405 - Scarecrow

4

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=657&page=show_problem&problem=3836

An

ális

is d

e al

gori

tmo

sEj

erc

icio

s 0

8:

Dis

eño

de

solu

cio

nes

Gre

ed

yP

rof.

Edga

rdo

Ad

rián

Fra

nco

Mar

tín

ez

4. Bear and Row 01

5

https://www.codechef.com/APRIL17/problems/ROWSOLD

An

ális

is d

e al

gori

tmo

sEj

erc

icio

s 0

8:

Dis

eño

de

solu

cio

nes

Gre

ed

yP

rof.

Edga

rdo

Ad

rián

Fra

nco

Mar

tín

ez

5. 11631 - Dark roads

6

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=673&page=show_problem&problem=2678

An

ális

is d

e al

gori

tmo

sEj

erc

icio

s 0

8:

Dis

eño

de

solu

cio

nes

Gre

ed

yP

rof.

Edga

rdo

Ad

rián

Fra

nco

Mar

tín

ez

6. 544 - Heavy Cargo

7

https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=485

An

ális

is d

e al

gori

tmo

sEj

erc

icio

s 0

8:

Dis

eño

de

solu

cio

nes

Gre

ed

yP

rof.

Edga

rdo

Ad

rián

Fra

nco

Mar

tín

ez

7. Andar Chido Reloaded

8

https://omegaup.com/arena/problem/Andar-Chido-Reloaded#problems

An

ális

is d

e al

gori

tmo

sEj

erc

icio

s 0

8:

Dis

eño

de

solu

cio

nes

Gre

ed

yP

rof.

Edga

rdo

Ad

rián

Fra

nco

Mar

tín

ez

8. 1193 - Radar Installation

9

https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=3634

An

ális

is d

e al

gori

tmo

sEj

erc

icio

s 0

8:

Dis

eño

de

solu

cio

nes

Gre

ed

yP

rof.

Edga

rdo

Ad

rián

Fra

nco

Mar

tín

ez

7. Función Horrible

10

https://omegaup.com/arena/problem/Formula-Horrible/#problems

An

ális

is d

e al

gori

tmo

sEj

erc

icio

s 0

8:

Dis

eño

de

solu

cio

nes

Gre

ed

yP

rof.

Edga

rdo

Ad

rián

Fra

nco

Mar

tín

ez

8. Organizando Cajas

11

http://matcomgrader.com/problem/9236/organizando-cajas/

An

ális

is d

e al

gori

tmo

sEj

erc

icio

s 0

8:

Dis

eño

de

solu

cio

nes

Gre

ed

yP

rof.

Edga

rdo

Ad

rián

Fra

nco

Mar

tín

ez

9. Bear and Clique Distances

12

https://www.codechef.com/APRIL17/problems/CLIQUED

An

ális

is d

e al

gori

tmo

sEj

erc

icio

s 0

8:

Dis

eño

de

solu

cio

nes

Gre

ed

yP

rof.

Edga

rdo

Ad

rián

Fra

nco

Mar

tín

ez

10. IOI 1996 - Un Juego

13

https://omegaup.com/arena/problem/Un-Juego#problems

An

ális

is d

e al

gori

tmo

sEj

erc

icio

s 0

8:

Dis

eño

de

solu

cio

nes

Gre

ed

yP

rof.

Edga

rdo

Ad

rián

Fra

nco

Mar

tín

ez

• Se deberá incluir la captura de pantalla del problemaaceptado en el juez online con fecha y hora.

• Incluir la redacción de cada ejercicio.

• Explicar cada solución de Programación Voraz y su análisis delorden de complejidad (Por inducción si el análisis no es posible de realizar

por medio del teorema maestro).

• Incluir el algoritmo y código de la solución.

• Para que los ejercicios cuenten al 100% deberán decontestarse al menos 1 correctamente.

• Portada con fotografía y encabezados de pagina.

14

Observaciones

An

ális

is d

e al

gori

tmo

sEj

erc

icio

s 0

8:

Dis

eño

de

solu

cio

nes

Gre

ed

yP

rof.

Edga

rdo

Ad

rián

Fra

nco

Mar

tín

ez

Lista cotejo de la evaluación del ejercicio

15

Indicador SI NO

Redacción del Problema (El reporte cuenta con

encabezados y los datos están redactados

completamente)

Análisis del Problema (Identifica y explica las

instrucciones o variables a considerar para el análisis)

Desarrollo del Problema (Explica el análisis

realizado y los pasos con lo que llego al resultado,

muestra las pantallas de envió y “Acepted” en el Juez

Online)

Secuencia Lógica (Hay una correcta

interpretación de los conceptos, cálculos y formulas)

Código (El código es original, esta autodocumentado

y documentado. )

An

ális

is d

e al

gori

tmo

sEj

erc

icio

s 0

8:

Dis

eño

de

solu

cio

nes

Gre

ed

yP

rof.

Edga

rdo

Ad

rián

Fra

nco

Mar

tín

ez

Fecha máxima de entrega en el sitio Web

16

• La entrega se realizará a través de la página:

http://www.eafranco.comEntregar a más tardar el día lunes 18 de junio de 2018

An

ális

is d

e al

gori

tmo

sEj

erc

icio

s 0

8:

Dis

eño

de

solu

cio

nes

Gre

ed

yP

rof.

Edga

rdo

Ad

rián

Fra

nco

Mar

tín

ez

• Grupo y contraseña

• Escribir y almacenar las claves de confirmación, paraaclaraciones a con respecto a la evaluación.

17

An

ális

is d

e al

gori

tmo

sEj

erc

icio

s 0

8:

Dis

eño

de

solu

cio

nes

Gre

ed

yP

rof.

Edga

rdo

Ad

rián

Fra

nco

Mar

tín

ezGrupo Contraseña

3CM1 analisis3cm1

3CM3 analisis3cm3