АСП1/К3 Јул 2021
< АСП1
Пређи на навигацију
Пређи на претрагу
- Овај рок није решен. Помозите СИ Wики тако што ћете га решити.
Јул 2021. године
1. задатак
Поставка
Посматра се план за реализацију једног софтверског пројекта дат табелом. Фаза С је почетна.
А |
С - 7 дана |
|---|---|
Б |
Г - 6 дана, Р-2 дана |
Ф |
L - 11 дана |
L |
С – 7 дана |
Г |
L – 3 дана, А – 4 дана |
M |
Ф – 5 дана, Б – 3 дана |
Р |
А – 5 дана |
Т |
Б – 7 дана, M – 2 дана |
- (5п) Представити пројекат графом.
- (10п) Ако фаза Б представља бета фазу пројекта и желимо да знамо да ни она неће каснити наћи критични пут (или путеве) и критичне активности за бета фазу.
- (10п) Наћи критични пут (или путеве) за успешну реализацију овог пројекта као и критичне активности.
Решење
2. задатак
Поставка
Дата је мрежа путева између градова представљена матричном репрезентацијом графа. Путарина између било која два повезана града износи 1. Међутим при уласку у сваки град, постоји одређена такса коју је потребно платити. Цена таксе се дефинише на нивоу града.
- Мика воли да путује и налази се у граду X. Израчунати за сваки град колико је новца Мики потребно да га обиђе уколико увек креће из места X. Имплементирати функцију која ефикасно рачуна минималну потребну количину новца за посету сваком граду. Функцији су прослеђени број градова, граф, цене такси за сваки град (низ природних бројева) и индекс почетног града. ЦАЛЦ ЕXПЕНСЕС(Н, Г, таxес, X)
- Један од градова је због недостатка туриста увео да туристи при уласку не плаћају таксу, већ да добију бенефицију у виду новца. Укратко прокоментарисати како ова модификација утиче на предложени алгоритам под а). Да ли би се у том случају користио исти алгоритам или би био погоднији неки други (ако да, који)?
Решење
3. задатак
Поставка
Упаривање неусмереног нетежинског графа.
- Предложити и укратко описати начин на који се врши проналажење максималног упареног скупа графа.
- За граф са слике приказати проналажење максималног упареног скупа по корацима.
Слика из трећег задатка.
Решење
4. задатак
Поставка
Обилазак по дубини
- Дефинисати стабло обиласка.
- Дефинисати почетно и завршно време приликом обиласка графа по дубини. Која је његова улога?
- Написати у псеудокоду имплементацију функције која на основу записаних почетних и завршних времена обиласка сваког чвора обиласком по дубини одређује да ли се чвор X налази у подстаблу чвора Y у стаблу обиласка.
ИС СУЦЦЕССОР(старт_тиме, финисх_тиме, x, y)