PRIMERA ETAPAHasta el 7 de mayo de 2016

SELECCIÓN E INSCRIPCIÓN EN CADA UNIDAD EDUCATIVA

SEGUNDA ETAPA5 de junio de 2016

PRUEBA SIMULTÁNEA A NIVEL NACIONAL EN CADA DISTRITO EDUCATIVO

TERCERA ETAPA31 de julio de 2016

PRUEBA SIMULTÁNEA A NIVEL NACIONAL EN CADA DEPARTAMENTO

CUARTA ETAPA3 al 8 de octubre de 2016

FINAL NACIONAL

LA PAZ - BOLIVIA

INFORMÁTICA

Ministerio de Educación

9

NOMBRE COMPLETOCARGO

UNIVERSIDAD MAYOR DE SAN ANDRÉS (UMSA)

AREA REPRESENTADA DURANTE LA 6TA

OCEPB• Ing. Mirko Raljevic Ergueta• Lic. Robert Muñoz

• Director del Planetario Max Schreier• Investigador del Planetario Max

Schreier

Astronomía -Astrofísica

• Lic. Roberto Apaza Chávez

• Lic. Guillermina Miranda

• Docente Investigador - carrera Biología

• Docente Investigador - carrera Biología

Biología

• Lic. Evaristo Mamani Carlo • Lic. Maria Verónica

Subieta Frías

• Docente - carrera Física• Docente - carrera Física Física

• MSc. Jorge Humberto Terán Pomier

• Lic. Jhonny Roberto Felipez Andrade

• Docente Investigador - carrera Informática

• Docente - carrera Informática Informática

• Ing. José Ayala Montes• Ing. Nelson Aban Botello

• Docente - carrera Geografía• Docente - carrera Geografía Geografía

• Ing. Sonia Córdero • Dr. Jimmy Santamaría

Torrez

• Docente Facultad de Ingeniería• Docente Facultad de Ciencias Puras Matemática

• Dr. Yohnni Cuanca Sarzuri• Ing. Javier Sanabria Garcia• Univ. Juan Pablo Crespo

Vargas

• Docente - carrera Informática• Docente - carrera Ing. Electróna• Carrera Ing. Electróna Robótica

• Dr. Rigoberto Choque • Ing. Grima Velazco

Alconde

• Docente Investigador Facultad de Ciencias Puras

• Docente Facultad de Ingeniería Química

COMITÉ CIENTÍFICO ACADÉMICO NACIONAL 6TA OLIMPIADA CIENTÍFICA ESTUDIANTIL PLURINACIONAL

BOLIVIANA (6TA OCEPB)

10

6ta Olimpiada Científica Estudiantil Plurinacional Boliviana

NOMBRE COMPLETO CARGO – UNIVERSIDAD AREA REPRESENTADA DURANTE LA 6TA OCEPB

MSc. Rocío Guzmán Saavedra

Docente investigador de la Universidad Mayor de San Simón

Astronomía- Astrofísica

MSc. Erika Fernandez Jefe de la Carrera de Biología de la Universidad Mayor de San Simón Biología

MSc. Marko Andrade Uzueta

Docente investigador de la Universidad Mayor de San Simón Física

MSc. Leticia Blanco Coca Docente de la Universidad Mayor de San Simón Informática

Ing. Raul José Ayala Montes

Director de la Carrera de Ingeniería Geográfica de la Universidad Mayor de San Andrés

Geografía

Ing. Gustavo Michel García

Docente de la Universidad Mayor de San Andrés Matemática

Egr. Willmar Pimentel SossaMSc. Carlos Lazo de la Vega

Director ICPC - Bolivia

Docente Universidad Católica Boliviana

Robótica

Dr. Leonardo Guzmán Alegría

Docente Investigador de la Universidad Mayor de San Andrés Química

COMITÉ CIENTÍFICO ACADÉMICO DE ASESORAMIENTO NACIONAL

6TA OLIMPIADA CIENTÍFICA ESTUDIANTIL PLURINACIONAL BOLIVIANA (6TA OCEPB)

Ministerio de Educación

11

6TA OLIMPIADA CIENTÍFICA ESTUDIANTIL PLURINACIONAL BOLIVIANA (6TA OCEPB)

CONVOCATORIA GENERALEl Ministerio de Educación, a través del Viceministerio de Ciencia y Tecnología, en coordinación con el Viceministerio de Educación Regular y las Universidades bolivia-nas: UMSA, UMSS, UTO, UATF, UMRPSFX, UPSA, UAB, UAJMS, UAP, UAGRM, UCB, UPDS; Direcciones Departamentales y Distritales de Educación; convocan a la 6ta Olimpiada Científica Estudiantil Plurinacional Boliviana (6ta OCEPB).

Participantes: Estudiantes bolivianos del Subsistema de Educación Regular de todas las Unidades Educativas Fiscales, Privadas y de Convenio del Estado Plurinacional de Bolivia; en las áreas de: ASTRONOMÍA - ASTROFÍSICA, BIOLOGÍA, FÍSICA, GEOGRAFÍA, INFORMÁTICA, MATEMÁTICA, ROBÓTICA y QUÍMICA, de acuerdo al siguiente detalle:

ÁREA GRADOS

Astronomía - Astrofísica De 6.o primaria a 6.o secundaria

Biología De 3.o a 6.o de secundaria

Física De 6.o primaria a 6.o secundaria

Geografía De 3.o a 6.o de secundaria

Informática De 5.o de primaria a 6.o de secundaria

Matemática De 1.o a 6.o secundaria

Robótica De 1.o primaria a 6.o secundaria

Química De 2.o a 6.o de secundaria

Objetivo General: Promover el desarrollo de capacidades científicas y tecnológicas e identi-

ficar talentos científicos en estudiantes de educación regular como apor-te al desarrollo científico, productivo, económico y social del país.

Objetivos Específicos:a) Estimular el desarrollo de capacidades de investigación en estudiantes en

las áreas de Astronomía - Astrofísica, Biología, Matemáticas, Física, Infor-mática, Robótica, Geografía y Química.

b) Motivar la creatividad y el interés de los estudiantes por las Ciencias y la Tecnología.

c) Despertar en los estudiantes sus vocaciones científicas y tecnológicas.d) Fomentar y contribuir al mejoramiento del aprendizaje y la enseñanza de

las Ciencias y la Tecnología.e) Promover la permanente capacitación y actualización de conocimientos

de los profesores de Ciencias.

12

6ta Olimpiada Científica Estudiantil Plurinacional Boliviana

f) Identificar y promocionar a estudiantes con potencialidades en ciencias y fortalecer sus capacidades.

g) Establecer relaciones de amistad y cooperación entre estudiantes y profe-sores de nuestro país y de otros países en torno a las ciencias.

h) Crear oportunidades para el intercambio de experiencias e información acerca de programas, técnicas de aprendizaje y enseñanza de las ciencias en nuestro país y en países vecinos.

