Mein informatik Prof hat einen Beweis in seinen Folien den ich einfach nicht verstehe, weil mir offensichtlich einige Mathe Grundlagen fehlen. Kann mir evtl. Jemand dazu helfen? Evtl. Einen Tipp oder welche Rechenregeln ich mir anschauen müsste oder einen guten link dazu. Würde mich freuen :) Der term nach dem ersten Gleichheitszeichen ist dabei noch klar. Ich weiß wie das Summenzeichen funktioniert. Aber wie ist das j in den exponent gekommen und wieso anschließend k/2^k? Was hat das mit dem unendlich zu tun? Also ich freue mich über jede Form der Unterstützung :) Liebe Grüße

Hilfe zu einem Beweis in Informatik?

Mein informatik Prof hat einen Beweis in seinen Folien den ich einfach nicht verstehe, weil mir offensichtlich einige Mathe Grundlagen fehlen. Kann mir evtl. Jemand dazu helfen? Evtl. Einen Tipp oder welche Rechenregeln ich mir anschauen müsste oder einen guten link dazu. Würde mich freuen :)

Bild zum Beitrag

Der term nach dem ersten Gleichheitszeichen ist dabei noch klar. Ich weiß wie das Summenzeichen funktioniert. Aber wie ist das j in den exponent gekommen und wieso anschließend k/2^k? Was hat das mit dem unendlich zu tun?

Also ich freue mich über jede Form der Unterstützung :)

Liebe Grüße

2 Antworten

Stnils

10.05.2018, 12:59

"Aber wie ist das j in den exponent gekommen und wieso anschließend k/2^k? "

Die Summe wurde umsortiert. Der erste Summand ist nach der Umsortierung der letzte, der zweite der vorletzte Summand, usw.

"wieso anschließend k/2^k"

Potenzgesetze . 2^(j-k-1) = 2^(j-1) * 1/2^k . Da es im ersten Faktor 2^(j-1) keine Abhängigkeit von k gibt, kannst du den Faktor auch aus der Summe herausziehen.

"Was hat das mit dem unendlich zu tun?"

Dort wurde die Reihensumme angegeben. Da man in der Reihensumme "bis unendlich summiert" und die obere Grenze der Summe aus dem Beweis j-1 < ∞ ist, wird in dem Beweis in der folgenden Zeile mit <= nach unten abgeschätzt.

KarlRanseierIII

Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer

Informatik

10.05.2018, 12:41

Anscheinend weiß Du nicht so wirklich, wie das Summenzeichen funktioniert, sonst wüßtest Du, wie das j dort hinkam, aber gut:

Für k=1 ergibt sich 2^0- das letzte Summenglied ist k=j-1, daher ist 2^(k-1) eben 2^(j-1-1)=2^(j-2).

Anschließend werden die Summanden nur neu zusammengefasst.

In meinem Physikbuch taucht im Fließtext immer wieder die Abkürzung i.a. auf. Zum Beispiel "... entsteht durch Überlagerung von i.a. unendlich vielen Wellen".

Mein Physik-Prof verwendet auf seinen Folien gerne die Abkürzung i.A. Das steht dann für "in Annäherung". In dem Buch würde diese Bedeutung auch meistens passen, aber dann müsste das A ja groß geschrieben sein.

Sonst kenne ich nur noch "im Allgemeinen", aber auch da müsste das A ja groß sein, und "im Auftrag", aber das passt natürlich überhaupt nicht.

...zur Frage

Pivotwahl bei Quicksort und Quickselect?

Guten Abend,

ich bräuchte mal kurz Hilfe bei folgenden Aufgaben, bitte. Es geht mir darum, dass ich einfach nicht versteh', was zu tun ist. Wir hatten in der Vorlesung den Quicksort-Algorithmus. Ich weiß, dass bei Quicksort das zu sortierende Array in immer kleiner Teilarrays eingeteilt wird, wobei das größere Array zuerst auf den Stack gelegt wird. Das Pivotelement ist entweder das linke oder das rechte und man setzt dann links und rechts einen Pointer am entsprechenden Teilarray. Ist das erste Element des zu sortierenden Teilarrays, welches größer als das Pivotelement ist, gefunden, und es findet sich vom rechten Pointer aus das erste Element, welches kleiner als das Pivotelement ist, so werden diese vertauscht. Bei Überkreuzungen tausche jenes Element auf dass der linke Pointer zeigt mit dem Pivotelement. So hatten wir's zumindest in der Vorlesung (Partitionswahl). Zu den Aufgaben

