1 Presentaci´o Ha arribat el dia en que s’ha de fiscalitzar la feina de la Gencat i,…
- User
1 Presentaci´o Ha arribat el dia en qu
e s’ha de fiscalitzar la feina de la Gencat i, entre d’altres, es realitzara una auditoria dels comptes d’acord amb els pressupostos. La nostra empresa, Empresa d’Auditories S.L. (EdA SL, en curt), ha rebut l’encarrec de fiscalitzar els comptes i la gerent de l’empresa ens ha demanat al servei informatic crear un programa per dimensionar l’equip d’auditors que participara en aquesta feina. L’objectiu ´es auditar totes les partides (Aplicacions) del pressupost d’un any donat amb un equip d’auditors adequat. Aix´ı, haurem d’assignar cada aplicaci´o pressupostaria a un auditor, pero aquesta assignaci´o no ´es trivial si es vol fer de la millor manera possible d’acord amb els criteris establerts. Per simplificar la feina als auditors, voldrem tenir la capacitat d’assignar nom´es aplicacions d’un mateix tipus a cada auditor, o d’un mateix cap´ıtol. A m´es, la gerent d’EdA SL ens indica que, per reduir costos, voldria poder trobar l’equip m´es petit possible pero sense sobresaturar cap dels nostres companys auditors. Es ´ a dir, en aquest cas buscar´ıem l’assignaci´o que necessiti el menor nombre d’auditors pero, donades dues solucions amb el mateix nombre, triar´ıem l’assignaci´o d’aplicacions que m´es b´e (balancejat) reparteix l’import total als auditors. 1.1 Dades d’entrada Tornarem a tractar amb el mateix tipus de dades sobre els pressupostos de la Gencat que d´ona el CTTI i que s’han fet servir abans en exercicis i practiques de l’assignatura. 1.2 Resum dels requeriments Si recopilem el m´es rellevant del que s’ha explicat abans: • Hem d’auditar totes les partides (aplicacions) del pressupost d’un any donat • Les aplicacions es repartiran entre auditors • A cada auditor se li poden assignar aplicacions per un import maxim donat. Tots els auditors tenen el mateix l´ımit. • Es pot demanar que cada auditor fiscalitzi nom´es (restriccions) aplicacions d’un mateix tipus (I/D) o d’un mateix cap´ıtol. • Es poden fer servir, en principi, tants auditors com calgui, pero... – es pot indicar el nombre d’auditors maxim a utilitzar, – o es pot demanar buscar la soluci´o amb el m´ınim nombre d’auditors. En aquest cas, entre dues solucions amb el mateix nombre, es prioritzara aquella que tingui l’import total m´es ben repartit entre auditors, ´es a dir, la que tingui la menor desviaci´o estandard (veure Equaci´o 1) de l’import assignat als auditors. σ = vuut 1 n Xn i=1 (pi − p) 2 F´ormula de la desviaci´o estandard σ, on n ´es el nombre d’auditors, pi ´es l’import agregat de les aplicacions assignades a l’i-esim auditor, i p ´es l’import mitja assignat als auditors. - Assistant
Sembla que estàs explicant una tasca d'algorismia i programació que involucra crear un programa per assignar partides pressupostàries a un equip d'auditors segons certes restriccions i criteris d'optimització. Usen les dades dels pressupostos de la Generalitat de Catalunya proporcionats pel CTTI. A continuació, et faig un resum més estructurat de la tasca a realitzar:
Resum del Problema:
Objectiu:
Auditar totes les partides (Aplicacions) del pressupost d'un any determinat amb l'equip més petit d'auditors possible, sense sobrepassar un límit màxim d'import assignat per auditor, i amb la restricció que cada auditor només pot revisar aplicacions del mateix tipus o capítol.
Dades Entrada:
- Llista de partides pressupostàries del pressupost d'un any determinat proporcionades pel CTTI.
- Límit màxim d'import que es pot assignar a cada auditor.
- Opcional: nombre màxim d'auditors que es poden utilitzar.
Requeriments:
-
Auditar totes les partides pressupostàries (aplicacions).
-
Repartir les aplicacions entre els auditors respectant el límit màxim d'import per auditor.
-
Opcionalment, assignar només aplicacions d’un mateix tipus (I/D) o d’un mateix capítol a cada auditor.
-
Trobar l'equip més petit d'auditors necessari, o dins d'un límit màxim especificat d'auditors.
-
Si hi ha múltiples solucions amb el mateix nombre d'auditors, prioritzar la que tingui l'import total més ben repartit (menor desviació estàndard σ de l'import assignat als auditors). La fórmula per calcular la desviació estàndard σ és la següent:
[ \sigma = \sqrt{\frac{1}{n} \sum_{i=1}^{n} (p_i - \bar{p})^2} ]
on:
- ( n ) és el nombre d'auditors.
- ( p_i ) és l'import agregat de les aplicacions assignades a l'audit i-ès.
- ( \bar{p} ) és l'import mitjana assignada als auditors.
Possibles Passos per Solucionar el Problema:
-
Analitzar les dades pressupostàries i les restriccions (tipo d'aplicació, capítols).
-
Establir un mètode per dividir les partides entre els auditors (per exemple, podria ser útil un algorisme de bin packing o de programació lineal).
-
Implementar un algorisme que assigni les partides als auditors, tot seguint les restriccions i optimitzant per la mínima quantitat d'auditors i/o la repartició més equitativa de l'import.
-
Calcular la desviació estàndard de l'import repartit entre els auditors per cada solució potencial.
-
Trobar la millor solució segons els criteris establerts.
-
Proveir la llista final d'assignments d'auditors, juntament amb el detall del pressupost que revisaran.
Podràs necessitar el coneixement d'algorismes de dividing & conquering, optimització i estadística per desenvolupar aquest programa eficientment. Si teniu un requisit de maximizar el rendiment o el code és molt complex, potser hauries de considerar l'ús de tècniques més avançades com heurístiques o algoritmes genètics.
- User
2 Feina a fer
- Fent servir backtracking, trobar una assignaci´o d’aplicacions a auditors que no superi el nombre
m
axim donat (si s’indica) i que compleixi les restriccions establertes. Si no ´es possible trobar una assignaci´o amb aquestes condicions, s’informara que no hi ha soluci´o. - Fent servir backtracking, trobar la millor assignaci´o d’aplicacions a auditors complint les restriccions donades, ´es a dir, la que minimitza el nombre d’auditors, primer, i la desviaci´o est
andard de l’assignaci´o d’imports en segon lloc. Igualment, si no ´es possible trobar una assignaci´o amb aquestes condicions, s’informara que no hi ha soluci´o. 2.1 Instruccions • Cal codificar el backtracking utilitzant les classes vistes a teoria: Solucionador, Solucio i Candidats. • Les dades es llegiran d’un fitxer de tipus text que contindra les dades de pressupostos que ja coneixeu fent servir les funcions d’eines.h. • Ens quedarem amb les l´ınies del pressupost de l’any indicat per l’usuari amb un import consolidat m´es gran que 0. Recordeu que pot haver-hi m´es d’una l´ınia (o import) associada a la mateixa aplicaci´o. Nom´es cal guardar la informaci´o associada a l’aplicaci´o. • Un cop calculada la soluci´o, aquesta es mostrara per la sortida estandard en un format lliure, pero similar al que es mostra m´es endavant en aquest document. En tot cas, ha de mostrar l’assignaci´o de cada auditor (les aplicacions que auditara ordenades per codi), l’import agregat de les aplicacions assignades a cada auditor, el nombre total d’auditors, la desviaci´o estandard dels imports assignats als auditors, i el temps que ha trigat a trobar la soluci´o. • Si es creu oport´u, es poden preprocessar les dades abans d’iniciar el backtracking per obtenir estructures que ens puguin ser ´utils per podar branques de l’arbre de possibilitats. Aquest preprocessament s’incloura en el calcul del temps de comput de l’algorisme. • En una execuci´o normal, cal indicar obligatoriament si es busca una o la millor soluci´o, l’any a auditar, l’import maxim que pot assumir un auditor, i el nom del fitxer de dades. El nombre maxim d’auditors ´es un parametre opcional (si no s’indica, s´on il·limitats), al igual que les restriccions per tipus I/D i cap´ıtol. Per saber com indicar aquests parametres, es pot consultar l’ajuda del programa (veure exemple m´es avall). • Per fer les proves, cal comen¸car amb poques l´ınies amb imports ben dimensionats (pel que fa al maxim que se li podra assignar a un auditor), i anar-ho incrementant de mica en mica (el temps d’execuci´o es disparara!). • El programa principal s’ha d’anomenar audita i ha de funcionar a trav´es de l’interpret de comandes tal com es descriu a continuaci´o: – Si es crida sense parametres, ha d’emetre un missatge indicant com demanar ajuda. 1 $ ./audita 2 Falten arguments ("./audita --help" per ajuda) – Si es demana ajuda, ha de descriure el seu funcionament. 1 $ ./audita --help 2 Utilitzaci´o: ./audita opcio fitxer 3 4 opcio pot ser: 5 -h, --help mostra aquest missatge d'ajuda i surt 6 -u cerca una soluci´o qualsevol que compleixi les EDA Practica 2: Algor´ısmica, curs 2023/24 GDDV/GEINF 3 7 restriccions del problema 8 -m cerca la soluci´o que minimitza el nombre d'auditors 9 i el repartimentoptim d'aplicacions 10 -t indica que nom´es es poden assignar aplicacions del 11 mateix tipus (ingr´es/despesa) a un auditor 12 -c indica que nom´es es poden assignar aplicacions del 13 mateix cap´ıtol a un auditor 14 -a <any> indica que s'ha de fer l'assignaci´o per a 15 l'exercici pressupostari <any> 16 -i <imp> assigna <imp> com a import maxim que un 17 ´unic auditor pot fiscalitzar 18 -n assigna com a nombre maxim d'auditors 19 20 fitxer ha de ser un fitxer de text amb totes les l´ınies 21 dels pressupostos amb el format del CTTI. 22 – El programa s’ha d’aturar i mostrar un missatge d’error amb el primer problema detectat amb l’entrada de parametres (si falta un parametre o ´es incorrecte). Per exemple: 1 $ ./audita -j 2 Opci´o desconeguda: -j 1 $ ./audita fitxer.txt 2 Cal indicar si es busca una soluci´o o la millor 1 $ ./audita -u 2 Falta el nom del fitxer 1 $ ./audita -u fitxer.csv 2 Cal indicar un valor correcte per l'any a auditar 1 $ ./audita -a fitxer.csv 2 Falta el valor associat a l'opci´o: -a 1 $ ./audita -i 0 -a 2021 -u fitxer.csv 2 Cal indicar un valor correcte per l'import maxim per auditor – Si el fitxer no s’ha pogut obrir, s’ha d’avisar. 1 ./audita -u -a 2020 -i 200 linies_0002.csv 2 3 32 l´ınies (28 aplicacions) llegides amb un import total de: 15406545.67 € 4 ...
- Fent servir backtracking, trobar una assignaci´o d’aplicacions a auditors que no superi el nombre
m
- Assistant
Sembla que ens estàs proporcionant instruccions per a la implementació d'un programa d'auditoria utilitzant backtracking. Aquí tens un resum sobre com procedir:
Feina a Fer:
1. Utilitzar el Backtracking per Assignar Aplicacions:
- Trobar una assignació d'aplicacions a auditors respectant un límit màxim d'auditors (si s’especifica) i seguint les restriccions.
- Informar quan no es pot trobar una solució sota les condicions donades.
2. Trobar la Millor Assignació Amb Backtracking:
- L'objectiu és minimitzar el nombre d'auditors.
- Prioritzar solucions amb menys desviació estàndard dels imports assignats als auditors.
- Informar quan no es pot trobar una solució sota aquestes condicions.
Instruccions per a la Implementació:
- Utilitzar les classes
Solucionador,Solucio, iCandidatsper codificar el backtracking. - Llegir dades d'un fitxer de text amb la informació pressupostària usant les funcions de
eines.h. - Filtrar les línies de pressupost de l'any desitjat i amb import consolidat major que zero.
- Només guardar la informació associada a l'aplicació.
- Mostrar la solució per sortida estàndard amb l'assignació per a cada auditor, l’import assignat total, el nombre d’auditors, la desviació estàndard dels imports i el temps de càlcul.
- Preprocessar les dades si és necessari per optimitzar la cerca amb el backtracking.
- El programa principal ha de ser
auditai ha de seguir la interfície de línia de comandes descrita. - Gestionar correctament els errors d'entrada i problemes amb l'obertura del fitxer.
Consideracions Especials:
El backtracking és una estratègia d'algorismia que pot ser molt costosa en temps de càlcul, especialment en problemes amb un gran nombre de possibilitats. Per tant:
- Comença amb conjunts de dades petits per assegurar que el teu algorisme funciona adequadament.
- Optimitza el procés de cerca podant branques de l’arbre de cerca quan sigui clar que no porten a una solució vàlida o òptima.
- Prova incrementar gradualment la mida del conjunt de dades per entendre el comportament del programa en situacions més realistes (però estigues preparat per temps d'execució significativament més llargs).
Això et donarà una base sòlida per començar la implementació del programa d'auditoria amb backtracking. Recordeu sempre fer proves extensives per validar la correcció del programa, especialment en casos complexos o límits.
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.