i) Crear espacios de articulación entre el Ministerio de Educación y las Universidades Bolivianas, para mejorar la calidad de la educación en ciencias.

Inscripción: La inscripción es gratuita, única y necesaria y se llevará a cabo a partir del 24 de marzo hasta el 7 de mayo de 2016. Para la 2.a, 3.a y 4.a etapa participan directamen-te los estudiantes clasificados en la etapa anterior.

Los profesores de las áreas de la Olimpiada, en coordinación con sus directores de Uni-dades Educativas, deben inscribir a un máximo de diez (10) estudiantes por grado y por área, a través de una prueba u otro mecanismo interno. El periodo de inscripción com-prende desde el 24 de marzo al 7 de mayo, de forma virtual a través de la página web olimpiadas.educabolivia.bo; en lugares alejados la Dirección Distrital de Educación es responsable de la inscripción vía Internet. Los estudiantes podrán participar en el nivel o grado que les corresponda o superiores y hasta en dos áreas como máximo. Etapas: La Olimpiada se desarrolla en 4 etapas:

1. Primera Etapa: del 24 de marzo al 7 de mayo, selección e inscripción en cada unidad educativa.

2. Segunda Etapa: 5 de junio, prueba simultánea a nivel nacional en cada-distrito educativo.

3. Tercera Etapa: 31 de julio, prueba simultánea a nivel nacional en cada departamento.

4. Cuarta Etapa: del 3 al 8 de octubre, pruebas finales en la ciudad de La Paz.

Lugares: La lista de los espacios físicos donde se aplicarán las pruebas será publicada oportunamente en las Direcciones Distritales y Departamentales de Educación, en las Universidades participantesy en la página web olimpiadas.educabolivia.bo

Horarios: Las pruebas para la Segunda y Tercera Etapas se realizarán:

HORAS ÁREAS

08:00 – 10:00 BIOLOGÍA – MATEMÁTICA – GEOGRAFÍA

08:00 – 13:00 ROBÓTICA

10:00 – 12:00 ASTRONOMÍA - ASTROFÍSICA QUÍMICA

12:00 - 14:00 FÍSICA

Ministerio de Educación

13

14:00 - 17:00 INFORMÁTICAContenidos mínimos: en la página web olimpiadas.educabolivia.bo se encuentran disponibles las convocatorias específicas de cada área, los contenidos mínimos por área/grado/etapa fueron elaborados por los Comités Académicos Departamentales confor-mados por representantes de las Universidades participantes, el Comité Académico Na-cional conformado por representantes de la UMSA y por el Ministerio de Educación.

Las convocatorias específicas impresas de cada área serán distribuidas a todas las Uni-dades Educativas del país, a través de sus Direcciones Departamentales y Distritales de Educación. Premios e incentivos: el Ministerio de Educación podrá entregar premios especiales e incentivos a estudiantes y unidades educativas (Fiscales, Privadas y de Convenio), consis-tentes en equipos de computación, audiovisuales, material bibliográfico y otros durante el desarrollo de las diferentes etapas de la 6ta OCEPB.

Los estudiantes ganadores de cada área y grado a nivel departamental y nacional, ob-tendrán diplomas, premios especiales, medallas de Oro, Plata, Bronce y Mención de Ho-nor, conforme a lo establecido en sus convocatorias específicas del área.

Los estudiantes clasificados en la Cuarta Etapa serán acreedores a un certificado de par-ticipación.

Los estudiantes ganadores de la Cuarta Etapa conformarán los equipos que podrán repre-sentar al país en Olimpiadas Científicas Estudiantiles Internacionales en la gestión 2017.

Los profesores tutores inscritos en el escalafón docente, cuyos estudiantes sean ganado-res de medallasde oro a nivel nacional, obtendrán certificados con valor curricular.

Los profesores tutores de los estudiantes ganadores de la Tercera y Cuarta Etapa podrán recibir un certificado que constate su labor, de sus Direcciones Departamentales de Edu-cación, al igual que el personal de apoyo logístico.

Los profesores tutores de los estudiantes que hayan obtenido el primer lugar en la prue-bas clasificatorias, podrán formar parte de la delegación boliviana y participar de even-tos internacionales, siempre que hayan participado del entrenamiento de los estudian-tes preseleccionados.

Mayor Información:MINISTERIO DE EDUCACIÓN

olimpiadas.educabolivia.boe-mail: olimpiada@minedu.gob.bo

Telf.: 2 2900490 – 2 2900491

Convocatoriasy contenidos mínimos

108

6ta Olimpiada Científica Estudiantil Plurinacional Boliviana

6TA OLIMPIADA CIENTÍFICA ESTUDIANTIL PLURINACIONAL BOLIVIANA 2016

CONVOCATORIA INFORMÁTICA

1. PRESENTACIÓN

El Ministerio de Educación, a través del Viceministerio de Ciencia y Tecnología, el Comité Na-cional de la ACM ICPC Bolivia (Competencia de Programación para Universitarios) y el Comité Nacional de la OBI (Olimpiada Boliviana de Informática), convocan a los estudiantes bolivianos del Subsistema de Educación Regular de las Unidades Educativas Públicas, Privadas y de Con-venio a participar de la Olimpiada Boliviana de Informática que clasificará a los representantes bolivianos a la IOI - 2017 (República Islámica de Irán).

La Olimpiada Boliviana de Informática es una competencia académica que inició el año 2011 y estuvo orientada a jóvenes de primaria y secundaria (de 5.o de primaria a 6.o de secundaria), que tienen agrado por resolver problemas prácticos usando lógica, algoritmos y la programación en una computadora. Esta Olimpiada forma parte del Sistema Internacional de Olimpiadas Científicas, con su evento denominado Olimpiada Internacional de Informática (IOI-Internatio-nal Olympiad in Informatics).

Desde el año 2011 el Ministerio de Educación, a través del Viceministerio de Ciencia y Tecno-logía, las Universidades Bolivianas y las Direcciones Departamentales de Educación, llevan a cabo la Olimpiada Científica Estudiantil Plurinacional Boliviana (OCEPB), evento que incluye a la OBF.

Este año la 6ta Olimpiada Científica Estudiantil Plurinacional Boliviana, incluye a la Olimpiada de Informática y la etapa final (cuarta etapa), se llevará a cabo en la ciudad de La Paz, sede del evento nacional.

El apoyo académico de la Olimpiada Boliviana de Informática, juega un rol importante en el desarrollo de las OCEPB; en esta oportunidad la Universidad Mayor de San Andrés, a través de la Facultad de Ingeniería, la Facultad de Ciencias Puras y Naturales y la Facultad de Ciencias Geológicas, con sus diferentes Carreras, asumen el reto de apoyar académicamente a la “6ta

Olimpiada Científica Estudiantil Plurinacional Boliviana”, conformando el Comité Académico Nacional, en coordinación con las demás Universidades del Sistema Universitario del País.

2. OBJETIVOS