Aufgabe 1

Ein wichtiger Faktor für die Laufzeit von Quicksort und Quickselect (das Auswahlverfahren des k-kleinsten Elements analog zu Quicksort) ist die Wahl des Pivotelements. Das Pivotelement sollte die zu sortierende Folge in zwei möglichst gleich große Teilfolgen aufspalten.Gegeben sei eine unsortierte Folge mit n paarweise verschiedenen Elementen. Weiterhin sei r(x) die Position des Elements x in der sortierten Folge. Eine mögliche Strategie für die Pivotwahl ist:Wähle uniform zufällig 7 Elemente aus der Eingabefolge und gib das viertkleinste als Pivotelement aus. Dabei können Elemente in der Auswahl mehrmals vorkommen (Ziehen mit Zurücklegen)

.a) Berechne die Wahrscheinlichkeit für das Ereignis: n/4 < r(Pivot) ≤ 3n/4.

b) Nach wie vielen unabhängigen Wiederholungen der Pivotwahl ist zu erwarten, dass der Rang des Pivotelements das erste Mal außerhalb des Intervalls aus Aufgabenteil a) liegt? Hinweis: Du darfst annehmen, dass n= 4·kfür ein k∈N.

Aufgabe 2

Konstruiere eine Folge der Länge7, so dass Quickselect bei Verwendung der Pivotfunktionpivot(links, rechts) =⌈(links+rechts)/2⌉ auf der Suche nach dem viertgrößten Schlüssel die Problemgröße stets nur um 1verringert. Der Algorithmus soll insgesamt also sieben Schritte benötigen, bis er terminiert. Wende Quickselect auf Ihre Folge an, um die Korrektheit zu zeigen

Ansatz Ich verstehe hier nicht, wie n/4 gemeint ist. Wir hatten in der Vorlesung immer das Pivotelement ganz links oder ganz rechts. Jetzt steht hier "Pivot(links,rechts) = [(links+rechts)/2]. Greift man sich also da Element in der Mitte? Das ist bei einer Folge der Länge 7 doch nicht möglich, oder? WIe gehe ich allgemein vor um eine solche Folge zu finden.

Jensek81

...zur Frage

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?

...zur Frage

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 :)

...zur Frage

Mathematik/Informatik Studium inwiefern Beweise können?

Beispielsweise stehen im Skript für die Lineare Algebra viele Formeln. Unter diesen Formeln meistens auch ein Beweis, der erklärt wie man auf diese Formel gekommen ist.
Ist dieser Beweis nur für das Verständnis oder muss man diesen Beweis können, um später die Formel benutzen zu können oder so?
Zum Beispiel gilt: A ⊆ B ∧ B ⊆ A ⇔ A = B
Braucht man den Beweis dafür oder ist der nur fürs Verständnis?

...zur Frage

Bei welcher Ausbildung/Studium lernt man mit Assembler zu programmieren und gleichzeitig mit Elektronischen Bauteilen zu arbeiten?

Hey,
Also ich werde nächstes Jahr meine FHR haben und ich weiss immer noch nicht so genau wo es danach hingehen soll.
Also es soll was im Wissenschaftlichen Bereich sein, mir liegen die Fächer Mathematik, Informatik und Physik.
Ich habe bereits einige Erfahrungen in der Informatik und Analisis(mit y).
Ich interessiere mich wahnsinnig für Elektronik, gleichzeitig auch für die Programmierung.
Was ich unbedingt wissen möchte ist, wie ein Computer funktioniert, nicht nur Theoretisch sondern auch wie die einzelnen Elektronischen Bauteile miteinander arbeiten ich möchte auf unterster Ebene Programmieren lernen, also mit der Maschinensprache.
Klingt evtl. sehr naiv, weil ich nicht mal im Gymnasium war und nicht der Einser Schüler bin, aber ich will es trotzdem so haben.

