.. and the classics 

How mathematicians do it...

Combinatorists do it as many ways as they can.
Combinatorists do it discretely.
(Logicians do it) or [not (logicians do it)].
Logicians do it by symbolic manipulation.
Algebraists do it in groups.
Algebraists do it in a ring.
Algebraists do it in a field.
Analysts do it continuously.
Real analysts do it almost everywhere.
Pure mathematicians do it rigorously.
Topologists do it openly.
Topologists do it on rubber sheets.
Dynamicists do it chaotically.
Mathematicians do it forever if they can do one and can do one more.

Cantor did it diagonally.
Fermat tried to do it in the margin, but couldn't fit it in.
Galois did it the night before.
Möbius always does it on the same side.
Markov does it in chains.
Newton did it standing on the shoulders of giants.
Turing did it but couldn't decide if he'd finished.


How to prove it..

proof by example:
    The author gives only the case n = 2 and suggests that it contains most of the ideas of the general proof.
proof by intimidation:
    "Trivial."
proof by vigorous handwaving:
    Works well in a classroom or seminar setting.
proof by cumbersome notation:
    Best done with access to at least four alphabets and special symbols.
proof by exhaustion:
    An issue or two of a journal devoted to your proof is useful.
proof by omission:
    "The reader may easily supply the details"
    "The other 253 cases are analogous"
    "..."
proof by obfuscation:
    A long plotless sequence of true and/or meaningless syntactically related statements.
proof by wishful citation:
    The author cites the negation, converse, or generalization of a theorem from the literature to support his claims.
proof by funding:
    How could three different government agencies be wrong?
proof by eminent authority:
    "I saw Karp in the elevator and he said it was probably NP-complete."
proof by personal communication:
    "Eight-dimensional colored cycle stripping is NP-complete [Karp, personal communication]."
proof by reduction to the wrong problem:
    "To see that infinite-dimensional colored cycle stripping is decidable, we reduce it to the halting problem."
proof by reference to inaccessible literature:
    The author cites a simple corollary of a theorem to be found in a privately circulated memoir of the Slovenian Philological Society, 1883.
proof by importance:
    A large body of useful consequences all follow from the proposition in question.
proof by accumulated evidence:
    Long and diligent search has not revealed a counterexample.
proof by cosmology:
    The negation of the proposition is unimaginable or meaningless. popular for proofs of the existence of God.
proof by mutual reference:
    In reference A, Theorem 5 is said to follow from Theorem 3 in reference B, which is shown to follow from Corollary 6.2 in reference C, which is an easy consequence of Theorem 5 in reference A.
proof by metaproof:
    A method is given to construct the desired proof. The correctness of the method is proved by any of these techniques.
proof by picture:
    A more convincing form of proof by example. Combines well with proof by omission.
proof by vehement assertion:
    It is useful to have some kind of authority relation to the audience.
proof by ghost reference:
    Nothing even remotely resembling the cited theorem appears in the reference given.
proof by forward reference:
    Reference is usually to a forthcoming paper of the author, which is often not as forthcoming as at first.
proof by semantic shift:
    Some of the standard but inconvenient definitions are changed for the statement of the result.
proof by appeal to intuition:
    Cloud-shaped drawings frequently help here.

From: User
-Subject:
-To: [email protected]
-Date: Mon, 28 Mar 1994 18:59:47 +0800 (WST)

SysAdmin, how do I use mail to send my friend in the US a picture file of
myself?
User

-From [email protected]
-Subject: Re: self portrait
-To: User
-Date: Mon, 28 Mar 1994 18:59:47 +0800 (WST)

> SysAdmin, how do I use mail to send my friend in the US a picture file of
> myself

Ok. Its not often that we get a request for this kind of thing, but here goes. When logged into a unix system with email access, you need to type 'elm -s "photo" [email protected]'. Now when it comes to the "Copies to:" prompt, stand in front of the screen so that you get a nice reflection on the glass. You may need to use some backlighting, such as a bright desk lamp for this. Now, without moving your face, press the "Print Screen" key on your keyboard (it is in the top right hand corner of the keyboard) Wait a few seconds, and then press return on the keyboard.