• Contribuir al mejoramiento de la enseñanza y del aprendizaje de la Informática en todas las Unidades Educativas del país.

• Identificar y preparar a los jóvenes talentosos para que representen a sus departamentos y al país en competencias nacionales e internacionales de programación en formatos presen-ciales físicos e internet (online).

• Fomentar valores de solidaridad, compañerismo y amistad entre estudiantes y profesores.

• Promover el proceso de inserción formal de la Informática como materia, dentro de la currí-

109

INFORMÁTICA

cula oficial, acorde a los tiempos de innovación de esta área a nivel mundial, como referente de progreso de los países.

• Fomentar el intercambio de conocimientos y experiencias entre los profesores participan-tes y la comunidad en general en cada uno de los eventos.

3. REQUISITOS INDISPENSABLES

3.1 Ser Estudiante de nacionalidad boliviana del Subsistema de Educación Regular de Unidades Educativas: Fiscales, Privadas y de Convenio del Estado Plurinacional de Bolivia.

3.2 Estar inscrito en el “Sistema Informático de la Olimpiada Científica” olimpiadas.educabolivia.bo.

3.3 Estar habilitado en la página oficial del Ministerio de Educación olimpiadas.educabolivia.bo, para su respectiva participación en cada etapa.

3.4 Portar su documento de identificación personal (cédula de identidad o pasaporte) durante las pruebas de selección.

3.5 Para que las pruebas sean evaluadas en las diferentes etapas, es indispensable el envío de su prueba en formato digital.

3.6 Portar sólo los materiales requeridos por el Comité Científico Académico Nacional.

3.7 Queda terminantemente prohibido el uso de celulares, audífonos, manuales, libros y cualquier tipo de equipo electrónico no autorizado por el Comité Científico Académico Nacional.

4. ETAPAS Y CLASIFICACIÓN

4.1 Participarán estudiantes de nacionalidad boliviana de las Unidades Educativas: Fiscales, Privadas y de Convenio de todo el país, en los grados de 6.o de primaria, 1.o, 2.o, 3.o, 4.o, 5.o y 6.o de secundaria.

La participación se desarrollará bajo el siguiente cronograma:

ETAPA ÁMBITO MODALIDAD INSCRIPCIÓN PRUEBA

Primera Unidad Educativa Presencial

Del 24 de marzo al 7 de mayo de 2016 en:

olimpiadas.educaboli-via.bo

Previa valoración interna en cada unidad educativa

Segunda Distritos Educativos Presencial Automática

5 de junio de 2016 NOTA. El nivel 1 tendrá su defensa pre-sencial junto con el área de robótica, una semana después de la Etapa departamental

Tercera Departamen-tal Presencial Automática 31 de julio de 2016

110

6ta Olimpiada Científica Estudiantil Plurinacional Boliviana

Cuarta Nacional Presencial Automática Del 3 al 8 de octubre de 2016 en la ciudad de La Paz

4.2 Materiales: Los materiales serán permitidos sólo a requerimiento del Comité Científico Académico Nacional.

En cada etapa los estudiantes deben portar cédula de identidad o pasaporte con carácter obligatorio.

4.3 Primera etapa. Se desarrolla en cada Unidad Educativa del Estado Plurinacional de Bolivia.

4.3.1 Los estudiantes no deberán ser mayores a 19 años hasta el 01 de julio de 2016; debido a que los estudiantes ganadores para poder ser habilitados en la Olimpiada Internacional de Informática, no deben tener más de 20 años cumplidos hasta el 1° de julio de 2017.

4.3.2 Cada unidad educativa asignará a un entrenador (coach) de equipo que se encargará de preparar a sus estudiantes. Es recomendable que el entrenador tenga conocimientos en programación de algoritmos en lenguajes C/C++. El entrenador puede ser el profesor de computación asignado a la unidad educativa o un tutor designado por el Director.

Para ser tutor oficial de un equipo de la Unidad Educativa, sólo se necesita el aval del Direc-tor respectivo, no necesariamente ser el profesor asignado al área.

4.3.3 Todos los estudiantes participantes y el tutor deberán tener una dirección de correo electrónico válida y escribirla correctamente durante el proceso de inscripción.

4.3.4 Niveles:

• Nivel0.Estudiantes de quinto de primaria a tercero de secundaria con conocimientos de Internet, Sistema Operativo Windows, Software Libre GNU- Linux y Ofimática.

• Nivel1.Estudiantes en equipos de hasta 2 personas de quinto de primaria a tercero de secundaria, con conocimientos de un lenguaje programación visual orientado al desa-rrollo de aplicaciones de animación, historias interactivas o creación de videojuegos.

• Nivel2.Estudiantes de primero a cuarto de secundaria que tengan conocimiento de programación básica en lenguaje C/C++ utilizando CodeBlocks.

• Nivel3.Estudiantes de primero a sexto de secundaria que tengan conocimiento de programación estructurada en lenguaje C/C++ utilizando CodeBlocks.

Un estudiante habilitado para cualquier nivel, no podrá inscribirse a un nivel inferior.

4.4 Segunda etapa: Se desarrolla en cada Distrito Educativo del país.

4.4.1 Todos los participantes: individuales, equipos de unidad educativa y sus tutores de-berán ingresar a: http://registro.icpc-bolivia.edu.bo, donde se validará su RUDE y se gene-rará su prueba electrónica correspondiente.

4.4.2 La competencia es grupal para el nivel 1 e individual para los niveles 0,2 y 3, para tal efecto se utilizarán plataformas informáticas.

4.4.3 Los competidores de Nivel 0 deberán resolver un examen de selección múltiple sobre Windows, Internet y ofimática en un determinado tiempo.

4.4.4 Los competidores de Nivel 1 deberán presentar una propuesta de su aplicación. La evaluación contemplará un avance de la aplicación propuesta de acuerdo al contenido y requerimientos establecidos.

111

INFORMÁTICA

4.4.5 Los competidores de Nivel 2 deberán desarrollar las soluciones a los problemas pro-puestos en lenguaje de Programación C/C++ utilizando CodeBlocks.

4.4.6 Los competidores de Nivel 3 deberán desarrollar las soluciones a los problemas pro-puestos en lenguaje de Programación C/C++ utilizando CodeBlocks.

4.4.7 Los contenidos de cada nivel de competencia se detallan en la sección 11 de la pre-sente convocatoria.

4.4.8 Los clasificados de la segunda etapa se publicarán de forma oportuna y de acuerdo a convocatoria general de la 6ta OCEPB.

4.4.9 Los criterios de clasificación a la Tercera fase son:

- Para el Nivel 0 se considerará como nota mínima de clasificación el 50% +1 de res-puestas correctas del total de preguntas planteadas.

- Para el Nivel 1 se considerará como clasificados a los equipos que tengan cumplidos el 80% de los requerimientos de la hoja de evaluación, respecto a las propuestas presentadas y el avance de la aplicación.

