Loading
Note di Apprendimento
Study Reminders
Support
Text Version

Problemi Semplificati & Soluzioni

Set your study reminders

We will email you at these times to remind you to study.
  • Monday

    -

    7am

    +

    Tuesday

    -

    7am

    +

    Wednesday

    -

    7am

    +

    Thursday

    -

    7am

    +

    Friday

    -

    7am

    +

    Saturday

    -

    7am

    +

    Sunday

    -

    7am

    +

Salve lì, benvenuti nella seconda sessione della vostra prima settimana. Quello che faremo in questa sessione èper rivisitare il problema semplificato, rivedere nuovamente la soluzione e soprattutto per offrire argomenti sucorrettezza. Questo è ciò che vedremo soprattutto in questa sessione. Vedremo anche un'implementazioneparticolarmente basata su fogli di calcolo. Esamineremo le generalizzazioni del problema e discuteremole strutture dei dati e la trasformazione coinvolta.
(Riferimento Slide Time: 00.51)

Professore Sano ha discusso la versione semplificata di questo problema in cui sono stati considerati due e tre coinquilini. Ora generalizzeremo a un numero arbitrario di coinquilini. Noiutilizzeremo di seguito la notazione:• denunceremo il numero di coinquilini di NRoomMate.• KEvents denunceranno l'evento.• Ogni evento sarà denotato da un EventId.• Alcuni coinquilini saranno denotati da un RoomMateId.
(Riferimento Slide Time: 01.30)
A fine mese rappresenteremo un evento per righe e ogni coinquilino da una colonna.Perciò, alla fine del mese, avremo una serie di righe che denotano i vari eventi che hannocondiviso dai coinquilini. E lungo ogni colonna saranno le spese o i soldi che hacontribuito da un solo coinquilino per un determinato evento. Questo array a 2 dimensioni, o matrice, può essererappresentato come spese per un EventID da parte di un coinquilino J, qualunque sia la spesa.
(Riferimento Slide Time: 02.21)
Per ogni fila desideriamo condividere le spese tra tutti i coinquilini, cioè colonne. Questo puòessere fatto sottraendo la quota di testa per ogni coinquilino da ogni coinquilino lo stato attualedegli affari. I coinquilini con numeri negativi saranno quelli che dovranno pagare mentre icoinquilini con numeri positivi contro i loro nomi saranno quelli che riceveranno soldi.Alla fine del mese, aggiungiamo semplicemente le colonne. Ancora, quelli negativi dovranno pagaree quelli positivi riceveranno denaro.(Fare Slide Time: 03.09)
Vediamo la correttezza di questo approccio. Di seguito alcune domande le cui risposte avrebberoessere molto importanti per noi, dopotutto stiamo facendo una macchina fare queste cose, non un altro essere umano:• Cosa intendiamo davvero per correttezza?• Cos' è che vogliamo? Perché la sottrazione di per capo spese per ogni fiera di attivitàper tutti i coinquilini? Perché la fine del mese a colonna dei saggi totali è anche equa?• Come cambierà questa nozione di equità man mano che aggiungiamo la complessità al problema?Dopo tutto, stiamo valutando la versione semplificata del problema. Ma è una buona idea averequesto pensiero nella nostra mente come si aggiunge la nostra complessità, in quali altri modi può pensare
la correttezza ci è utile. Potrebbero esserci anche altre domande, ma per i nostri fini queste sono le domande chiaveper noi. Prendiamoli uno per uno.(Fare Slide Time: 04.20)
Che cosa richiediamo dall'idea di correttezza o dall'approccio fairness? Ebbene, tutti quelli checontribuiscono più della sua quota devono essere restituiti esattamente quel contributo in eccesso. Allo stesso modo,chiunque non abbia contribuito deve eventualmente pagare esattamente quello stesso importo, qualunque siadevo. Anzi, più fortemente, non più, né meno. Nessuno riceve più di quello che è la quota cheha diritto. E nessuno paga più di qualunque cosa sia richiesto a lei o a lei. Questa nozionedi equità – paghi solo quanto devi e ricevi solo quanto hai contribuito.
(Riferimento Slide Time: 05.24)
Vediamo attentamente come funziona in realtà questa idea di equità, dato il nostro approccio di soluzione.Supporre, ad esempio, iniziamo con il primo evento, in modo che non ci siano spese o pagamenti per esseresistemati o riconciliati. Supponiamo che un coinquilino paghi per un evento, qualche importo X. Poi dato checi sono NRoomMates in totale, il contributo per capo è X diviso per il numero dicoinquilini. Chiamiamola così per contributo di testa come P.� = �G.U.G.U.G.U.G.U.L.
Il nostro approccio dice che sottriamo a � da ogni coinquilino il contributo, che attualmente è 0,perché è il primo evento. Come � stato contribuito da quel coinquilino, e � � la sua quota.Perciò, l'importo di saldo per questo coinquilino che ha contribuito sarebbe � � − �. E dal momento cheè sottrazione di � dal 0 per gli altri coinquilini che non hanno contribuito, vedremo − �per ogni coinquilino che non ha contribuito alla didn t.
Questo è abbastanza coerente con la nostra idea che i coinquilini con numeri negativi contro di loro avrebbero dovuto pagare, e il coinquilino con numeri positivi contro di loro avrebbe dovuto farsi pagare. Si tratta di un'algebra sempliceper vedere che la somma di � − � del coinquilino contribuente, e il − � del restodei coinquilini è 0.
(Riferimento Slide Time: 07.21)
Guardiamo alla fine dei mesi totali. Perché la fine del mese è anche equa? La cifra saggia della colonnarappresenta un singolo compagno di stanza dei contributi, oppure per le azioni di testa dovute aaltri su tutti gli eventi in quel mese. L'aggiunta di tutti gli importi per una colonna dà l'importo netto cheil coinquilino deve pagare o ricevere. Se consideriamo la fine del mese totali per ogni coinquilino, e dato che l'importo da pagare sono negativi, e gli importi da ricevere sono positivi,allora è possibile utilizzare leggi come associatività o commutatività dei numeri per l'operazione di aggiunta,per dimostrare che le somme saggiate di colonna totale devono essere sempre 0.
(Riferimento Slide Time: 08.15)
Andiamo al passo successivo. Come cambierà questa equità con la complessità? Ricordiamo che abbiamo 2direzioni distinte in cui possiamo aggiungere complessità in questo problema:1. Uno è il problema stesso può essere reso ancora più generale. Perché dovremmo aspettare alla finedel mese per i totali? Perché dovremmo avere sempre dei totali per tutti? Forse io comecoinquilino potrebbe solo volere il mio totale per quel punto di tempo. Ci potrebbero essere molto piùcoinquilini di quello che abbiamo appena considerato, e tanti altri modi – abbiamo giàvisto tutto questo.
2. La seconda via sarebbe la generalizzazione della soluzione basata su computer. Vorremmopensare se il nostro approccio di soluzione rimarrà equo mentre aggiungiamo qualsiasi tipo di complessità.
(Riferimento Slide Time: 09.23)
Infatti, lo farà. L'argomento che la somma degli eccessi positivi e dei debiti negativi deve essere0 sarà sempre vero. Questo è il comportamento non mutevole o invariante di questo problema. Infatti, questo invariantegarantisce che la soluzione sia sempre equa e quindi corretta indipendentemente dalla complessitàaggiuntiva.(Fare Slide Time: 09.51)
Infine, guardiamo in quali altri modi può questo pensare alla correttezza aiutarci. Supponiamo che noiabbiamo milioni di coinquilini, sebbene sia abbastanza improbabile, questo invariante garantirà comunque la correttezzadella nostra soluzione. Infatti, può anche aiutarci a identificare alcuni errori di implementazione.Ad esempio, le nostre macchine sono tipicamente macchine di precisione finite. Pertanto possono verificarsi overflow e sotto i flussi. Se ci pensiamo un po ', allora qualsiasi errore di overflow o di underflow,rifletta immediatamente nel nostro invariante diventando nonzero, che dovrebbe essere il caso di essere il caso se vogliamoessere completamente equo. Il momento in cui vediamo che il nostro invariante è nonzero, sappiamo che qualcosa è andatosbagliato!Questo è un buon momento per fare una pausa. E pensate alle questioni che abbiamo appena discusso.(Fare Slide Time: 11.04)
dimostreremo la soluzione utilizzando un foglio di calcolo. Sulla figura riportata sopra, si vedrà slideche mostrano un'istantanea del foglio di calcolo di Libre Office 6,0. Abbiamo un EventID di colonna. Questosignifica sostanzialmente che ogni riga rappresenta un evento.
(Riferimento Slide Time: 11.31)
Abbiamo una colonna che cattura le spese per quell' evento.(Fare Slide Time: 11.36)
Abbiamo un mucchio di colonne per RoommateID.
(Riferimento Slide Time: 11.44)
Abbiamo mostrato qui 5 coinquilini, che sono F1, F2, F3, F4 e F5. In pratica,questi potrebbero essere alcuni nomi reali come Ramesh, Sudha, Nikhil ... etc.
(Riferimento Slide Time: 12.04)
Abbiamo anche illustrato che il coinquilino F1 ha pagato qualche importo per l'evento con EventID1.
(Riferimento Slide Time: 12.12)
La regione accerchiata nella figura riportata sopra denota i dati di input, cioè per un evento, comemolto è stato pagato da chi.(Fare Slide Time: 12.25)
La regione accerchiata nella figura riportata sopra denota i calcoli e i risultati di output. Questoè dove calcoliamo la quota equa di ogni coinquilino per ogni evento, e andiamo ad accumularela quota equa per tutti gli eventi.
(Riferimento Slide Time: 12.44)
Avviso l'ultima colonna che è l'invariante. Si tratta della somma di ogni riga della parte calcolata, cheè il contributo meno la quota di testa. Questa colonna deve essere sempre zero su ogni riga. Noiabbiamo già visto che si tratta di un argomento di correttezza. Così, nel foglio di calcolo, abbiamo appenasommato le righe e scriviamo che in questa particolare colonna. Se cioè 0 allora sappiamo che i nostricalcoli erano corretti.
(Riferimento Slide Time: 13.19)
Ecco anche una formula di calcolo per le persone che potrebbero non sapere di fogli di calcolo. Questa formulacalcola la somma dei contenuti delle celle a partire da colonna J e riga 13 (denotati da
�: 13) alla colonna N e alla riga 13 (denotati da �: 13). In questo particolare esempio abbiamo 55 −45 + 55 − 70 + 5 = 0. Pertanto, la nostra soluzione di fogli di calcolo è corretta. Si equilibra esattamentel'importo che deve essere dato e l'importo che deve essere ricevuto.(Fare Slide Time: 14.15)
Facciamo un'occhiata alla soluzione di lavoro effettiva.(Fare Slide Time: 14.21)
Ecco un foglio di calcolo Excel della stessa soluzione che abbiamo visto. Aggiungete un settimo evento. Facciamo chedichiari che si tratta di rupie 200. Questo significa che tra 5 amici, il contributo per capo è rupie40. Supponiamo che l'amico numero 1 paghi 20 rupie, paga tutto il 200 mentre altri no
pagare a tutti. Da notare che per l'amico 1 l'importo in eccesso è rupie 160. La sua quota di rupie 40è stata sottratta a partire dal 200 e quindi il 160 è l'importo in eccesso.Ovviamente, l'altro deve pagare rupie 40 ciascuno, ce ne sono 4. Pertanto, 160 rupiedevono assolutamente essere pagati dagli altri 4 e il nostro amico che ha contribuito deve ricevere 160 rupie.L'invariante è quindi 0.
(Riferimento Slide Time: 15.45)
Questo è di nuovo un buon punto per mettere in pausa e rivedere ciò che è stato fatto.(Fare Slide Time: 15.52)
Vediamo ora alcune strutture dati di questo problema. La struttura dati chiave è ovviamente una tabella. Nella nostra discussione, abbiamo definito questo come la tabella delle spese, oppure può essere anche definito comeuna matrice. Sarebbe bene indicizzare questa tabella utilizzando il RoommateID. Questo potrebbe esserefatto, ad esempio, utilizzando dizionari in Python. Lasciamo questa discussione qui come il programmapuò essere implementato in qualsiasi lingua.Per il nostro corso abbiamo usato, utilizzeremo Java. Come esattamente dobbiamo realizzare l'indicizzazione basata su RoommateIDè qualcosa che lasciamo a te! Gli altri pezzi di informazioni sono davverosingoli tipi di dati. Ad esempio, il RoommateID è una stringa. L'EventID è un numero interopositivo. Le spese o per capo condividi, o tali oggetti, sono numeri reali o numeri a virgola mobile.(Fare Slide Time: 17.24)
Ci servirà anche la dichiarazione del metodo che calcola la fair sharing. Quella è un'importante elaborazione della funzioneda fare in questa soluzione. Ecco uno schizzo di dichiarazione del metodo,Boolean computePerHeadShare (Real Estensi []);. Questa dichiarazione èillustrativa e utilizza una sintassi in stile C, C++ e Java. Il metodo restituisce un Boolean: che ci dicese il lavoro è fatto o meno. Magari mentre progrediamo e aggiungiamo la complessità, potremmo dover cambiareil tipo di ritorno a uno più adatto. Il metodo accetta un parametro, una schiera di numeri realinamed Spese, che rappresenta la tabella delle spese finora.
Quick Check 1: Nella lezione abbiamo usato Boolean come tipo di ritorno per ilcomputePerHeadShare, ma in realtà questo doesn t t serve bene lo scopo. Quale potrebbe essere un tipo di ritornomigliore per questa funzione e perché?(Fare Slide Time: 18.15)
ripetiamo che questo è solo uno schizzo delle strutture dati essenziali. A seconda della lingua chesi utilizza, potrebbe essere necessario utilizzare i modi corretti per definire queste strutture dati. Inoltre, si puòvoler arricchire queste strutture dati. Queste sono solo schizzi di ossa nude. Ad esempio, invece di solonumeri nella tabella delle spese, si potrebbe desiderare di aggiungere anche la data o la posizione o la descrizione.
Nelle nostre illustrazioni nel foglio di calcolo avevamo mostrato una data di colonna, che le informazioni erano anchecatturate lì. Potresti anche avere bisogno di ulteriori metodi. Ad esempio, è possibile che tu possavoler calcolare la quota equa di un determinato coinquilino invece di tutti. Quindi, potresti volerrestituire una schiera di numeri reali che indicano la condivisione di un determinato coinquilino dato da RoommateIDR, e la schiera Spese [].
Quick Check 2: Nella lezione abbiamo usato Real [] come tipo di ritorno per getFairShareOf, maabbiamo davvero bisogno di una schiera di numero reale? Quale potrebbe essere un tipo di ritorno migliore per questa funzione,e perché?
Questo è un punto in cui vorremo attirare la vostra attenzione. In alcune assegnazioni, potremmo affidare ai metodi da definire e utilizzare, potremmo affermare esplicitamente che quali sono i metodi che si hanecessità di definire e utilizzare. Ogni volta che viene dato un simile mandato, allora la tua soluzione deve essere costruitautilizzando i metodi indicati e altri metodi aggiuntivi che si possono degustare. Ma devono essere richiesti i metodiindicati. Potremmo utilizzare test automatizzati e, di conseguenza, se non esisteranno nella tua soluzione, non saremo in grado di valutarlo e, quindi, non guadagnerai crediti per quell' impegno.(Fare Slide Time: 20.39)
Mentre arriviamo alla fine di questa sessione, lasciatemi schizzare il nostro percorso verso l'app web. Prossimamente guarderemoalla versione di riga di comando del programma avrà seguito le principali proprietà:• La versione della riga di comando sarà l'app per l'utenza unica.• Sarà in esecuzione su una singola CPU condivisa tra i singoli coinquilini.• Ci sarà una singola base di informazioni localizzate. Non esiste rete.Essenzialmente, si tratta di un'architettura molto monolitica. Ci generalizzavamo incorporando più utenti, ma comunque con una CPU condivisa. Quella CPU condivisa è quella che chiameremmo come accesso di serviziopunto. Questo implicherebbe includere ulteriore pezzo di funzionalità, come l'autenticazione dell'utente. E noipotremmo dover pensare alla separazione delle informazioni contro la condivisione. Analizzeremo questi come il corsoprogredisce.
Avanti, introdurremo la rete. Ma l'idea principale della rete è che un separatore di inpute output e la lavorazione. Analizzeremo il web come una tecnica di input di rete larga e output. Apre le possibilità di architetture a punti multi - accesso. Pertanto, la nostra architetturanon sarà più monolitica e sarà distribuita. Le nostre prossime generalizzazioni sarebbero lungorendendo la nostra app multi utente con più punti di accesso con più gruppi di coinquilini e cosìon. Questo puoi utilizzare questa anteprima per iniziare a pensare a come generalizzare la tua app in vari modi.Verso la fine di questo corso avrai un progetto di 2 settimane in cui potrai generalizzare in comemolti modi diversi come si può pensare. Ovviamente, ti verrà richiesto di impegnare prima la tua generalizzazione, devi indicare qual è la generalizzazione che farai e soloinoltrare quella parte.Questo è un buon punto di pausa.Con che arriviamo al termine della seconda sessione della settimana 1. Grazie. Ci vediamo nella prossima sessione.