Computermathematik_HE_G5

359 days ago by PatrickHammer

Hausübungsblatt_1
Gelöst von Patrick Hammer, Daniel Perz und Sandra Peterl
WS 2010/11

BEISPIEL 1
Schreiben Sie einen Algorithmus der ein maximales Matching in einem Graphen findet. Testen Sie Ihren Algorithmus anhand eines (zufälligen) Graphen mit mindestens 15 Knoten.

Lösung:
1. Liste allcomb aller möglichen Edges-Kombinationen bilden per Potenzmenge.
2. Matchings in allcomb sind nur jene welche keinen Knoten doppelt haben.
3. Wähle nun eines der Matchings mit maximaler Knotenanzahl, dieses ist ein maximales Matching.
G=graphs.RandomGNP(15,0.1) show(plot(G)) alledges=[[x[0],x[1]] for x in G.edges()] #all edges allcomb=list(powerset(alledges)) #all possibilities to combine edges matchings_quality=[]; matchings=[] for x in allcomb: flatx=sum(x,[]) #vertice is only one time in list => a matching if len([a for a in flatx if flatx.count(a)==1]) == len(flatx): matchings_quality.append(len(flatx)) matchings.append(x) best_index=matchings_quality.index(max(matchings_quality)) print "a maximal matching:",matchings[best_index] print "not used vertices amount:",len(G.vertices())-matchings_quality[best_index] 
        

a maximal matching: [[0, 4], [2, 9], [3, 10], [5, 11], [6, 14], [8, 12]]
not used vertices amount: 3

a maximal matching: [[0, 4], [2, 9], [3, 10], [5, 11], [6, 14], [8, 12]]
not used vertices amount: 3
BEISPIEL 2
Man berechne Γ(3/2) := ∫(0,oo) t^1/2 e^−t dt mit Hilfe der Kepler’schen Fassregel auf 20 Stellen genau. (Hinweis: Beispiele 6 und 16)
%hide %latex \[ \int t^{1/2} e^{-t} dt\] $t= x^{2} \Rightarrow dt = 2x dx$ $\Rightarrow$ \[\int t^{1/2} e^{-t} dt = \int e^{-x^{2}} dx\] 
       
f(t)=e^(-t^2) g(t)=t^(1/2)*e^(-t) a=0; b=8; digits=20; showdigits=20 def fass_sum(f,n,a,b): h=(b-a)/n return h/3*((f(a)+f(b))/2+sum([f(a+c*h) for c in range(1,n)])+2*sum([f((a+c*h+a+(c-1)*h)/2) for c in range(1,n+1)])) print g.integrate(t,0,oo)==f.integrate(t,0,oo) var('h'); accuracy=10^-digits print "f at b already accurate enough:",f(b) #this idendity print "integrate f(t) dt == sqrt(pi)/2?",bool(f.integrate(t,0,oo)==sqrt(pi)/2) #allows an exact error check MAX=f.derivative(4).find_maximum_on_interval(a,b,tol=10^-10000)[1] h=N([s[h] for s in solve([accuracy==(b-a)/2880*h^4*MAX],h,solution_dict=true) if s[h] in RR and s[h]>0][0]) print "h needs to be smaller or equal to:",h n=ceil((b-a)/h); print "sectors: ",n wert=fass_sum(f,n,a,b); fehler=N(abs(wert-sqrt(pi)/2),digits=999) print "fehler:",fehler,"fasssumme:",N(wert,digits=showdigits+2) 
        
t |--> 1/2*sqrt(pi) == 1/2*sqrt(pi)
f at b already accurate enough: e^(-64)
integrate f(t) dt == sqrt(pi)/2? True
h needs to be smaller or equal to: 0.0000365365851708817
sectors:  218959
fehler:
9.9472743739807434331700932432041311403846350663442929303416949158666454\
708503357049754289186078823147221250256771505800918633541923573916395826\
447617259630204022360799381284576827430798059762447075437955175981869814\
337429588381208806609355087312385951917361924332121427934697403882217136\
642666319213596461604247528446627079975792975255261468514333280842409579\
159785696472679026945090394062329354264319309759428532463692812549408126\
596422013614350832190251283661894521112436406092164238615111360263988088\
282005834801938450765904389134665545565369026508206519272695519492142316\
657276560547577003121714223104224328850481429646248709894153122039780526\
339651372568144148370543901163579591961183650205372278605526750484389116\
482607592952021781950338185196751101050791376115951111265782536024357031\
491619447672414267145226638929491018195532930744316085300437276767820629\
211874802786665507279427977515490622841633029588213540957226569118227580\
6331632933715722445204908492851839886128527112088554244382605258e-30
fasssumme: 0.8862269254527580136496
t |--> 1/2*sqrt(pi) == 1/2*sqrt(pi)
f at b already accurate enough: e^(-64)
integrate f(t) dt == sqrt(pi)/2? True
h needs to be smaller or equal to: 0.0000365365851708817
sectors:  218959
fehler: 9.94727437398074343317009324320413114038463506634429293034169491586664547085033570497542891860788231472212502567715058009186335419235739163958264476172596302040223607993812845768274307980597624470754379551759818698143374295883812088066093550873123859519173619243321214279346974038822171366426663192135964616042475284466270799757929752552614685143332808424095791597856964726790269450903940623293542643193097594285324636928125494081265964220136143508321902512836618945211124364060921642386151113602639880882820058348019384507659043891346655455653690265082065192726955194921423166572765605475770031217142231042243288504814296462487098941531220397805263396513725681441483705439011635795919611836502053722786055267504843891164826075929520217819503381851967511010507913761159511112657825360243570314916194476724142671452266389294910181955329307443160853004372767678206292118748027866655072794279775154906228416330295882135409572265691182275806331632933715722445204908492851839886128527112088554244382605258e-30 fasssumme: 0.8862269254527580136496