- Para el Nivel 2 al menos un problema resuelto.

- Para el Nivel 3 la ponderación de puntaje considerará un máximo de 300 puntos (100 puntos por problema) y el mínimo será determinado por el Comité de Problemas, cada competidor será notificado mediante el sistema de evaluación al momento de iniciar su examen.

4.5 Tercera etapa: Se desarrolla en cada departamento del país.

4.5.1 Los competidores de Nivel 0 deberán resolver un examen de selección múltiple sobre Linux, Internet y ofimática en un determinado tiempo, para tal efecto se utilizarán platafor-mas informáticas.

4.5.2 Los competidores de Nivel 1 deberán presentar la aplicación desarrollada a través de la plataforma informática y defenderla en forma presencial.

4.5.3 Los competidores de Nivel 2 deberán desarrollar las soluciones a los problemas pro-puestos en lenguaje de Programación C/C++ utilizando CodeBlocks, para tal efecto se utili-zarán plataformas informáticas.

4.5.4 Los competidores de Nivel 3 deberán desarrollar las soluciones a los problemas pro-puestos en lenguaje de Programación C/C++ utilizando CodeBlocks, para tal efecto se utili-zarán plataformas informáticas.

4.5.5 Los contenidos de cada nivel de competencia se detallan en la sección 11 de la pre-sente convocatoria.

4.5.6 Clasifican a la cuarta etapa veinte (20) estudiantes: (7) estudiantes del nivel 2, (7) estu-diantes del nivel 3 y (6) estudiantes del nivel 1 (los tres mejores equipos) de cada departa-mento.

4.5.7 La clasificación del nivel 0 es sólo departamental, por lo que NO PARTICIPA en la cuarta etapa (nacional).

4.5.8 En caso que un departamento no tenga clasificados en alguno de sus niveles, el Coor-dinador Departamental podrá invitar hasta un máximo de 2 por nivel, luego de una revisión detallada de todas las pruebas. En el caso que tenga un clasificado en alguno de sus niveles, podrá invitar a uno adicional. En el caso de que tenga dos o más clasificados en alguno de

112

6ta Olimpiada Científica Estudiantil Plurinacional Boliviana

sus niveles, no se puede realizar invitaciones.

4.6 Cuarta etapa: Se desarrollará en la ciudad de La Paz. Los clasificados de la tercera etapa y el “pool” de competidores: los mejores 9 estudiantes (si corresponde, por desempeño, edad y grado) de la preselección boliviana de la Olimpiada 2015, serán convocados a participar directamente de la cuarta etapa de la presente Olimpiada.

4.6.1 La competencia es de carácter individual a pesar que se hayan inscrito como equipo.

4.6.2 Los competidores de Nivel 1 deberán presentar la aplicación desarrollada a través de la plataforma informática y defenderla en forma presencial.

4.6.3 Los competidores de Nivel 2 deberán desarrollar las soluciones a los problemas pro-puestos en lenguaje de Programación C/C++ utilizando CodeBlocks.

4.6.4 Los competidores de Nivel 3 deberán desarrollar las soluciones a los problemas pro-puestos en lenguaje de Programación C/C++ utilizando CodeBlocks.

La preselección boliviana estará conformada por los mejores clasificados en los niveles 2 y 3.

El entrenamiento de la preselección, que inicia en septiembre de 2016, estará a cargo del Comité del ICPC Bolivia, del mismo se seleccionará un máximo de 4 estudiantes que confor-marán el equipo boliviano para la Olimpiada Internacional de Informática el 2017.

Los resultados obtenidos en la Fase Nacional (ubicaciones y medallas) no serán determi-nantes al momento de definir la selección nacional para representar a Bolivia en la Final Mundial.

5. TUTORES

Cada Unidad Educativa asignará un entrenador (coach) de equipo que se encargará del entre-namiento del estudiante. Es recomendable que el tutor ó entrenador tenga conocimientos en programación de algoritmos en lenguajes C/C++. El entrenador puede ser el profesor de computación asignado a la unidad educativa o un tutor designado por el Director.

Para ser tutor oficial de un equipo de la Unidad Educativa, sólo se necesita el aval del Direc-tor respectivo, no necesariamente ser el profesor asignado al área. El tutor deberá tener una dirección de correo electrónico válida que deberá registrar al momento de inscribir a sus es-tudiantes.

Cuarta etapa: Entre los tutores de los estudiantes mejor puntuados de la tercera etapa, el Co-mité Científico Académico Departamental se encargará de seleccionar al tutor que será res-ponsable de capacitar a su delegación departamental y de acompañarla en la etapa nacional.

El profesor del estudiante que ocupe el primer lugar en el examen de 5.o de secundaria podrá viajar con el equipo boliviano al evento internacional respectivo, siempre y cuando haya par-ticipado efectivamente con el Comité Científico Académico en el entrenamiento de los estu-diantes seleccionados.

6. COMITÉS ORGANIZADORES

Para cada una de las etapas se conformarán Comités Organizadores o responsables:

Primera etapa: Director de la Unidad Educativa.

113

INFORMÁTICA

Segunda Etapa: Comité Organizador Distrital.

Tercera Etapa: Comité Organizador Departamental.

Cuarta Etapa: Comité Organizador, Comité Académico Departamental, Comité Científico Académico Nacional de la UMSA y Comité Nacional de la Olimpiada Informática.

El Comité Nacional de Problemas, elaborará las pruebas para todas las fases, incluida la final nacional.

7. COMPETIDORES

Los estudiantes competirán observando el Honor Olímpico, y debe observarse el Reglamento de Competencia para el área Informática. (Ver anexo I).

8. CARACTERÍSTICAS, DISEÑO Y CALIFICACIÓN DE LAS PRUEBAS

8.1 En la primera etapa, El proceso de selección es definido por la Unidad Educativa, se reco-mienda preservar principios de competitividad.

8.2 Segunda etapa. Las pruebas serán elaboradas y puestas a disposición de cada Distrito Edu-cativo por parte del Comité Nacional de la Olimpiada. Éstas serán provistas a los responsa-bles de la toma de las pruebas, a través de un sistema evaluador de exámenes que construi-rá pruebas distintas para cada estudiante que esté registrado en el sistema de inscripción.

8.3 Tercera etapa. Las pruebas serán elaboradas y puestas a disposición de cada departamen-to por parte del Comité Nacional de la Olimpiada. Éstas serán provistas a los responsables de la toma de las pruebas a través de un sistema evaluador de exámenes que construirá pruebas distintas para cada estudiante que esté registrado en el sistema de inscripción. La evaluación para los niveles 2 y 3 será de forma presencial utilizando el Juez Virtual CMS.

8.4 Cuarta etapa. Las pruebas serán elaboradas por parte del Comité Nacional de la Olimpiada. La evaluación será de forma presencial utilizando el Juez Virtual CMS.

9. PREMIOS, ESTÍMULOS Y RECONOCIMIENTOS