You may wish to add an explanatory message in the body of the letter letting him know what the attached binary file is.

Let me know if you have any problems with this, or if it doesn't work for your system. Some IBM "compatibles" don't fully support this feature, since it is rarely used.


Good luck!
SysAdmin

 

Exista intotdeauna? Adica, este adevarat ca orice graf conex, (2k)-regular este Hamiltonian?
Cred ca raspunsul este nu (cred ca exista un graf conex 4-regular care nu e Hamiltonian: Petersen graph modificat putin). So, poate graful era Hamiltonian pe deasupra (sau K era mai special)?

http://courses.csail.mit.edu/6.851/spring07/lec.html

Un hypercube (n-dimensional cube) graph este un graf care are un nod pentru fiecare string binar de lungime n. Doua varfuri sunt adiacente daca cele doua numere difera printr-un singur bit. (2^n varfuri, n * 2^(n-1) muchii)

Doua muchii sunt independente daca nu au nici un varf in comun si nu exista nici un patrat (ciclu de lungime 4) care le contine pe ambele.

Care este numarul maxim de muchii independente doua cate doua (un upper/lower bound maybe)? (adica, cat de mare poate fi un set S de muchii astfel incat oricare doua muchii din S sunt independente).

Any thoughts?
 
Numarul maxim de muchii independente doua cate doua e mult mai mare decat credeam  .
Un lower bound de  O(2^(n-1)) e aproape evident (construiesti un graf G care are un varf pentru fiecare muchie; doua varfuri sunt adiacente in G daca cele doua muchii nu sunt independente; G are n*2^(n-1) varfuri si fiecare varf are 3(n-1) vecini, deci are un independent set >= n*2^(n-1)/(3*(n-1))).
Initial am crezut ca numarul maxim de muchii independente doua cate doua e polinomial in n (problema nu e foarte interesanta daca numarul de muchii e exponential). 

Anyway.. nevermind.

Daca recunoaste careva melodia din ultimul clip sa-mi zica si mie pls

manowar - warriors of the world united

Nu cred ca are rezolvare polinomiala. Altfel ai putea rezolva prin aceeasi metoda si problema comis voiajorului.

cum reduci hamilton path la problema aceasta? nu mi se pare evident pentru ca in problema aceasta ai voie sa vizitezi un nod de mai multe ori..
exista o varianta a acestei probleme care e NP-complete, si anume sa gasesti cel mai lung drum simplu (nu ai voie sa repetzi un nod) (aici reducerea e evidenta, cel mai lung drum simplu intr-un graf hamiltonian este un drum hamiltonian)
in schimb, sa gasesti un drum care viziteaza orice muchie cel mult o data (adica "walk") (care poate sa inceapa si sa se termine in orice nod) intr-un graf pare polinomial (ma gandeam la un algoritm de genul: fie s un nod al grafului si w_s un walk constuit astfel: pornesti din s si traversezi o muchie la intamplare cu conditia sa nu traversezi un bridge (bridge sau cut-edge e o muchie e a.i. G\e are mai multe componente conexe decat G) decat daca esti fortzat sa o faci (bineinteles, stergi muchia traversata); continui pana cand nu mai poti extinde walkul.. intuitiv, un walk maximal cred ca este w_s a carui lungime este maxima)

