Verwandte Themen

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
FelixFragtMathe
21.04.2022, 09:17
Was passiert wenn man eine Grafikkarte übertaktet und haben Grafikkarten der unterschiedlichen Hersteller auch technische Unterschiede?

Nehmen wir mal die 3070 als Beispiel aber das könnte man jetzt auch mit der 3080, der 3070ti, der 3060 und so weiter machen machen. Es gibt ja mehrere Varianten der 3070 und die sind alle unterschiedlich teuer. Und zwar so unterschiedlich teuer das man denken könnte die würden sich auch technisch voneinander unterscheiden. So wie ich das aber verstanden habe wird an der Grafikkarte selbst nichts dran verändert sie unterscheiden sich also größtenteils in irgendwelchen Extras wie Beleuchtung oder in der Lüftung usw. weil die teureren Grafikkarten anscheinend übertaktet werden und dementsprechend für die erhöhte „Leistung“ auch besser gekühlt werden müssen. Aber hat das auch einen Unterschied bei der Leistung? Falls ja was passiert überhaupt wenn man eine GraKa übertaktet? Und können das alle Grafikkarten also auch die günstigeren Varianten? Und wie groß wäre dann der Unterschied? Also in FPS berechnet. Kann ich zum Beispiel mit der günstigsten RTX3070 auch die Leistung des teuersten RTX3070 erreichen? Im Endeffekt wäre es mir eigentlich nur wichtig nicht so viel Geld auszugeben und dennoch die Leistung zu erreichen die ich in den Benchmark Videos gesehen habe. Zum Beispiel ein leistungsunterschied von über 10fps wäre für mich enorm, aber einer von 5 eher nicht. Ich weiß das hängt auch von der CPU oder dem mainboard ab deshalb sagen wir mal in dem Fall wären alle anderen Komponenten gleich nur die Grafikkarte nicht.

PC, Computer, Technik, Grafikkarte, Streaming, Nvidia, Technologie, Twitch, Spiele und Gaming
3 Antworten

Meistgelesene Beiträge zum Thema Computer
Mehr meistgelesene Fragen zu Computer