Gwybodaeth Modiwlau
Manylion y cyrsiau
Math o Ddysgu | Manylion / Hyd Dysgu |
---|---|
Darlith | 22 x Darlithoedd 1 Awr |
Tiwtorial | 4 x Tiwtorial 1 Awr |
Dulliau Asesu
Math o Assessiad | Manylion / Hyd Assessiad | Cyfran |
---|---|---|
Arholiad Ailsefyll | 2 Awr (Arholiad Ysgrifenedig) | 100% |
Arholiad Semester | 2 Awr (Arholiad Ysgrifenedig) | 100% |
Canlyniadau Dysgu
Wedi cwblhau'r modiwl dylai'r myfyrwyr:
1. ymchwilio priodweddau elfennol graffiau;
2. perfformio lluniadau graff syml;
3. cynrychioli graffiau haniaethol fel diagramau;
4. penderfynu os yw graff yn bodloni amryw o feini prawf;
5. cymhwyso algorithmau ar gyfer darganfod cydrannau;
6. disgrifio algorithmau Dijkstra a Floyd, a’u cymhwyso mewn achosion syml;
7. cymhwyso dadansoddiad llwybr critigol i brosiectau syml;
8. cymhwyso naill ai algorithm Prim neu Kruskal ar gyfer darganfod coed rhychwantol pwys optimwm;
9. cymhwyso algorithm Ford-Fulkerson i rwydwaith cludiant i ddarganfod llif macsimwm.
Disgrifiad cryno
Datblygwyd damcaniaeth graff trwy ymchwilio nifer o broblemau clasurol – Problem Pontydd Konigsberg Euler, Problem Rhwydwaith Trydanol Kirchoff, Rhifiad Cayley o Graffiau Cemegol a’r Broblem Pedwar Lliw ar gyfer Mapiau Plân. Darganfyddir datrysiad llawn i Broblem Euler ac astudir problem Hamilton perthynol. Rhoddir algorithmau llwybr byrraf a hiraf gyda chymwysiadau, er enghraifft, i amserlennu gorchwyl (PERT). Disgrifir algorithmau i ddarganfod coed rhychwantol pwys optimwm mewn graffiau pwysol. Gellir eu defnyddio, er enghraifft, i ddarganfod rhwydweithiau cludiant cysylltiedig cost leiaf. Amlinellir y damcaniaethau o lifoedd mewn rhwydweithiau cludiant, yn arbennig theorem y toriad-lleiaf-llif-mwyaf. Mae yna gymwysiadau i lifoedd cludiant a damcaniaeth cydweddu.
Nod
I gyflwyno rhai testunau mewn damcaniaeth graff clasurol. I ddisgrifio algorithmau rhwydwaith fel y rhai i ddarganfod llwybrau o hyd optimaidd, coed rhychwantol pwysau optimwm a llifoedd macsimwm, ac i’w egluro trwy gymwysiadau i achosion syml.
Cynnwys
2. Llwybrau a chydrannau mewn graff. Algorithm i bennu cydrannau. Algorithmau llwybrau byrraf (Dijkstra) a hiraf. Algorithm Floyd.
3. Trefniad topolegol. Dadansoddiad Llwybr Critigol.
4. Coed rhychwantol. Algorithmau Prim a Kruskal i ddarganfod coed rhychwantol pwysau optimwm.
5. Rhwydweithiau cludiant. Llifoedd, toriadau. Theorem y toriad-lleiaf-llif-mwyaf. Algorithm Ford-Fulkerson.
6. Cymwysiadau.
Nodau
Mae'r modiwl hwn yn cydymffurfio a FfCChC Lefel 6