Was genau muss ich dafür studieren bzw. zu was muss ich mich ausbilden lassen?

Ich bedanke mich schonmal im Voraus für hilfreiche Antworten, die beste wird Ausgezeichnet ^^

...zur Frage

Landau Symbole Matheaufgabe; wie lösen?

Was muss ich wissen, um so eine Aufgabe zu lösen? Anscheinend hab ich irgendwas verpasst und jetzt habe ich keine Ahnung, was ich googlen könnte oder sonstiges um mir das Wissen für diese Aufgabe aneignen zu können.

Ich weiß nur, dass das durchgestrichene O heißt, dass die Funktionen irgendwie gleich verlaufen. Das Hufeisensymbol heißt glaube ich dass die Funktion kleiner ist und das große O größer, aber ist wahrscheinlich sowieso falsch was ich sage.

...zur Frage

schlauste Art ähnliche Wörter zusammenzufassen(python)?

Hallo, ich habe die Aufgabe bekommen Kopierrechte, hier als BSP. copyR1-20, zusammenzufassen. Wenn ich mit meiner "Ähnlichkeitsfunktion" über die Liste gehe gibt diese mir die Liste für das entsprechende Kopierrecht zurück von 100, genau gleich bis 0 absolut verschieden. Nehmen wir also mal an meine Ähnlichkeitsfunktion macht Sinn und es kommen logische Werte raus. Gibt es hier ein Statistisches Verfahren um die ähnlichsten Kopierrechte in einer Gruppe zusammenzufassen?

Bislang schaue ich einfach Kopierrecht1 an, nehme alle Kopierrechte über mein Limit 86 hinzu und nenne das meine Gruppe. Das Führt jedoch zu Problemen, wenn z.B. Kopierrecht1 ähnlich zu Kopierrecht 2 und 3 ist, Kopierrecht 4 aber nur ähnlich zu Kopierrecht 2 ist. Hier weiß ich nicht wie ich die Gruppen bilden soll.

Also zu meiner Frage:

Ich soll das in Python implementieren.

Gibt es eine systematische Möglichkeit durch z.B. einen Clusteralgorithmus die besten Gruppen hier zu bilden? (Die Tabelle ist nicht ausgefüllt, sie geht natürlich noch weiter)

Vielen Dank im Vorraus

...zur Frage

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?

...zur Frage

Themenbereiche Informatik - Eure Lieblingsthemen?

Es kann sein, dass ich nicht alles angegeben habe, aber dafür gibt es den Bereich "Anderes".

Danke Euch.

...zur Frage

Entscheidungsbaum für Quicksort und HEapsort zeichnen?

Wie kommt man darauf, was man in die Knoten schreiben muss?

Also warum ist bei Quicksort z. B. als erstes 1:3, dann drunter bei den Kinderknoten 2:3 und 2:3, also woher weiß ich, welche Sachen ich in die Knoten zu schreiben habe, also warum z. B. bei der Wurzel gerade 1:3 und nicht z. B. 1:2 oder so?

...zur Frage

Unterschied zwischen Kreis und Zyklus Graphentheorie?

Moin, Titel sagt alles. Was ist der unterschied zwischen einem Kreis und einem Zyklus in einem Graphen?

...zur Frage

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;
  }

...zur Frage

Komplexität von Funktion bestimmen?

Das ist die Funktion. Leider gibts für die Aufgabe keine Lösung, aber ich hätte gesagt, dass die innere Schleife log_2(n) Höchstens log_2(n) Durchläufe hat, weil k ja immer mindestens halbiert wird. Zusammen mit der äußeren Schleife wäre das n * log n

Aber die äußere Schleife macht ja eigentlich nichts, wenn k = 0 ist. Muss das n dann trotzdem mitberechnet werden oder würde hier auch ein log n reichen, sodass es auf log^2 n rauslaufen würde?

...zur Frage

Was möchtest Du wissen?

Deine Frage stellen