presupun ca limbaje formale inseamna regular languages/context-free grammars/turing machine languages si automatele lor  (am incercat un google search, si primele rezultate cam asta imi sugerau)
am luat un curs la un moment dat.. se numea Theory of computation, si era de fapt cartea lui Sipser din scoartza in scoartza (Sipser M, Introduction to the theory of computation).
pot sa-ti dau pagina cursului, dar nu cred ca te ajuta (poate doar daca vrei sa vezi ce probleme primeam ca teme)
http://www.cs.princeton.edu/courses/archive/fall06/cos487/
desi se numeste "introduction to.." cartea aceea e chiar foarte avansata, dar e incredibil de bine scrisa .
in prima parte sunt toate acele limbaje si automate, si din cate stiu este cartea de referintza pentru cursurile avansate de teoria computatiei.
cred ca inca se mai gaseste pe net un web draft al cartii, cred ca era editia 1; editia 2 are mult mai multe probleme fatza de editia 1, in rest sunt la fel (toate problemele din editia 2 se gasesc pe net oricum).

Am citit de curand cartea Thinking in C++ Second Edition de Bruce Eckel ... urmeaza sa citesc Editia urmatoare ... o carte foarte interesanta

good point

am citit de curand Complexity Theory: A modern approach (S. Arora, B. Barak) http://www.cs.princeton.edu/theory/complexity/

si Graph Classes: A Survey (J. Spinrad)

prima e mai fun decat cea de-a doua (am incercat sa pun un link pentru cea de-a doua, eu aveam un web draft dar se pare ca nu mai exista pe web)

a.. si am rasfoit Data Structures and Network Algorithms (R. Tarjan).. cam veche si pare ca un survey al catorva articole semnate de Tarjan (dar e dragutza pentru inceput)..

Jean-Paul Satre - Greata
Mihail Bulgakov - Maestrul si Margareta
Arthur C. Clarke - Sfarsitul Copilariei , Odiseea Spatiala
J.D. Salinger - De Veghe in Lanul de Secara
Stanislaw Lem - Solaris
Andrew Sinclair - Gog, Magog, King Ludd
Hermann Hesse - Lupul de Stepa, Narcis si Gura-de-Aur, Demian, Peter Camenzind
Lewis Carroll - Alice in Tara Minunilor
Fyodor Dostoyevsky - Crima si Pedeapsa
Jules Verne - 20000 de Leghe sub Mari, Ocolul Pamantului in 80 de Zile
Gabriel Garcia Marquez - Toamna Patriarhului, Un Veac de Singuratate, Despre Dragoste si Alti Demoni
Gabriel Liiceanu - Usa Interzisa
Albert Camus - Strainul, Ciuma
Friedrich Nietzsche  - Dincolo de Bine si Rau, Amurgul Idolilor
Franz Kafka - Metamorfoza, Procesul
Mircea Eliade - Romanul Adolescentului Miop, Gaudeamus, Dayan, Nouasprezece Trandafiri
Charles Dickens - David Copperfield, Marile Sperantze, Povestea Celor Doua Orase
James Clavell - Shogun

A Clockwork Orange, Pink Floyd The Wall,  Eternal Sunshine of the Spotless Mind, The Terminal, Filantropica, Occident, Everything is Illuminated, American Beauty, Casablanca, Breakfast at Tiffany's, Amelie,

The Pianist, Lord of War, Birdy, Good Will Hunting, A Beautiful Mind,  Moartea Domnului Lazarescu, The Weather Man, Amadeus, The Truman Show, Match Point, Just Friends, Serendipity,  Home Alone 1-3, Mr. & Mrs. Smith, The Lord of the Rings, Star Trek I-VI, The Legend of Zorro, The Mask of Zorro, Ocean's Twelve,  Alexander The Great, Ice Age, Garfield, toate filmele semnate Disney-Pixar  (Toy Story, A Bug's Life, Monsters Inc, The Incredibles, Finding Nemo, etc.), Superman I-V, How the Grinch Stole Christmas, The Mask, The Chronicles of Narnia,

probabil le-am uitat tocmai pe unele dintre cele mai importante

din cate imi amintesc.. this should work:

minim = *(s.begin());
maxim = *(s.rbegin());

begin() si rbegin() sunt in timp constant amortizat..

