[LA] Linux avanzato 2008

Ah un'altra cosa,teorema della colorabilità o non-teorema della colorabilità,a cosa serve fare una prova in C(che poteva anche essere Java,COBOL,Fortran...etc) se poi di C non c'è nulla?A questo punto se si deve conoscere ASD era meglio mettere una domanda in più apposita,e farci fare un esercizio serio sul C,dove si utilizzano puntatori,descrittori di file e processi concorrenti,ma come dice TheOne,se tutto ciò viene fatto al laboratorio a cosa serve farlo su carta?
Poi vedete quanta gente non passa l'esame perchè non sa neanche cosa è un puntatore...

Scusate, non vorrei soffiare sul fuoco ma secondo me tutti siamo capaci di prendere un algoritmo e tradurlo in codice, a prescindere da quale esso sia (posso capire se si doveva scrivere in prolog...)
La difficoltà stava tutta nel ragionare, fare assunzioni e scelte di progettazione prima di buttarsi a dare una soluzione...
E poi... interpretando il grafo come la rappresentazione di una cartina geografica... si riduceva al banale problema dei 4 colori, che qua erano solo due...

Secondo me, almeno nella mia aula, molti sono andati in panic-mode quando è stato detto che l'esercizio di C era fondamentale e tanti si sono fiondati a risolvere senza analizzare la domanda: in fondo la matrice di adiacenza associata ad un grafo la conoscono TUTTI e scandire una matrice altrettanto.

L'esercizio non chiedeva una soluzione esatta, o ottima, o chissà cosa. Era una riga e mezza che chiedeva: esiste una possibilità che ogni coppia di nodi abbia colori differenti?

Rizzi ha scritto:

Ludace ha scritto:

Ragazzi,
senza offesa, ma Algoritmi e Strutture Dati era tra i requisiti richiesti e il problema in C che ci ha proposto non mi pareva di grande difficoltà, anzi, anche senza aver mai studiato la materia, si poteva fare benissimo..

Magari mi ha bocciato (molto probabile), ma credo che della difficoltà dell'esame non ci si può proprio lamentare..

Come l'hai risolto? Non parlo di C ma di algoritmo risolutivo.

Molti a fine esame hanno detto che era semplice ma non avevano capito la traccia.

Ciao

ciao ragazzi! Io nei primi 10 minuti ho pensato di andarmene e che non ci sarei mai riuscito.. poi piano piano ho cominciato a mettere insieme le informazioni che avevo e ho deciso che dovevamo vedere solo se ci fossero dei cicli con 3 nodi.. infatti se 3 nodi (tipo i vertici di un triangolo) sono attaccati non si può colorare con 2 colori..
Quindi ho fatto 3 cicli for ( i = riga per riga - j= Cerca un uno sulla riga - k= Cerca gli altri uni sulla riga e vai a vedere se M[j][k] ==1 ossia se anche gli altri 2 nodi sono adiacenti e quindi c'e' un ciclo) e tanti saluti.. Wikipedia sembra darmi ragione riguardo l'algoritmo, ma come è già stato detto da ludace, tanto mi boccerà lo stesso!
Da un punto di vista formale il problema consisteva nel vedere se il grafo era bipartito:
en.wikipedia.org/wiki/Bipartite_graph

Intuitive definition

It is possible to color the nodes of a bipartite graph red and blue such that no edge exists between like colors. For example, this is impossible in the case of a fully connected graph with 3 vertices (a triangle): after one node is colored red and another blue, the remaining one is connected to both but must have the same color as either.

Insomma, speriamo bene anche nel male!

Smoking, ho fatto esattamente come te ma penso non basti perchè il teorema dice questo:

"Teorema dei due colori per i grafi: Un grafo è 2-colorabile se e soltanto se il grafo non ha cicli di lunghezza dispari. (si ricorda che un ciclo (o circuito) in un grafo è un cammino chiuso, cioè una sequenza di almeno 3 lati che non si auto-intersechi, tale che il vertice iniziale e finale coincidano)."


Quindi il controllo da fare era che non ci fossero cicli con un numero dispari di nodi.

La mia speranza è che, essendoci andati vicino e avendo (si spera) ben implementato la nostra idea, almeno la sufficienza esca fuori!

Cara Eturella,si disquisiva su un altro argomento...ossia il fatto che l'esercizio poteva essere spiegato in un modo più chiaro,perchè è ovvio che chiunque si trovi al quarto anno(laureato) sappia fare un algoritmo che scandisce una matrice...quindi non c'è bisogno di sottolinearlo nuovamente perchè la discussione non verte sulla difficoltà dell'esercizio...
Anzi,secondo me l'esame era molto più abbordabile degli altri passati...
Poi ancora,a prescindere dal teorema dalla colorabilità o non,se si parla di programma in C e dato che si sta parlando di verifica delle conoscenze allora voglio un esercizio che testi LE MIE CONOSCENZE SUL LINGUAGGIO C...nient'altro e quindi se vuole testare le mie conoscenze su algoritmi e strutture dati mi fa un'altra domanda....oppure toglie questo ridicolo test,perchè io,come tutti voi,non devo dimostrare di conoscere delle cose che lo stesso Bovet mi ha insegnato nella triennale..........
Ma poi si torna a parlare sempre della stessa cosa,e qualcuno mi accuserà di fare discorsi ridondanti...
A tutti voi,anche ai più sboroni, auguro un grosso in bocca al lupo....

Rizzi ha scritto:

Smoking, ho fatto esattamente come te ma penso non basti perchè il teorema dice questo:

"Teorema dei due colori per i grafi: Un grafo è 2-colorabile se e soltanto se il grafo non ha cicli di lunghezza dispari. (si ricorda che un ciclo (o circuito) in un grafo è un cammino chiuso, cioè una sequenza di almeno 3 lati che non si auto-intersechi, tale che il vertice iniziale e finale coincidano)."


Quindi il controllo da fare era che non ci fossero cicli con un numero dispari di nodi.

La mia speranza è che, essendoci andati vicino e avendo (si spera) ben implementato la nostra idea, almeno la sufficienza esca fuori!

cavolo è vero... non so perchè ma la mia mente si era fermata a 4 nodi (forse pensavo che 3 è il minimo indispensabile e non mi sono posto il problema di cosa accadeva con 5). a questo punto allora non spero proprio più di averlo passato.. azzo!