# Gerade durch n Punkte



## FantastischMan (8. Jul 2021)

Entwickeln Sie einen moglichst effizienten Algorithmus, der fu ̈r eine gegebene Punktmenge P mit n Punkten mit maximal k unterschiedlichen x-Koordinaten eine Gerade findet, die durch mo ̈glichst viele Punkte aus P la ̈uf


----------



## FantastischMan (8. Jul 2021)

Muss kein Code sein reicht auch Erkältung


----------



## M.L. (8. Jul 2021)

Stichwort Interpolation (oder Methode der kleinsten Quadrate): https://de.wikipedia.org/wiki/Interpolation_(Mathematik)  (es kommt übrigens auf die formellen (Rand-)Bedingungen beim Anwenden eines Verfahrens an)


----------



## httpdigest (8. Jul 2021)

Wenn die Dimensionalität der Punkte bzw. Tupel = 2 ist (was von dir nicht spezifiziert ist), dann:









						What is the most efficient algorithm to find a straight line that goes through most points?
					

The problem:  N points are given on a 2-dimensional plane. What is the maximum number of points on the same straight line?  The problem has O(N2) solution: go through each point and find the number...




					stackoverflow.com
				




Der Zusatz, dass es höchstens `k` Tupel mit unterschiedlicher x-Koordinate gibt, finde ich allerdings interessant. Wenn z.B. in einem konkreten Fall `k=0` ist, dann weisst du schon, dass die gesuchte optimale Gerade die Gleichung `x=<x>` hat (mit <x> = irgendeine der gleichen x-Koordinaten, die dann ja für alle Tupel gleich ist).
Wahrscheinlich gilt das sogar für einen Grenzwert für `k < n/2`.

Wenn `k` gross ist (oder `k = n`), könnten die Tupel immer noch auf einer Geraden liegen. Das wiederum ist dann das Problem, was vom referenzierten Stackoverflow-Artikel angesprochen wird.


----------



## LimDul (8. Jul 2021)

Mal ein paar Random Gedanken:
Unter O(n log n) sollte nicht möglich sein
Es gibt zwei Lösungsklassen: 
* Einmal eine Lösung mit einer senkrechten Gerade (Sprich, x ist konstant, y ist variabel) 
* Oder eine Lösung mit einer nicht senkrechten Gerade. Diese Lösung kann man in der Form y = a*x + b schreiben

Klar ist, wenn es maximale k verschiedene X-Koordinaten gibt, kann (sofern die Punkte alle paarweise verschiedenen sind), eine Lösung der zweiten Kategorie maximal k Punkte schneiden. Das heißt, wenn ich die Punkte nach x-Koordinaten gruppiere und finde, dass es zu einer X-Koordinate mindestens k Punkte gibt, dann ist diese senkrechte Gerade die beste Lösung. Nur wenn das nicht zutrifft, muss ich überhaupt prüfen, ob eine Gerade der Form y = a*x + b mehr Punkte trifft. 

Mehr Ideen hab ich gerade so nebenbei nicht.


----------



## FantastischMan (8. Jul 2021)

okay ich habe paar weitere aufgaben üfr euch


----------



## FantastischMan (8. Jul 2021)

Berechnen Sie ein flächenmaximales 2-stabiles Dreieck mit Wurzel p1in dem Polygon aus Abbildung 15 mit dem Verfahren von Dobkin and Snyde






						Dobkin and Snyder Algorithm[3]
					

Dobkin and Snyder Algorithm[3]



					cgm.cs.mcgill.ca


----------



## kneitzel (8. Jul 2021)

FantastischMan hat gesagt.:


> okay ich habe paar weitere aufgaben üfr euch


Das ist super - Sehr nett von Dir, dass Du uns Aufgaben gibst, mit denen wir etwas üben können ...


----------



## M.L. (8. Jul 2021)

FantastischMan hat gesagt.:


> weitere aufgaben