.. poate imi scapa ceva.. dar confunzi cumva C++ reference cu pointer?
C++ are un tip de variabila numit "reference" care nu exista in C (in C acelasi rezultat e obtinut folosind pointeri)
acest tip de variabila e folosit in parametri, de exemplu functia void invert(char&, char&)  despre care intrebai..
conceptual, reference variables sunt de fapt pointers sub un alt nume, dar nu pot fi instantiate ca pointeri de catre compilator..

uite un exemplu:
int x;
int *p1 = &x;   // pointer
int &p2 = x;     // reference

atat p1 cat si p2 contin adresa lui x

daca vrei sa atribui o valoare lui x (sa zicem 10):
*p1 = 10;        // adresa trebuie sa fie "dereferenced" folosind *
p2 = 10;          // adresa este "dereferenced" fara sa folosesti vreun operator

adresele pot fi manipulate direct daca folosesti un pointer, de ex: ++ p1 (ca sa obtii urmatoarea adresa)
ceea ce nu e posibil folosind reference

sper ca intelegi de ce functzia aceea merge..

la prima vedere, nu pare prea important ca numerele sunt intregi.. pot sa fie chiar reale (cam acelasi algoritm, poate un pic mai simplu)..
asa ca sa zicem ca-s reale..

daca numerele sunt toate pozitive, poti aplica algoritmul pentru subsecventza de suma maxima (fiind reale, pot sa fie < 1: o subsecventza cu 0 elemente are produsul 1, ignori subsecventze cu produs < 1)

fie prod(s) = produsul elementelor subsecventzei s

