Informatiker Board | Suchergebnis

Informatiker Board » Suche » Suchergebnis

» Hallo Gast [Anmelden|Registrieren]

Zeige Beiträge 1 bis 6 von 6 Treffern

Autor

Beitrag

Thema: kontextfreie Grammatik deterministich machen

evinda

Antworten:	0
Hits:	4.331

kontextfreie Grammatik deterministich machen 07.09.2014 16:10

Forum: formale Sprachen

Hallo!!!

Ich habe eine kontextfreie Grammatik,die ich deterministich machen will.

Das ist die kontextfreie Grammatik:

$[latex]I \to \gamma \delta a X | \gamma \delta \beta Y , X \to XXX | \delta , Y \to I | X[/latex]$

Ich habe folgendes versucht:

$[latex] I \to \gamma \delta K , K \to aX | \beta Y[/latex]$
$[latex] X \to \delta M, M \to \delta M | \varnothing [/latex]$
$[latex] Y \to \gamma \delta K | \delta M[/latex]$

Ist es richtig? verwirrt

Oder ist es nicht so $[latex] X \to \delta M, M \to \delta M | \varnothing [/latex]$ ,sondern so:
$[latex] X \to \delta M, M \to \delta N , N \to \delta N | \varnothing [/latex]$ ?

Oder habe ich was anderes falsch gemacht? geschockt

Thema: Warteschange Q

evinda

Antworten:	2
Hits:	3.957

RE: Warteschange Q 31.08.2014 00:02

Forum: Algorithmen

Ok!!! Vielen Dank!!!! Daumen hoch

Thema: Warteschange Q

evinda

Antworten:	2
Hits:	3.957

Warteschange Q 26.08.2014 13:54

Forum: Algorithmen

Hallo!!!

Ich habe eine Frage über die Anwendung des folgenden Algorithmus bei einen Beispiel:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:

Breitensuche(G,s)

for each u !=  V \ {s}
     color[u]<-white
     d[u]<-oo
     p[u]<-Ø
color[s]<-gray
d[s]<-0
p[s]<-Ø
Q<-Ø // Q ist eine Warteschlange
Insert(Q,s)
while Q != Ø
       u<-Delete(Q)
       for each v e  Adj(u)
          if color[v]=white then
             color[v]<-gray
             d[v]=d[u]+1
             p[v]<-u
             Insert(Q,v)

       color[u]<-black

code:
1: 2: 3: 4: 5: 6: 7: 8:	Delete(Q) x<-Q[head[Q]] if head[Q]=length[Q] then head[Q]<-1 else head[Q]<-head[Q]+1 return x

Das Beispiel ist das folgende,s. breadth.png

Am Anfang ist es so,s. fi.png

und nach der ersten "for",ist es so,s. search.png

Ich habe nicht verstanden,warum man von Q das s löscht.

Mit der Anweisung u<-Delete(Q),bekommt u den Wert s, und in der Funktion ändert sich die Variable head[Q],beim Hauptprogramm,bleibt sie aber unverändert,oder nicht? :-?

Thema: Teilprobleme im Verhältnis 9:1 zerlegen

evinda

Antworten:	2
Hits:	3.725

10.08.2014 01:16

Forum: Theoretische Informatik

Ich will die Rekursionsgleichung finden,mit der ich die Komplexität vom Algorithmus berechnen kann,angenommen wir zerlegen die Teilprobleme im Verhältnis 9:1.

Die Implementierung der Funktion "partition" teilt das Feld so, dass sich das Pivotelement an seiner endgültigen Position befindet und alle kleineren Elemente davor stehen, während alle größeren danach kommen.

Die Funktion ist die folgende:

code:
1: 2: 3: 4: 5: 6: 7: 8: 9:	partition(A,p,r) x<-A[r] i<-p-1 for j<-p to r-1 if A[j]<=x then i<-i+1 A[i]<->A[j] A[i+1]<->A[r] return i+1

Thema: Teilprobleme im Verhältnis 9:1 zerlegen

evinda

Antworten:	2
Hits:	3.725

Teilprobleme im Verhältnis 9:1 zerlegen 09.08.2014 17:53

Forum: Theoretische Informatik

Hallo!!!

Wie kann ich die Rekursion finden,die die Komplexität vom Algorithmus Quicksort beschreibt,wenn wir die Teilprobleme im Verhältnis 9:1 zerlegen?

Der Algorithmus ist der folgende:

code:
1: 2: 3: 4: 5:	Quicksort(A,p,r) if p<r then q<- partition(A,p,r) Quicksort(A,p,q-1) Quicksort(A,q+1,r)

Thema: Komplexität vom Algorithmus

evinda

Antworten:	1
Hits:	4.002

Komplexität vom Algorithmus 27.07.2014 19:40

Forum: Berechenbarkeits- und Komplexitätstheorie

Hallo!!!

Ich will die Komplexität vom folgenden Algorithmus finden.

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:

 Merge(A,p,q,r)
           n1=q-p+1;
           n2=r-q;
           for i<-1 to n1
               L[i]<-A[p+i-1]
           for j<-1 to n2
                R[j]<-A[q+j]
           L[n1+1]<-oo  ,   R[n2+1]<-oo   
               
           
           i<-1, j<-1
           for k<-p to r
              if L[i]<=R[j] then
                  A[k]<-L[i]
                  i<-i+1
              else
                  A[k]<-R[j]
                  j<-j+1
             
      
        MERGESORT(A,p,r)
           if p<r then
              q<-floor((p+r)/2)
              MERGESORT(A,p,q)
              MERGESORT(A,q+1,r)
              Merge(A,p,q,r)

In meinen Buch,steht das die Komplexität die folgende ist:

$[latex] T(n)=\begin{cases}<br /> c & ,n=1\\ <br /> 2T(n/2)+cn & ,n>1<br /> <br /> \end{cases}[/latex]$

ich habe aber nicht verstanden,wie man zu diesen Ergebnis kommt.
Könntet ihr mir weiterhelfen? geschockt

Zeige Beiträge 1 bis 6 von 6 Treffern