Wer bekommt im Zweifelsfall die Note ?    Und das "Ghostwriter" nicht zuverlässig sein müssen, merkt man gerade an aktuellen Buch"kritiken"...


----------



## FantastischMan (8. Jul 2021)

Ne ich bekomme keine Note aber wir haben keine ml und ich brauche Hilfe zum lernen und habe andere Klausuren noch


----------



## Mart (8. Jul 2021)

FantastischMan hat gesagt.:


> Ne ich bekomme keine Note aber wir haben keine ml und ich brauche Hilfe zum lernen und habe andere Klausuren noch


selber machen hilft da ungemein 

du bekommst in der Klausur 1 Punkt fürs richtig sein und den Rest der Punkte der Aufgabe für deinen Ansatz ... niemand verlangt von dir dass du alle punkte kriegst


----------



## FantastischMan (8. Jul 2021)

ja danke für eure hilfe, glaube aich dass die aufgabe auch euch zu schwer ist


----------



## White_Fox (8. Jul 2021)

FantastischMan hat gesagt.:


> ...und habe andere Klausuren noch


Gib uns deine anderen Klausurvorbereitungen doch auch gleich noch mit.


----------



## Mart (8. Jul 2021)

FantastischMan hat gesagt.:


> ja danke für eure hilfe, glaube aich dass die aufgabe auch euch zu schwer ist


Nein das ist nicht der fall...

Es interessiert einfach niemanden komplette Aufgaben zu lösen hier im Forum weil das der Sinn von Übungs Aufgaben ist dass man damit übt


----------



## httpdigest (8. Jul 2021)

FantastischMan hat gesagt.:


> ja danke für eure hilfe, glaube aich dass die aufgabe auch euch zu schwer ist


Bin gespannt, wer hierdurch zuerst getriggert wird und eine fertige Lösung präsentiert. Ich denke aber, niemand, weil Leute hier nicht dumm sind.


----------



## kneitzel (8. Jul 2021)

FantastischMan hat gesagt.:


> ja danke für eure hilfe, glaube aich dass die aufgabe auch euch zu schwer ist


Ja, viel zu schwer. Aber was erwartest du auch? Das hier ist doch ein Forum für Freunde der Kaffee-Sorten von Java ...

Wende Dich doch mit sowas an ein Forum, in dem auch Leute sind, die z.B. Informatik studiert haben ... evtl. findest du sogar ein Forum, in dem auch Leute aktiv sind, die an einer Uni ihr Geld verdienen ...

Ansonsten sollten wir jetzt hier On Topic werden: Die Fragen sind immer noch nicht endgültig beantwortet:
A) Einfluss der Jahreszeiten auf den Kaffeegeschmack
B) Veränderung des Kaffeegeschmacks über die letzten 20 Jahre und der Zusammenhang mit der Entwicklung des Klimas

Aber vielleicht kannst du dazu etwas beitragen anstatt uns mit Aufgaben, die viel zu schwer sind für uns Kaffeeliebhaber, zu nerven.


----------



## Mart (8. Jul 2021)

kneitzel hat gesagt.:


> Das hier ist doch ein Forum für Freunde der Kaffee-Sorten von Java ...


Das möchte ich auch mal schwer meinen


----------



## White_Fox (8. Jul 2021)

kneitzel hat gesagt.:


> Das hier ist doch ein Forum für Freunde der Kaffee-Sorten von Java ...


Ja eben - das Logo ist doch wohl eindeutig gewählt.


----------



## Mart (8. Jul 2021)

FantastischMan hat gesagt.:


> ja danke für eure hilfe, glaube aich dass die aufgabe auch euch zu schwer ist


Also ich glaube niemand ist aktiv beleidigt


um ein Beispiel zu meiner OOP2 Klausur zu nennen (sehr kurz gefasst)
es gab 17 Punkte: (war 25% der Klausur )
man musste eine vorgegebene FXML laden
Es musste Lauffähig sein
und man musste einen Eventhandler dem Button geben