9.1 Los premios, estímulos e incentivos a los participantes ganadores y a sus profesores tutores en su respectiva jurisdicción, se describen en la convocatoria general de la OCEPB.

9.2 De los 7 clasificados de los niveles 2 y 3, y de los 6 clasificados del nivel 1 por departamento, existirá un cupo rural que será otorgado al mejor clasificado no importando su ubicación general, los restantes 6 serán asignados a los mejores clasificados. Si ningún participante del área rural logra tener la nota mínima requerida por el Comité Nacional, entonces no podrá aplicarse esta regla.

9.3 En la cuarta etapa la Universidad Boliviana y el Ministerio de Educación gestionarán y otor-garán: premios, medallas, diplomas y otros incentivos a los estudiantes ganadores y partici-pantes, así como a los profesores tutores participantes.

9.4 Clasificación a eventos internacionales.

Los estudiantes que participaran en Olimpiadas Internacionales durante la presente ges-tión, son aquellos que fueron seleccionados durante la 5a versión de la OCEPB y son capa-

114

6ta Olimpiada Científica Estudiantil Plurinacional Boliviana

citados, desde la pasada gestión hasta la fecha de su respectiva participación en el evento internacional.

En la 6ta Versión los estudiantes más destacados estarán sujetos a una selección definitiva, realizada por el Comité Científico Académico Nacional, selección que se efectuará previa etapa de preparación y evaluación de los pre-clasificados. La preparación consiste en ac-tividades académicas a realizarse en las Universidades participantes de la OCEPB, desde noviembre de 2016 hasta julio de 2017.

10. DISPOSICIONES COMPLEMENTARIAS

10.1 Cada Comité Organizador resolverá, en la etapa correspondiente, los aspectos que no estén contemplados en la presente convocatoria.

10.2 El Comité Científico Académico Nacional resolverá, en la cuarta etapa, los aspectos que no estén contemplados en la presente convocatoria.

11. CONTENIDOS MÍNIMOS

El material de estudio para los Niveles 2 y 3 está disponible para todos los estudiantes interesa-dos en participar en: http://olimpiada.icpc-bolivia.edu.bo

Los contenidos mínimos de todas las etapas de la 6ta OCEPB, se detallan a continuación; sin embargo, también se podrá incluir en las pruebas contenidos de niveles inferiores.

11.1 NIVEL 0

11.1.1 Contenido mínimo de la Segunda Etapa:

- Windows 7: Introducción- Manejo Básico de Internet- Suite Ofimática Office 2010:

•Hoja de cálculo: Excel•Procesador de palabras: Word•Presentaciones: Power Point

- Redes Sociales- Riesgos del Internet

11.1.2 Contenido mínimo de la Tercera Etapa:

- Software Libre (se describe la filosofía de Software Libre)•Introducción al software libre•Qué es GNU-Linux?•Licencia GPL•Licencia Open Source

