Algorithmen und Datenstrukturen – die meistgelesenen Beiträge

Verwandte Themen
Jensek81
15.09.2019, 19:59
Mit Bildern

Logarithmenfunktionen nach asymptotischem Wachstum ordnen?

Guten Abend

Ansatz:

Zunächst erst mal alle unnötig kompliziert gegebenen Funktionen so umschreiben, dass sie sich vergleichen lassen

a (n) = 13n³, kann man nicht mehr vereinfachen

b (n) = log_4 n³ ist nichts anderes als 1,5 log_2 n

c (n) = 9 log_3 n hätt ich jetzt auch nicht weiter vereinfachen können

d (n) = log_2 4 n^4/3 ist nichts anderes als log_2 (4) + log2 (n^3/4), also 2 + 3/4 log_2 n

e (n) = n^log_4 n^4 kann man umschreiben zu n^2 log_2 (n).

Ich hätte die Funktionen also sortiert (von langsam nach schnell):

c < d < b < a < e.

Problem: Mein Tutor meinte die richtige Reihenfolge wäre: d < b < c < e < a.

Ich versteh es nicht. c. hat ja log_3 (n) und das ist ja schon mal langsamer als alles mit log_2 (n). Bei d und b bin ich mir unsicher, weil die ja eigentlich asymptotisch gleich schnell wachsen sollten. b wächst vielleicht bissl schneller weil es mit 1,5 multipliziert wird, während d nur mit 3/4 multipliziert wird.

Großes Kopfzerbrechen bereitet mir die Tatsache, dass e langsamer wachen soll als a. Bei e (n) ist doch das "n" im Exponenten. Auch wenn man im TR z.B. für n = 17 die Funktion e (n) eingibt, also 17^log_4 (17)^4 ist das 2.9210^21, also eine tierisch hoche Zahl. Wärend n = 17 in die Funtkion a(n) eingesetzt, lediglich 1317³ = 63869 ergibt, also viel weniger wächst. Auf desmos kann man die Funktionen plotten, und dort ist e (n) [bzw. ich musste es hier f(n) nennen, weil das Programm den Buchstaben "e" direkt als Euler'sche Phi-Funktion interpretiert] auch viel stärker an der y-Achse dran, also müsste es doch eigentlich stärker wachsen, or?

Bild zum Beitrag
Schule, Mathematik, Informatik, Logarithmus, Potenzen, Theoretische Informatik, Wachstum, Algorithmen und Datenstrukturen
2 Antworten
EkkoMcfly
21.04.2022, 20:06

Korrektheitsbeweis Algorithmus?

Hallo liebe Community,

ich habe eine Aufgabe bekommen in welcher ich Pseudocode entwickeln soll. Meinem Algorithmus wird ein Array an Zahlen gegeben A[1, n] mit n Einträgen. Ich soll in diesem Array die Senken zählen. Eine Senke ist dabei eine Position i [2, n - 1] für die folgendes gilt: A[i - 1] > A[i] < A[i + 1].

Meiner Auffasung nach bedeutet das nun, dass z.B. das Array [1, 3, 2, 4, 3, 5] zwei Senken hat. Nämlich einmal der dritte Eintrag und der fünfte Eintrag.

Mein Pseudocode sieht folgendermaßen aus:

Input: A[1, n] mit n Einträgen
Output: Anzahl der Senken

counter := 0
for j := 2 to n - 1 do
  val := A[j]
  if val < A[j - 1] and val > A[j + 1] do
    counter := counter + 1

Mein Java Code dazu sieht folgendermaßen aus:

public static int countSenken(int[] arr) {
  int counter = 0;
  for (int i = 1; i < arr.length - 1; i++) {
    int val = arr[i];
    if (val < arr[i - 1] && val < arr[i + 1]) {
      counter++;
    }
  }
}

Nun soll ich die Korrektheit meines Algorithmus' beweisen. Wir haben das schonmal an dem Beispiel des Insertionsort Algorithmus' gemacht. Die herangehensweise ist ja eigentlich, dass man eine Schleifeninvariante aufstellt und diese dann mittels Induktion beweist. Mein Problem ist jetzt aber, dass ich diese Schleifeninvariante nicht aufstellen kann. Beim Insertionsort, da beweist man ja die Sortiertheit und da verändert sich ja das Array. Aber bei diesem Algorithmus jetzt da verändert sich das Array ja gar nicht.

Ich weiß halt, dass n >= 3 sein muss damit der Algorithmus überhaupt funktioniert. Kann mir vielleicht jemand einen Ansatz geben wie ich die Korrektheit beweise?

Ich wäre euch allen sehr dankbar :)