als 30 Leute durchgefallen sind von 80 durch die Klausur und wir den Prof im nächsten Semester wieder gehabt haben hat er nur indirekt gesagt ::

Er kann nicht verstehen warum so viele die Aufgabe Leer gelassen haben alleine Wenn man die Main hingeschrieben hätte eine Klasse und den Methoden Namen hätte man 5 Punkte bekommen aber die meisten haben nicht mal das gebacken gekriegt ...

hätte man den Eventhandler hingeschrieben der ein Vierzeiler war und nicht wirklich schwer
hätte man 7 Punkte bekommen zusätzlich


das zuweisen des EventHandlers und die FXML laden war das schwere dafür hats halt die Restlichen 5 Punkte gegeben... die er auch nicht erwartet hätte dass die jeder hat





Dieses Forum ist für "Gedanken Blockaden lösen" da... wenn man nicht weiter kommt und wie vor einer Wand steht oder Halt wie der Dritte Teil der Aufgabe "die schweren Sachen" wo man mal doch einen größeren Anstoß an Hilfe braucht ..zumindest habe ich so den Eindruck ...

und wie du merkst ... auf das was das Forum löst gibts die wenigstens Punkte


----------



## mihe7 (9. Jul 2021)

httpdigest hat gesagt.:


> Bin gespannt, wer hierdurch zuerst getriggert wird und eine fertige Lösung präsentiert. Ich denke aber, niemand


Kommt auf die "Lösung "an... 😈


----------



## temi (11. Jul 2021)

FantastischMan hat gesagt.:


> okay ich habe paar weitere aufgaben üfr euch





FantastischMan hat gesagt.:


> Muss kein Code sein reicht auch Erkältung


Hust! Reicht da auch eine *Erkältung*?


httpdigest hat gesagt.:


> Bin gespannt, wer hierdurch zuerst getriggert wird und eine fertige Lösung präsentiert. Ich denke aber, niemand, weil Leute hier nicht dumm sind.


Und schon hat sich ein Dummer gefunden


----------



## httpdigest (11. Jul 2021)

Und wer löst die erste Aufgabe, mit der Geraden durch möglichst viele Punkte? Na kommt schon...


----------



## White_Fox (11. Jul 2021)

temi hat gesagt.:


> Und schon hat sich ein Dummer gefunden


Ist das denn die Lösung? Ich habe das bisher so verstanden daß es um EINE Gerade geht (und dabei z.B. an Regression gedacht). Im Bild sehe ich aber fünf Geraden - wenn ich die Ränder des Dreiecks mal ausnehme.


----------



## httpdigest (11. Jul 2021)

Es gab noch eine zweite Aufgabe, die er in der Antwort in seinem ersten Post auch zitiert hat.


----------



## kneitzel (11. Jul 2021)

White_Fox hat gesagt.:


> Ist das denn die Lösung? Ich habe das bisher so verstanden daß es um EINE Gerade geht (und dabei z.B. an Regression gedacht). Im Bild sehe ich aber fünf Geraden - wenn ich die Ränder des Dreiecks mal ausnehme.


Du denkst an die erste Aufgabe, die zu schwer für uns war. Das ist die Lösung für die zweite, leichtere Aufgabe ...

Aber ist doch nett, dass neue User, die als Prüfer zu uns kommen, uns so noch eine weitere Chance eben ...

*scnr*


----------



## thecain (11. Jul 2021)

kneitzel hat gesagt.:


> neue User


Neue User oder neue Accounts?


----------



## Mart (11. Jul 2021)

ichWeißDes hat gesagt.:


> Mir ist dein Benehmen oder ob du die Rechtschreibpolizei spielen willst scheißegal. Aber der TE hat seinen Ansatz zur zweiten Aufgabe gepostet und ich habe eine Erklärung mit Lösung verlinkt. Auf meine Implementierung muss nicht zurückgegriffen werden.
> 
> Dass sich der TE nicht mehr meldet, ist schade. Ich denke, er wollte nur eine Lösung abgreifen.
> 
> Ach so, über eure Kompetenzen kann ich nicht urteilen, aber alleine der Umstand, dass ihr zwei Aufgaben nicht voneinader unterscheiden könnt, spricht nicht gerade dafür.


der Thread ist halt tod nachdem der TE nicht mehr da ist und seit dem juckts keinen mehr so wirklich deswegen kommt da eher nur noch troll hier rein


----------



## kneitzel (11. Jul 2021)

ichWeißDes hat gesagt.:


> Mir ist dein Benehmen oder ob du die Rechtschreibpolizei spielen willst scheißegal.


Warum reagierst Du dann so auf diesen einfachen Spaß? 


ichWeißDes hat gesagt.:


> Aber der TE hat seinen Ansatz zur zweiten Aufgabe gepostet und ich habe eine Erklärung mit Lösung verlinkt. Auf meine Implementierung muss nicht zurückgegriffen werden.


Das ist doch auch in Ordnung - niemand hat etwas dagegen geschrieben. (Auch wenn ich es ähnlich sehe wie @httpdiggest ... bei so einem Auftreten helfe ich der Person eher nicht mehr  )


ichWeißDes hat gesagt.:


> Dass sich der TE nicht mehr meldet, ist schade. Ich denke, er wollte nur eine Lösung abgreifen.


Wenn Du das doch selbst erkannt hast: Das macht deine Reaktion auf einen Einfachen Spaß noch viel weniger verständlich!


ichWeißDes hat gesagt.:


> Ach so, über eure Kompetenzen kann ich nicht urteilen, aber alleine der Umstand, dass ihr zwei Aufgaben nicht voneinader unterscheiden könnt, spricht nicht gerade dafür.


Und da zeigt sich dann, dass dies der neue Account von Tobias ist?


----------



## White_Fox (11. Jul 2021)

Ach, was soll man da wohl wieder sagen...


----------



## mihe7 (11. Jul 2021)

White_Fox hat gesagt.:


> Ach, was soll man da wohl wieder sagen...


LOL, das grenzt ja an Folter.


----------



## kneitzel (11. Jul 2021)

Wenn Du das noch irgendwie mit Argumenten untermauern könntest ... wieso sollte mir ein Arztbesuch helfen?

Oder hoffst Du, dass ich Tipps bekomme, wie man mit Dir besser umgehen kann?


----------



## httpdigest (12. Jul 2021)

Er wollte dich bestimmt nur fragen, ob du schon deine Corona Impfung von einem Arzt bekommen hattest, weil er um deine Gesundheit bei einer moeglichen Ansteckung (insbesondere durch die sich ausbreitende Delta Variante) besorgt ist. Ist ja eigentlich nett von ihm. Nur hat er seine Bedenken diesbezueglich vielleicht etwas unklar ausgedrueckt.


----------



## kneitzel (12. Jul 2021)

Ahh so, das ist natürlich seht nett von ihm. Da bin ich jetzt total gerührt. Toll, wie fürsorglich Leute hier sind.


----------



## kneitzel (14. Jul 2021)

ichWeißDes hat gesagt.:


> Neee, der könnte kneitzels Kopf untersuchen.  (Wenn nur Luft drin ist, muss sich keiner Sorgen machen  )


Hmm, schließt da jemand von sich auf Andere? 

Ich frage mich, was jemand für Probleme haben muss. der sich mit irgendwas angegriffen fühlt (#30) und dann meint, so hier austeilen zu müssen.. Hast Du so wenig Selbstbewusstsein? Oder was ist gerade Dein Problem? Mir soll es egal sein - Ich finde das hier einfach nur lustig.


----------



## mihe7 (14. Jul 2021)

🍿


----------