- Instalación y configuración de una distribución GNU-Linux•Panorama general de las distribuciones GNU-Linux•Instalación y configuración de Ubuntu (Ubuntu standalone, compartido con Win-

dows, Live Boot)o Requerimientos mínimos de hardwareo Particiones primarias, extendidas, swap y sistema de archivos ( Estándar de

Estructura de FS (organización de las carpetas más importantes y su conteni-do)

115

INFORMÁTICA

o Sistema de arranque (GRUB)o Pasos para la instalación del Ubuntu (software center)o Task Manager (listar procesos, matar procesos)- Herramientas de Gestión GNU-Linux

•El escritorio de Ubuntu•Contenido y Uso del menú•Personalización•Configuración de la barra de menú•Acceso a carpetas•Uso de application launcher •Gestión de documentos y archivos

o Explorador de archivoso Manejo de archivoso Gestión de permisos

•Gestión de las actualizaciones•Gestión de la red (red física, red inalámbrica)•Gestión de dispositivos externos

- Herramientas de trabajo libres•Herramientas de Ofimática•Gestionar documentos de texto (Writer)

o Gestión de la páginao Formatos y Estiloso Manejo de Imágenes y Tablaso Generación de tablas de contenidoo Ortografía y gramática

•Gestionar hojas de cálculo (Calc)o Gestión de las celdaso Formato de las celdaso Creación y uso de fórmulaso Generar gráficos

•Crear presentaciones (Impress)o Gestionar diapositivaso Formatos de textoo Manejo de Imágenes, Audio, Video y Tablaso Generar diagramaso Animar diapositivas

•Firefox, como navegador de Internet•Gestión de Thunderbird como cliente de correo electrónico•VLC Media Player, como gestor de música•Shotwell, como herramienta de gestión de fotos

11.2 NIVEL 1 11.2.1 Contenido mínimo de la Segunda etapa

- Documentación de la aplicación•Título.•Edad del público al que está orientado.•Objetivos específicos que persigue la aplicación.•Historia, como narrativa relacionada a la aplicación interactiva que se desarrolla-

rá. Se debe describir los caracteres (personajes), el mundo, y las actividades o interacciones que realizan los caracteres en el mundo creado. Debe considerar

116

6ta Olimpiada Científica Estudiantil Plurinacional Boliviana

que en el diseño de esta clase de aplicaciones sólo uno de los tres (caracteres-mundo-interacciones) debe ser elegido como el elemento más sobrenatural (bi-zarro, extraño).

•Descripción de los caracteres en cuanto a su apariencia, comportamiento, habilida-des y relaciones entre caracteres. Describir sus funciones en la aplicación.

•Tecnologías que usará para su desarrollo y tecnologías requeridas para su ejecu-ción. (se valorará tecnologías multiplataforma y de carácter abierto para su desa-rrollo así como ejecución)

- Implementación básica de la aplicación•Crear el entorno de la aplicación con el uso de las tecnologías planteadas.•Agregar los actores y la programación de sus funciones básicas.•Relacionar la aplicación con la documentación propuesta.

11.2.2 Tercera etapa y Cuarta etapa- Defensa de la aplicación

•Animación•Enfoque de cámara•Interacción de elementos•Construcción de secuencias•Tarea sorpresa por equipo•Detallar las etapas y escenarios que contendrá la aplicación (nombre o título de

etapa, breve resumen de la historia, desarrollo de la historia (trama), caracteres y habilidades que presentan, música y efectos).

•Definición y descripción de controles para la aplicación interactiva. Para la cuarta etapa, los estudiantes deberán realizar las mejoras que su Comité

Académico Departamental les sugiera, en base a los criterios de la evaluación de la etapa final.

Software recomendado y versiones

Se recomienda el uso de lenguajes de programación visuales de licencia libre, que permitan el desarrollo de las aplicaciones para plataformas (linux y windows).

La aplicación de controles es libre (es decir uso de dispositivos externos distintos al teclado), sin embargo se recomienda y será favorable el uso de controles de fácil acceso (tanto eco-nómicos como de disponibilidad local)

Recomendaciones

La aplicación debe orientar y fortalecer un pensamiento positivo de las personas a las que está dirigido en cuanto a:

• Promoverlapaz(unaactitudpacifistaydenoviolencia)[Losjuegosde“shooting”porlogeneral promueven la violencia ]

• Promoveraspectosmoralesyéticosinherentesalserhumano(beneficencia,justicia,auto-nomía, entre otros). Todos estos aspectos derivan del respeto a la dignidad del ser humano.

• Promoverlosaspectospositivosdelaculturaboliviana(valoresdelacosmovisiónandina-amazónica).

• Promoverelrespetoporlanaturaleza.

• Promoverelusodeproducciónnacionalencuantoanarrativa,música,videosyotroscon

117

INFORMÁTICA

licencias libres de re-uso y adaptación.

Estas recomendaciones se valorarán de forma positiva y tendrán influencia en la puntua-ción de las aplicaciones presentadas.

11.3 NIVEL 2 11.3.1 Segunda y tercera etapa: Deberán programar sus soluciones en lenguaje C/

C++ utilizando CodeBlocks

- Resolución de problemas•Problemas lógicos•Aritmética•Álgebra

- Implementación de algoritmos en C/C++- Estructuras de programación fundamentales- Sintaxis básica y semántica del lenguaje C/C++- Variables, tipos de datos, expresiones y asignaciones- Entrada y salida de datos simple- Estructuras de control condicionales e iterativas- Implementación de funciones y paso de parámetros - Trabajar con números primos y descomposición de números- Series- Lotes

11.3.2 Cuarta Etapa (Final nacional):

- Cadenas- Vectores- Matrices- Conocimiento de la estrategia “divide y vence”, ejemplo: búsqueda binaria

La delegación departamental se conformará con los estudiantes clasificados de la etapa 3 y un tutor departamental por nivel. El tutor será designado por los coordinadores departamentales del Comité Académico- Científico de Informática.

11.4 NIVEL 3

11.4.1 Segunda y Tercera Etapa: Deberán programar sus soluciones en lenguaje C/C++ utilizando CodeBlocks

- Estructuras de programación fundamentales.- Sintaxis básica y semántica del lenguaje C/C++- Variables, tipos de datos, expresiones y asignaciones- Entrada y salida de datos simple- Estructuras de control condicionales e iterativas- Funciones y paso de parámetros- Vectores- Matrices- Series- Lotes- Cadenas- Solución problemas de tipo competencia- Problemas lógicos teoría de números. Manejo de cadenas- Métodos de ordenación.

118

6ta Olimpiada Científica Estudiantil Plurinacional Boliviana

- Combinatoria- Teoría de grafos

11.4.2 Cuarta Etapa (Final nacional):

- Geometría básica (punto, vector, línea, ángulo, distancia).- Estrategias de resolución de problemas (Divide y vencerás, Algoritmos voraces, Pro-

gramación Dinámica).

El Comité Nacional de la Olimpiada se reserva el derecho de modificar, reordenar o actualizar este listado de temas. Cualquier modificación deberá ser publicada en la página web: http://olimpiada.icpc-bolivia.edu.bo/ con la debida anticipación para evitar algún perjuicio.

10. INFORMACIÓN

Para mayor información se pueden contactar a los miembros del Comité Académico Cien-tífico en horarios de oficina, ó realizar sus consultas vía correo electrónico.

COMITÉ ACADÉMICO CIENTÍFICO NACIONAL DE LA 6ta OCEPB – ÁREA INFORMÁTICA

Jorge Humberto Terán PomierUniversidad Mayor de San Andrésjteran@gmail.com

Jhonny Roberto Felipez AndradeUniversidad Mayor de San Andrés

COMITÉ ACADÉMICO CIENTÍFICO DEPARTAMENTAL DE INFORMÁTICA

ChuquisacaLuis Antonio Molina YampaUniversidad Mayor Real y Pontificia San Francisco Xavier de Chuquisacaantoniomolina.yampa@gmail.com

José Enrique IglesiasUniversidad Mayor Real y Pontificia San Francisco Xavier de Chuquisaca

CochabambaLeticia Blanco Coca Universidad Mayor de San SimónCel.: 70719996leticia.blanco@gmail.com

La PazJhonny Roberto Felipez AndradeUniversidad Mayor de San Andrés

119

INFORMÁTICA

OruroJuan Gregorio Choque UñoUniversidad Técnica de OruroCel.: 70434657

Dennis Martínez CrovoUniversidad Técnica de Orurodmartinez@uto.edu.boCel.: 72471751

PotosíLeticia Gómez ValdaUniversidad Autónoma Tomás FríasCel.: 70464017

PandoJavier Patty MagneUniversidad Amazónica de PandoCel.: 72926559javierpattymagne@gmail.com

Samuel Fuentes ChambiUniversidad Amazónica de PandoCel.: 72930483fuesam@hotmail.com

Santa CruzEvans Balcázar VeizagaUniversidad Autónoma Gabriel René MorenoCel.: 72107856evansbv@gmail.com

Leonardo Vargas PeñaUniversidad Autónoma Gabriel René Moreno

TarijaOctavio Aguilar MalleaUniversidad Autónoma Juan Misael Saracho

Marcelo Cespedes MachicaoUniversidad Autónoma Juan Misael Saracho

Estudiante de Informát ca en la f nal d

e la 5

ta OCEPB

- Su

cre

MATERIAL DE APOYO

Estudiante de Informát ca en la f nal d

e la 5

ta OCEPB

- Su

cre

122

4

Bloqueos en la Ciudad

En una ciudad bien organizada, donde las calles han sido organizadas en uncuadrado perfecto de NxN calles, la gente se ha vuelto loca y ha comenzadoa bloquear las calles. Aparentemente no hay razon para los bloqueos.

Los bloqueos se dan en las esquinas de las calles. En la ciudad las calles senominan con numeros. Las verticales se nominan desde 0 (se comienza masa la izquierda) y en horizontales desde 0 (se comienza desde arriba).

Lamentablemente el representante de la Organizacion de Ciudadanos Ejem-plares, Prudentes y Bondadosos (OCEPB) debe trasladarse desde su casa enla esquina (X0,Y0) a la sede de la OCEPB en (Xf,Yf) donde se reunira conun hombre que dice tener la solucion al problema de la locura de la gente,este senor trabaja para la Organizacion de Buenos Individuos (OBI).

Ayuda al representante de la OCEPB a saber el camino para llegar a sudestino conociendo el mapa actual de la ciudad y sus bloqueos. En caso deque pueda llegar debes indicar que HAY RUTA POSIBLE. Si fuera imposiblellegar debes indicarle que NO HAY RUTA POSIBLE.

En caso de que la esquina de destino o la esquina de origen este bloqueadadebe indicar NO HAY RUTA POSIBLE.

Entrada

Se tienen varios casos de prueba, cada caso de prueba consiste de variaslıneas.

29

30

Primera lınea N, Numero de calles verticales y horizontales con 2 ≤ N ≤ 100

Segunda lınea: X0 y0 Xf Yf

(X0,Y0) es el punto origen del representante de la OCEPB, y (Xf,Yf) es sudestino.

Siguen N lıneas con N caracteres representando la posibilidad de bloqueos enla ciudad. B significa Bloqueado y L Libre

Los casos de prueba terminan cuando N es 0.

Salida

Una lınea con dos posibles mensajes: HAY RUTA POSIBLE, o NO HAY RUTA

POSIBLE

Ejemplos de entrada

5

0 1 1 4

BLBLB

LLLLL

BBBLL

LBLBB

BBLLB

0

Respuestas para el ejemplo

HAY RUTA POSIBLE

123

31

Bloqueo

Solucion por recursividad

Analizando el problema vemos que existen cuatro lugares a donde se puedemover. Si en algun momento se encuentra en la posicion Pi, j puede moversea las posiciones Pi+ 1, j, Pi− 1, j, Pi, j − 1, Pi, j + 1 tal como se muestraen la figura 4.1

Pi,j

Pi+1,j

Pi−1,j

Pi,j−1 Pi,j+1

Figura 4.1: Lugares donde se puede mover de la posicion Pi, j

Representando las posiciones arriba, abajo, izquierda y derecha. Con esto enmente escribimos un programa recursivo que visite estas posiciones solo cuan-do no esten bloqueadas. Para terminar la recursion nos fijamos si llegamos ala salida deseada.

Esta solucion no garantiza que no se entre en un ciclo infinito. Podemosllegar a una dos veces a una misma posicion, por ejemplo desde arriba porun camino y por abajo por otro. Para evitar que esto se convierta en un ciclocreamos una matriz para marcar loas posiciones visitadas si llegamos a unaposicion visitada terminamos esa recursion continuando con otra posiciones.

Un algoritmo que puede recorrer todos los elementos como se ve en el algo-ritmo 11.

En este algoritmo hemos creado dos arreglos uno denominado ciudad quees el que nos dan en la entrada y otro que denominamos visitados paraanotar todos los lugares ya examinados. Esto elimina los bucles y el procesorepetido. En el algoritmo 11 no hemos controlado los extremos. Esto significaque cuando llegamos a un extremo derecho no existe la columna siguiente,por lo que se produce un error. Para evitar estar controlando estos puntos enlos que nos salimos del espacio definido, es conveniente agregar un contorno

30

Primera lınea N, Numero de calles verticales y horizontales con 2 ≤ N ≤ 100

Segunda lınea: X0 y0 Xf Yf

(X0,Y0) es el punto origen del representante de la OCEPB, y (Xf,Yf) es sudestino.

Siguen N lıneas con N caracteres representando la posibilidad de bloqueos enla ciudad. B significa Bloqueado y L Libre

Los casos de prueba terminan cuando N es 0.

Salida

Una lınea con dos posibles mensajes: HAY RUTA POSIBLE, o NO HAY RUTA

POSIBLE

Ejemplos de entrada

5

0 1 1 4

BLBLB

LLLLL

BBBLL

LBLBB

BBLLB

0

Respuestas para el ejemplo

HAY RUTA POSIBLE

124

31

Bloqueo

Solucion por recursividad

Analizando el problema vemos que existen cuatro lugares a donde se puedemover. Si en algun momento se encuentra en la posicion Pi, j puede moversea las posiciones Pi+ 1, j, Pi− 1, j, Pi, j − 1, Pi, j + 1 tal como se muestraen la figura 4.1

Pi,j

Pi+1,j

Pi−1,j

Pi,j−1 Pi,j+1

Figura 4.1: Lugares donde se puede mover de la posicion Pi, j

Representando las posiciones arriba, abajo, izquierda y derecha. Con esto enmente escribimos un programa recursivo que visite estas posiciones solo cuan-do no esten bloqueadas. Para terminar la recursion nos fijamos si llegamos ala salida deseada.

Esta solucion no garantiza que no se entre en un ciclo infinito. Podemosllegar a una dos veces a una misma posicion, por ejemplo desde arriba porun camino y por abajo por otro. Para evitar que esto se convierta en un ciclocreamos una matriz para marcar loas posiciones visitadas si llegamos a unaposicion visitada terminamos esa recursion continuando con otra posiciones.

Un algoritmo que puede recorrer todos los elementos como se ve en el algo-ritmo 11.

En este algoritmo hemos creado dos arreglos uno denominado ciudad quees el que nos dan en la entrada y otro que denominamos visitados paraanotar todos los lugares ya examinados. Esto elimina los bucles y el procesorepetido. En el algoritmo 11 no hemos controlado los extremos. Esto significaque cuando llegamos a un extremo derecho no existe la columna siguiente,por lo que se produce un error. Para evitar estar controlando estos puntos enlos que nos salimos del espacio definido, es conveniente agregar un contorno32

Algoritmo 11: Recorrer la ciudad recursivamente

1 void Buscar(x,y)

2 if ((x igual salidax)&&(y igual saliday))3 return existe una salida;

4 if (visitadosx,y igual 1 )5 return // ya fue visitado ;

6 visitadosx,y=1;7 // verificar la fila de abajo ;8 if (ciudadx+1,y igual 0 )9 void Buscar(x+1,y);

10 // verificar fila de arriba ;11 if (ciudadx−1,y igual 0 )12 void Buscar(x-1,y);

13 // verificar la columna izquierda ;14 if (ciudadx,y−1 igual 0 )15 void Buscar(x,y-1);

16 // verificar la columna derecha ;17 if (ciudadx,y+1 igual 0 )18 void Buscar(x,y+1);

que evite este problema. En el ejemplo podemos agregar un contorno debloqueos como se muestra en la figura 4.2.

En el algoritmo 11, suponemos que se creo un contorno como el mostrado.

Solucion utilizando grafos

Para entender esta solucion pongamos el ejemplo que se muestra en el cuadro4.1 en una matriz de dos por dos:

Ahora numeremos los elementos de esta matriz secuencialmente como semuestra en el cuadro 4.2:

Con esto dicho podemos representar los posibles movimientos en un grafo,los numeros representaran los nodos, y la distancia para ir de un nodo aotro definimos como uno, porque solo deseamos encontrar una salida. En el

125

33

B

BB

BBBBBB

BB

BB

BBBBBB

BB

B B B B B B B B B BB

B B B B B B B B B B BB

Area original

Figura 4.2: Insertar un contorno

B L B L BL L L L LB B B L LL B L B BB B L L B

Cuadro 4.1: Ejemplo de bloqueo

ejemplo se comienza en la fila 0, columna 1. En nuestra nueva nomenclaturasera el nodo 1 y como se ve solo puede conectarse al nodo 6. La figura 4.3muestra este grafo.

Para representar un grafo en una computadora utilizamos un vector dondecada elemento es una lista enlazada. Las listas enlazadas se encuentran enlas librerıas de todos los lenguajes de programacion. El ejemplo puede repre-sentarse en un vector de las listas enlazadas. En la figura 4.4 se muestra un

0 1 2 3 45 6 7 8 910 11 12 13 1415 16 17 18 1920 21 22 23 24

Cuadro 4.2: Numeracion de las posiciones del ejemplo

32

Algoritmo 11: Recorrer la ciudad recursivamente

1 void Buscar(x,y)

2 if ((x igual salidax)&&(y igual saliday))3 return existe una salida;

4 if (visitadosx,y igual 1 )5 return // ya fue visitado ;

6 visitadosx,y=1;7 // verificar la fila de abajo ;8 if (ciudadx+1,y igual 0 )9 void Buscar(x+1,y);

10 // verificar fila de arriba ;11 if (ciudadx−1,y igual 0 )12 void Buscar(x-1,y);

13 // verificar la columna izquierda ;14 if (ciudadx,y−1 igual 0 )15 void Buscar(x,y-1);

16 // verificar la columna derecha ;17 if (ciudadx,y+1 igual 0 )18 void Buscar(x,y+1);

que evite este problema. En el ejemplo podemos agregar un contorno debloqueos como se muestra en la figura 4.2.

En el algoritmo 11, suponemos que se creo un contorno como el mostrado.

Solucion utilizando grafos

Para entender esta solucion pongamos el ejemplo que se muestra en el cuadro4.1 en una matriz de dos por dos:

Ahora numeremos los elementos de esta matriz secuencialmente como semuestra en el cuadro 4.2:

Con esto dicho podemos representar los posibles movimientos en un grafo,los numeros representaran los nodos, y la distancia para ir de un nodo aotro definimos como uno, porque solo deseamos encontrar una salida. En el

126

33

B

BB

BBBBBB

BB

BB

BBBBBB

BB

B B B B B B B B B BB

B B B B B B B B B B BB

Area original

Figura 4.2: Insertar un contorno

B L B L BL L L L LB B B L LL B L B BB B L L B

Cuadro 4.1: Ejemplo de bloqueo

ejemplo se comienza en la fila 0, columna 1. En nuestra nueva nomenclaturasera el nodo 1 y como se ve solo puede conectarse al nodo 6. La figura 4.3muestra este grafo.

Para representar un grafo en una computadora utilizamos un vector dondecada elemento es una lista enlazada. Las listas enlazadas se encuentran enlas librerıas de todos los lenguajes de programacion. El ejemplo puede repre-sentarse en un vector de las listas enlazadas. En la figura 4.4 se muestra un

0 1 2 3 45 6 7 8 910 11 12 13 1415 16 17 18 1920 21 22 23 24

Cuadro 4.2: Numeracion de las posiciones del ejemplo34

1

6 7 8 9

13 14

17

22

Figura 4.3: Grafo que representa el ejemplo

vector donde cada nodo es un elemento del vector y cada uno de esto apuntaa los lugares donde tiene conexion.

Para el recorrido de un grafo existen dos algoritmos Breadth-first search(BFS) y Depth-first search (DFS). Estos argoritmos para el recorrido de ungrafo tambien se denominan recorrido en anchura y en profundidad.

El recorrido en anchura recorre todos los nodos del grafo, como se muestraen el algoritmo 12. Para resolver el problema solo es necesario verificar si enel recorrido llegamos al punto de salida.

Algoritmo 12: Algoritmo Breadth-First-Search - BFS

1 BFS(x,y)

2 Crear una cola vacıa Q ;3 insertar el nodo inicial en Q ;4 while (Q no esta vacıa)5 sacar en U un elemento de la cola. ;6 ∀ ( nodo n adyacente a U )7 if (n no fue visitado)8 agregar n a la cola Q ;

Para este problema tambien podemos utilizar el algoritmos DFS, la diferencia

127

35

5

0

1

2

3

5

4

7

8

6

7

3

6

6

8 9

89

1

7 6 8

3 13

14

10

17

22

24

22

17

Figura 4.4: Listas enlazadas que representan el grafo36

con el la solucion anterior es que en lugar de utilizar una cola utilizamos unapila. El algoritmo 13 muestra esta implementacion.

Algoritmo 13: Algoritmo Depth-first search - DFS

1 DFS(x,y)

2 Crear una pila vacıa P ;3 insertar el nodo inicial en P ;4 while (P no esta vacıa)5 sacar en U un elemento de la pila. ;6 ∀ ( nodo n adyacente a U )7 if (n no fue visitado)8 agregar n a la pila P ;

El la complejidad en esta representacion es O(nodos+vertices). Esto se ve-rifica porque hay que recorrer todos los nodos y en cada nodo todos susenlaces.

Variantes al problema

Un problema adicional que se puede plantear es: ¿Cual es el camino mascorto para llegar al destino? Para resolver esto hay que revisar el algoritmosde Dijsktra.

Adicionalmente es posible pensar en cual sera el segundo camino mas corto.

34

1

6 7 8 9

13 14

17

22

Figura 4.3: Grafo que representa el ejemplo

vector donde cada nodo es un elemento del vector y cada uno de esto apuntaa los lugares donde tiene conexion.

Para el recorrido de un grafo existen dos algoritmos Breadth-first search(BFS) y Depth-first search (DFS). Estos argoritmos para el recorrido de ungrafo tambien se denominan recorrido en anchura y en profundidad.

El recorrido en anchura recorre todos los nodos del grafo, como se muestraen el algoritmo 12. Para resolver el problema solo es necesario verificar si enel recorrido llegamos al punto de salida.

Algoritmo 12: Algoritmo Breadth-First-Search - BFS

1 BFS(x,y)

2 Crear una cola vacıa Q ;3 insertar el nodo inicial en Q ;4 while (Q no esta vacıa)5 sacar en U un elemento de la cola. ;6 ∀ ( nodo n adyacente a U )7 if (n no fue visitado)8 agregar n a la cola Q ;

Para este problema tambien podemos utilizar el algoritmos DFS, la diferencia

128

36

con el la solucion anterior es que en lugar de utilizar una cola utilizamos unapila. El algoritmo 13 muestra esta implementacion.

Algoritmo 13: Algoritmo Depth-first search - DFS

1 DFS(x,y)

2 Crear una pila vacıa P ;3 insertar el nodo inicial en P ;4 while (P no esta vacıa)5 sacar en U un elemento de la pila. ;6 ∀ ( nodo n adyacente a U )7 if (n no fue visitado)8 agregar n a la pila P ;

El la complejidad en esta representacion es O(nodos+vertices). Esto se ve-rifica porque hay que recorrer todos los nodos y en cada nodo todos susenlaces.

Variantes al problema

Un problema adicional que se puede plantear es: ¿Cual es el camino mascorto para llegar al destino? Para resolver esto hay que revisar el algoritmosde Dijsktra.

Adicionalmente es posible pensar en cual sera el segundo camino mas corto.