tii doua subsecventze (de fapt tii modulul produsului numerelor si eventual cei 2 indici): prima este subsecventza maximala cu produs pozitiv (prod(s) > 0, si pentru orice subsecventza s' cu prod(s') > 0: prod(s) >= prod(s'))
cea de-a doua este subsecventza maximala cu produs negativ (prod(s) < 0,
si pentru orice subsecventza s' cu prod(s') < 0: |prod(s)| >= |prod(s')|)

sa zicem ca o subsecventza maximala e x[ i ]..x[ j ]
daca x[ j ] > 0:  x[ i ] .. x[ j-1 ] este o subsecventza maximala cu produs pozitiv
daca x[ j ] < 0:  x[ i ] .. x[ j-1 ] este o subsecventza maximala cu produs negativ

fie A produsul subsecventzei maximale cu produs pozitiv, B valoarea absoluta a produsului subsecventzei maximale cu produs negativ

initial A = 1; B = 0

deci faci update cam asa:
   citesti x[ i ]
   
   x[ i ] > 0: A *= x[ i ]; B *= x[ i ]
   x[ i ] < 0: A *= abs(x[ i ]); B *= abs(x[ i ]); swap A si B
   x[ i ] = 0: A = 1; B = 0
   
   A = max(1, A);
   best = max(best, A);

ai nevoie sa tii doar 3 variabile (A, B, best) si eventual cate o pereche de indici pentru fiecare (daca ai nevoie sa stii indicii de inceput si sfarsit ai subsecventzei)

trebuie sa demonstrezi ca e corect? inductie.

nu pot sa fac dijsktra in loc de bellman ford ? parcurgerea in latime gaseste un cel mai scurt drum relativ la nr de muchii, dijsktra gaseste un cel mai scurt drum relativ la costurile pe muchii. 

.

. poti sa folosesti Dijkstra daca nu ai cicluri de cost negativ, dar trebuie sa modifici
greutatile pe muchii ca sa devina non-negative...

pentru a modifica greutatile muchiilor, tii un vector f[ v ] = potentialul varfului v
greutatea (costul) fiecarei muchii e = u->v devine w[ e ] + f[ u ] - f[ v ], unde w[ e ] este adevaratul cost al muchiei...
costul unui drum de la s la t se modifica cu o constanta (f[ s ] - f[ t ]), asa ca drumurile de cost minim in graful cu
costurile modificate nu se modifica..

initial f[ v ] = costul minim de la s la v
noul cost al unei muchii e >= 0, pentru orice muchie e = u->v (pentru ca alfel ai avea f[ v ] > f[ u ] + w[ e ],
ceea ce contrazice faptul ca f[ v ] este costul minim)

tot ceea ce ramane de facut e sa modifici potentialele de fiecare data cand
gasesti un augmenting path (trebuie sa le modifici inainte sa trimiti flux
pe drumul gasit)...

sa zicem ca ai gasit un augmenting path p folosind Dijkstra, si d[ v ] = costul
minim de la s la v (gasit de Dijkstra la pasul curent)..
vrei sa modifici potentialele inainte sa trimiti flux pe drumul p astfel incat
toate muchiile pe drumul p sa aiba noul cost 0 (astfel muchiile de intoarcere vor
avea si ele noul cost 0)

asa ca faci update astfel: f[ v ] <- f[ v ] + d[ v ]

teoretic, implementarea naiva max flow + Bellman Ford e O(n^4), si max flow +
Dijkstra + costuri modificate e O(n^3)..
practic, nu stiu care e mai rapid...

.. sau cu wget

poti sa downloadezi sursa si sa o "compilezi" (make && make install vor copia man pages intr-un anumit director ... check the README).. proiectul se numeste man-pages si poti sa il downloadezi de aici:
http://www.win.tue.nl/~aeb/linux/man/

gasesti linkul pe pagina aceea la sectiunea download...
cred ca by default man pages sunt in /usr/share/man/man*   (~/man1, ~/man2 , etc.)..

.. uitasem de BARF (Better Archiver with Recursive Functionality)


http://www.cs.fit.edu/~mmahoney/compression/barf.html

.. un citat (the BARF principle):

Recursive compression has long been thought to be impractical. The pigeonhole principle states that it is impossible for a single algorithm to compress all messages of n bits or more, no matter what n is. This is because there are 2n possible messages of n bits, but only 2n-1 possible encodings of n-1 or fewer bits. This means that at least two messages must code to the same encoding. Such an encoding could not be decompressed unambiguously. To avoid this, some messages must inevitably "compress" to an equal or larger size than the original. This limitation has stymied the development of recursive file compression technology because we eventually reach a point at which the "compressed" file is not any smaller.
However, the pigeonhole principle does not apply to a set of algorithms. BARF solves the recursive compression problem by using multiple algorithms arranged in such a way that every nonempty file can be compressed by at least one of them. By choosing the best algorithm, it is guaranteed that every nonempty file can compressed by at least one byte. By repeated compression, any file can be eventually compressed to 0 bytes.

pai.. o sa vedem oricum.. daca la fiecare pas ai obtine "garantat" o compresie mai buna, ai putea comprima orice fisier arbitrar de mult  .. btw.. ce ai sa stochezi ca sa poti decomprima fisierul dupa ce ai aplicat huffman de cateva ori? ai sa stochezi pentru fiecare pas matricea  caracter-cod? stochezi distributia? 

.. ok.. chiar daca un caracter apare de 1000 ori, al doilea de 1001 ori, si tot asa.. distributia tot (aproape) uniforma ramane.. oricum.. daca ai niste rezultate te rog posteaza-le...

.. da.. va fi un nou sir de caractere.. ma refeream la faptul ca noile caractere in noul mesaj vor avea probabilitate aproape egala... uite, de exemplu iei primii 8 biti si formezi un caracter din noul alfabet.. de cate ori te astepti sa vezi caracterul acesta in noul mesaj? te astepti sa-l vezi a doua oara? a treia, etc? ma refeream doar la faptul ca nu vei avea caractere repetate in noul mesaj..

.. ai incercat sa testezi metoda ta? al doilea pass iti aduce vreo imbunatatire?... sunt curioasa pentru ca intuitiv cred ca a doua aplicare a algoritmului iti poate imbunatati compresia doar din intamplare... intuitia imi spune ca a doua/ treia, etc. distributie pe care o obtii e foarte aproape de distributia uniforma..