Computer, Schule, Mathematik, programmieren, Informatik, Algorithmus, Algorithmen und Datenstrukturen
1 Antwort
Jensek81
09.05.2019, 00:52

Ternärer Baum als Pseudocode?

In dieser Aufgabe betrachten wir gewurzelte ternäre Bäume. Jeder Knoten v kann also ein linkes Kind v.L, ein mittleres Kind v.M und/oder ein rechtes Kind v.R haben. Wir möchten nun herausfinden, wie viele Knoten im Baum sind.Gebe jeweils einen rekursiven Algorithmus in Pseudocode an, der durch den Aufruf count(v0) die Anzahl n der Knoten im Baum mit Wurzel v0 bestimmt. Begründe die Korrektheit der Algorithmen.

a) Gehe für den Entwurf deines Algorithmus zuerst davon aus, dass der Baum vollständig ist, also jeder Knoten entweder genau drei Kinder oder gar kein Kind besitzt und für jedes Blatt der Weg von der Wurzel die gleiche Länge hat. Stelle eine Rekursionsgleichung für die Laufzeit auf und löse diese mithilfe des Master-Theorems. Der Algorithmus soll eine Laufzeit von o(n)haben.

b) Wie verändern sich Algorithmus und Laufzeit, wenn Sie allgemeine ternäre Bäume betrachten?

________________________________________________________

Es geht um Pseudo-Code. In der Vorlesung benutzen wir C (obwohl wir C eigentlich erst nächstes Semester lernen), also wir lassen immer Klammern auf und schließen diese erst in der nächsten oder ubernächsten Zeile und erhöhen Variablen durch i++.

Ich habe mir überlegt, weil das ganze ein ternärer Baum sein soll und die Länge gezählt wird:

var counter = 0
    for b = 0; b ≤ n; b++) {
        for (l = 1, l++) {
             l = l + 1
}
        for (m = m, m++) {
             m = m + 1
}
        for (r = r, r++) {
             r = r + 1
}
        counter = counter + 1
}

wobei b die, ich nenn's jetzt einfach mal "Oberschleife" ,für den Baum an sich ist und l, m und r jeweils Unterschleifen, wobei l = links, m = mitte, r = rechts. Glaube aber, dass ich's mir hiermit zu einfach mache.

Zudem muss das Ganze ja noch als rekursive Funktion geschrieben werden, also der Form T (n) = a * T (n/b) + f(n), wobei b in diesem Fall = 3 ist, weil es ja ein ternärer Baum ist. Aber was ist a? Man könnte ja theoretisch unendlich viele Kinderknoten haben? Oder versteh ich da was falsch?

Schule, Mathematik, Knoten, Baum, Informatik, Pseudocode, Algorithmen und Datenstrukturen
2 Antworten
computerfan001
24.08.2020, 11:04

Umgekehrte Polnische Notation / Postfix-Notation über Stack programmieren, so richtig?

Hallo,

ich soll die umgekehrte polnische Notation / Postfix-Notation in Java mit Hilfe eines Stacks programmieren. Dafür stehen mir nur folgende Informationen zur Verfügung:

public class IntegerStack {
  public boolean emptystack();
  public int head();
  public void push(int i);
  public int pop();
}

Leider zeigt ein Testfall als Fehler Folgendes an:

IntegerStack s = new IntegerStack();
String[] input = {"1", "2", "*", "3", "4", "*", "+"};
Calculator(input, s);
System.out.println(s.compareHistory(new String[] {
  "[1]",
  "[1, 2]",
  "[1]",
  "[]",
  "[2]",
  "[2, 3]",
  "[2, 3, 4]",
  "[2, 3]",
  "[2]",
  "[2, 12]",
  "[2]",
  "[]",
  "[14]",
  "[]" }
));

// erwartet:
true
// erhalten:
wrong history length: target 14 - is 0
false

Ich kann diesen Fehler nicht deuten. Kann mir bitte jemand sagen, was da falsch sein soll? Ich weiß nicht, was ich beheben soll.

Anbei mein Code:

public int Calculator(String[] input, IntegerStack s) {
  s = new IntegerStack();

  for (int i = 0; i < input.length; i++) {
    switch(input[i]) {
      case "+":
        int x = s.pop();
        int y = s.pop();

      
          s.push(y + x);
        
        break;
      case "-":
        x = s.pop();
        y = s.pop();

       
          s.push(y - x);
        
        break;
      case "/":
        x = s.pop();
        y = s.pop();

      
          s.push(y / x);
       
        break;
      case "*":
        x = s.pop();
        y = s.pop();

        
          s.push(y * x);
        
        break;
      case " ":
        break;
      default:
        if (input[i] != null) {
          s.push(Integer.parseInt(input[i]));
        }
        else {
        }
        ;
      }
    }

    int z = s.pop();
    return z;
  }
Computer, Freizeit, Studium, Schule, Mathematik, programmieren, Java, Informatik, Physik, stack, Algorithmen und Datenstrukturen
3 Antworten
PrettyRANDOM
03.10.2022, 16:07

Informatik "Rätsel"?

Programmiersprache: JavaWie stellt man bei der Datenstruktur Queue Objekte nicht hinten sondern vorne an? Also vom Code her.Kontext/Hintergrund von dieser Frage: Ich habe eine PriorityQueue. Doch dann soll plötzlich ein neues Objekt hinzugefügt werden, welches eine höhere Priorität als alle bereits in der PriorityQueue vorhandenen Objekte hat. (Da das hinzuzufügende Objekt ja die höchste Priorität hätte, müsste es ganz vorne in der PriorityQueue stehen).
Natürlich habe ich mir, bevor ich die Frage hier auf GF stelle, selbst nachgedacht, wie man das Problem lösen könnte. Bis jetzt ist mir aber nur

first = new QueueInhalt(pObject, pPriority);

eingefallen. Ich komme beim setNext(), also wenn der neue, eingefügte, Knoten QueueInhalt seinen Next - Link auf den ursprünglich an derselben Stelle (ganz vorne) gewesenen Knoten QueueInhalt setzt. (Wenn man ein Objekt hinten anstellt, schön nach FIFO halt, hätte ich kein Problem mit dem Setzen der next - links und first - links. Aber vorne anstellen? Keine Ahnung, wie das gehen soll.)
Danke und ein "Hilfreich" schonmal für eure Antworten😀

public void add(ContentTypePerson pObject, int pPriority) {
    QueueInhalt inhaltsobjekt = new QueueInhalt(pObject, pPriority);
    if (first == null) { //Wenn kein Objekt in der Queue vorhanden ist
    first = new QueueInhalt(pObject, pPriority);
    } else if (pPriority > first.getPriority()) {
    first = new QueueInhalt(pObject, pPriority);
//...?    
    }
}
Software, Schule, IT, programmieren, Java, Datenstrukturen, Informatik, Softwareentwicklung, Algorithmen und Datenstrukturen
2 Antworten