Die Mathe-Redaktion - 25.11.2017 06:25 - Registrieren/Login
Auswahl
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden oder den Newsletter bestellen.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 339 Gäste und 1 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
 
Suchwörter   (werden UND-verknüpft)
Keines der folgenden   keine eigenen Beiträge
Name des Autors 
nur die Themen
Forum 
 Suchrichtung  Auf  Ab Suchmethode  Sendezeit Empfehlungbeta [?]
       Die Suche erfolgt nach den angegebenen Worten oder Wortteilen.   [Suchtipps]

Link auf dieses Suchergebnis hier

Forum
Thema Eingetragen
Autor

Theoretische Informatik
Universität/Hochschule 
Thema eröffnet von: kaffi
Halteproblem auf leerem Band  
Beitrag No.3 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2014-06-19
xycolon
 

Hi kaffi,

was genau ist deine Fragestellung? Zunächst fragst du, ob du das Halteproblem verstanden hast.

Das Halteproblem ist die folgende Fragestellung: "Gegeben ist eine Turingmaschine und eine Eingabe. Hält die Maschine wenn, ich sie auf der Eingabe starte?".

Das Halteproblem auf leerem Band ist ein Spezialfall davon: "Gegeben ist eine Turingmaschine und die spezielle Eingabe '' (nichts). Hält die Maschine wenn, ich sie auf der leeren Eingabe starte?"


Du versuchst einen Widerspruch zu erzeugen, zu was? Um damit die Unentscheidbarkeit des Halteproblems auf leerem Band zu zeigen?


Dann musst du das Präzisieren, dann ist H die Turingmaschine, die das Halteproblem auf leerem Band löst. Weil man das annimmt, gibt diese Maschine 1 oder 0 zurück, je nachdem. Sie geht dann aber _nicht_ in eine Endlossschleife.


Die Idee mit dem Widerspruch ist relativ leicht: Man konstruiert eine Turingmaschine G, die folgendes macht:
Sie erhält eine Turingmaschine als Eingabe und außerdem eine Eingabe x für diese originale Turingmaschine.

Nun konstruiert G eine neue Turingmaschine, die folgendes macht: sie schreibt die Eingabe x auf ein leeres Band und verhält sich dann so, wie die Eingabemaschine.

Das heißt: die Eingabemaschine macht auf der Eingabe x genau das gleiche, wie die neue Turingmaschine auf '' (nichts).

Das ist ein widerspruch: Denn wenn man das Halteproblem auf dem leeren Band lösen könnte, hätte man damit auch das Halteproblem gelöst!

Sonstiges
Universität/Hochschule 
Thema eröffnet von: Cube_Max
65537-Eck als Bilddatei  
Beitrag No.4 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2014-02-26
xycolon
 

2014-02-26 09:49 - ZetaX in Beitrag No. 3 schreibt:
Wenn du das als Vektorgrafik speicherst, dürftest du das ganze in rund 1 MB bekommen. Ein Kreis, 65537 Koordinaten, ein wenig mehr Daten, das ist alles.

Der Wikipedia-Artikel enthält eine svg-Datei, die 1,8 MB groß ist. Also hast du gut geschätzt wink

Algorithmen / Datenstrukturen
Universität/Hochschule 
Thema eröffnet von: flo_yd
aufsteigende Zahlenfolge in AVL-Baum einfügen in linearer Zeit  
Beitrag No.5 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2014-02-26
xycolon
 

ja, das war meine idee. nun müsstest du nur noch beweisen, dass das balanciert ist.

Algorithmen / Datenstrukturen
Universität/Hochschule 
Thema eröffnet von: flo_yd
aufsteigende Zahlenfolge in AVL-Baum einfügen in linearer Zeit  
Beitrag No.3 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2014-02-25
xycolon
 

ja, das hast du richtig verstanden.

ich gehe davon aus, dass das mit der aufgabenstellung vereinbar ist. außerdem glaube ich nicht, dass man mit balancierungsoperationen auf lineare laufzeit kommt.

Algorithmen / Datenstrukturen
Universität/Hochschule 
Thema eröffnet von: flo_yd
aufsteigende Zahlenfolge in AVL-Baum einfügen in linearer Zeit  
Beitrag No.1 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2014-02-25
xycolon
 

hi flo,

da die Folge der Zahlen bereits sortiert ist, kannst du Effizient auf bestimmte Elemente zugreifen und so einen anderen Ansatz als den mit der Liste wählen.

Überlege, welches Element an die Wurzel gehört und wie du leicht darauf zugreifen kannst! Anschließend rekursiv fortfahren.

Technische Informatik
  
Thema eröffnet von: viertel
Kann Handy App auf den kompletten WLAN Datenverkehr zugreifen?  
Beitrag No.19 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2013-12-02
xycolon
 

Die virtuellen privaten Netzwerke für Gastzugang können nicht nur Fritzboxen sondern zahlreiche weitere Router, z.B. die neueren Modelle von TP-Link und alles wo custom-firmwares drauf laufen (DD-WRT oder open-WRT).

In nicht-modifizierten Geräten (iOS und Android, Windows weiß ich nicht, vermute es aber auch) kann man nicht einfach den Verkehr mitschneiden. Auf gerooteten/gejailbreakten Geräten ginge das schon. Mitgeschnittene WLAN-Kommunikation wäre dann aber verschlüsselt.

Dies Betrifft nur die kabellose Kommunikation, die Ethernet-Daten werden vom Router nicht über WLAN-Weitergeleitet, wenn beide Empfänger das Ethernet nutzen.

Programmieren
Universität/Hochschule 
Thema eröffnet von: NikeAir22
Java: Multiple Choice Fragen  
Beitrag No.2 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2013-08-14
xycolon
 

2013-08-12 18:04 - NikeAir22 im Themenstart schreibt:
   
   
Hier meine Gedanken zu einigen der Fragen:

   
Zu 01: Wrapper-Klassen sind ja Immutable (unveränderlich), daher ist das doch falsch?

Zu 05: Wrapper-Klassen sind Immutable, also sind sie doch auch final, oder etwa nicht?.

Zu 07: Mehrere Pakete können Klassen mit den gleichen Namen haben, aber die Klasse Peter
       dem Paket Uschi kann doch nicht auch gleichzeitig im Paket Klaus sein, stimmts?
       
Zu 10: Die Klasse String ist ja auch eine Wrapper-Klasse und ist daher Immutable, oder ist
       hier wohl eher der primitive Datentyp gemeint?
       
Zu 11: Enum-Klassen in Java sind, wenn ich mich recht entsinne, Immutable. Bin mir nicht ganz sicher
01: Ist genau die Definition von Immutable.

05: Die Wrapper-Klassen (solange du nur die von Java für die Standardtypen bereitgestellten meinst) sind final. Solche Sachen kannst du einfach im SDK nachschauen.

07: eine Klasse ist in genau einem Paket.

10: Siehe SDK.

11: Enum ist immutable.

Mache dir klar, was Immutable heißt: Immutable impliziert nicht, dass eine Klasse final ist. Insbesondere muss man beim vererben von immutables aufpassen, dass sie immutable bleiben (oder das in der API-Beschreibung deutlich kenntlich machen).

EDIT: ich habe gerade noch mal nachgesehen. In verschiedenen Texten wird empfohlen, immutable-Klassen gleichzeitig zu finalisieren. Da müsstest du mal in deine Vorlesungsunterlagen schauen.

Zu 13: ich weiß nicht, wie das gemeint ist. IMHO lassen sich von anonymen Klassen Objekte erstellen, man braucht ja auch new zum Erzeugen. Man kann halt nicht selbst weitere Instanzen generieren. Die Antwort hängt also von der genauen Bedeutung der Frage ab. ("Lassen sich" würde ich allgemein deuten.)

gruß,
xycolon

[ Nachricht wurde editiert von xycolon am 14.08.2013 14:13:34 ]

Komplexitätstheorie
Universität/Hochschule 
Thema eröffnet von: snooc
Registermaschinen | uniformes/logarithmisches Kostenmaß  
Beitrag No.1 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2013-07-10
xycolon
 

Hallo Snooc,

bei 1) geht es um die Platzkomplexität.

Um das abzuschätzen muss man sich folgendes überlegen: was kann die RAM machen, so dass möglichst viel Platz verbraucht wird? Sie wird in jedem Schritt eine möglichst große Zahl berechnen und in ein neues Register schreiben. Die größte mit Grundoperationen berechenbare Zahl in <math>f(n)</math> Schritten ist (denke ich) etwa <math>n^{2^{f(n)}}</math>. Das ganze wird dann in Binärdarstellung gespeichert, also werden <math>O(f(n))</math> Registerplätze belegt die jeweils mit <math>O\left(2^{f(n)}\cdot log(n)\right)</math> Bits belegt sind.

bei 2) ist es ähnlich, die Zeit hängt ja im logarithmischen Kostenmaß von der Zahldarstellung und damit vom benötigten Platz ab.

gruß,
xycolon

Formale Sprachen & Automaten
Universität/Hochschule 
Thema eröffnet von: bandchef
Warum soll diese Sprache regulär sein?  
Beitrag No.7 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2013-07-10
xycolon
 

Eine wesentliche Eigenschaft von regulären Sprachen ist, dass sie nur endlich viele Zustände abbilden können (da sie ja von endlichen Automaten simuliert werden können).

Aus dieser Eigenschaft folgt insbesondere, dass sie nicht zählen können. Wenn man zählt, hat man irgendwann weiter gezählt als die vorhandenen Zustände. Daher ist z. B. die Sprache <math>L=\{1^n 0^n | n \in \mathbb N\}</math> nicht regulär, wo man ja nach <math>n</math> Einsen genausoviele Nullen zählen muss.

Die hier vorgegebene Sprache hat diese Eigenschaft nicht: hier soll nur geprüft werden, ob <math>n+m</math> gerade ist, was sich in konstant vielen Zuständen (im Wesentlichen: Summe ist gerade gerade/ungerade) modellieren lässt, der genaue Wert von <math>n</math> und <math>m</math> ist egal.

Mit dieser Anschauung kann man oftmals bereits erkennen, ob eine Sprache regulär ist, oder nicht.

Gruß,
xycolon

Formale Sprachen & Automaten
Universität/Hochschule 
Thema eröffnet von: bandchef
Warum soll diese Sprache regulär sein?  
Beitrag No.4 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2013-07-08
xycolon
 

n und m sind verschiedene Zahlen. Du könntest übrigens einfach einen DFA für die Sprache angeben, das ist für diese Sprache nicht sehr schwer.

gruß,
xycolon



[Die Antwort wurde nach Beitrag No.2 begonnen.]

Komplexitätstheorie
Universität/Hochschule 
Thema eröffnet von: bandchef
P-NP-Aufgabe  
Beitrag No.4 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2013-07-04
xycolon
 

Das Konzept einer Polynomialzeitreduktion ist relativ einfach.

Erstmal ne Reduktion: Du hast zwei Probleme gegeben, A und B und willst fed-Code einblenden zeigen, also generell sowas wie "A ist nicht schwieriger als B". Die Idee ist, dass A dann nicht schwieriger ist, wenn man B zur Lösung nutzen kann.

Man erstellt also einen Algorithmus, der eine Eingabe von A nimmt, damit irgendwas macht, so dass eine Eingabe von B rauskommt.

Anschließend ruft man B auf und gibt die Antwort von B als Lösung für A aus. (Wichtig: man darf nachher _nichts_ mehr am Ergebnis ändern!)

Damit das klappt, muss natürlich gelten: Die Eingabe von A wird genau so umgewandelt, dass gültige A-Eingaben gültige B-Eingaben werden und andersrum.

Wenn deine Berechnung in Polynomialzeit geht ist das dann eine Polynomialzeitreduktion.

gruß,
xycolon

Programmieren
Universität/Hochschule 
Thema eröffnet von: Denl
Pascal: begin end  
Beitrag No.22 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2012-10-26
xycolon
 

2012-10-25 17:37 - Calculus in Beitrag No. 14 schreibt:
2012-10-25 15:19 - weird in Beitrag No. 11 schreibt:
Na, dann bin ich mal froh, dass es wenigstens Leidensgenossen wie chryso gibt, die sich mit dieser Vielzahl von unnütz gesetzten Klammern in C-Programmen auch nicht anfreunden können. In meinem "Wirkungsbereich" würde ich sowas jedenfalls nicht zulassen, da für mich Übersichtlichkeit absolute Priorität hat.


Also fändest du solch einen Code vollkommen in Ordnung?
C
int main(int argc, char* argv[]){
    for(int i = 0 ; i < 2 ; ++i)
        for(int j = 0 ; j < 2 ; ++j){
            // Hier kommen 100 Zeilen Code
        }
}


Generell sollte man überlegen, ob "100 Zeilen Code" nicht in eine Funktion/Methode gehören, und ob man das eventuell noch feingliedriger einteilen kann.

Gegen die Klmmerung habe ich persönlich nichts, mache ich auch so, ich kann weird daher verstehen.

Wiedersprechen muss ich ihm aber dabei, dass das eine unsinnige Vorgabe ist:
Buris Argument, dass man den Code später verändern muss, ist sehr wichtig. Es tritt in Projekten häufig auf, dass etwas verändert werden muss. Und wenn man dann einfach eine Zeile einfügt, ohne die Klammern hinzuzufügen gibt es einen gravierenden Fehler. Wenn man an die Klammer denkt, tritt das Problem mit dem Suchen auf. Wenn man sich aber daran hält, die Methoden klein zu halten, ist das kein wirkliches problem wink

In realen Produktivsystemen sind die Vorgaben an den Code nicht, dass man ihn schön findet oder so, sondern, dass der Code leicht lesbar ist (von allen Projektmitgliedern), leicht wartbar/erweiterbar und nach möglichkeit die meisten Fehler automatisch vermieden werden. Darum wird dort längerer Code, der Klarer ist bevorzugt. Der compiler optimiert eh alles ganz gut wink

gruß,
xycolon

Komplexitätstheorie
Universität/Hochschule 
Thema eröffnet von: Chris311
MAX SNP  
Beitrag No.3 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2012-10-05
xycolon
J

Hey, ich hab mir das mal angesehen.

Die Probleme in Max SNP sind reduzierbar aufeinander bezüglich L-Reduktion. Das ist ein sehr starkes Reduktionskonzept. Der Reduktionsfaktor bei L-reduzierbaren Problemen kann sich zwar unterscheiden, aber es können alle Lösungen von einem Problem auf Lösungen des anderen abgebildet werden.

Daraus folgt dann, dass für alle Probleme in Max SNP ein PTAS existiert, wenn nur für ein einziges vollständiges ein PTAS existiert.

Zusammen mit dem Resultat von Arora, dass es keinen PTAS für Max 3-SAT gibt, folgt daraus, dass die Probleme in Max SNP alle nur konstant approximierbar sind. L-Reduktionen erhalten konstante Approximierbarkeit, nur die Approximationsgüte ändert sich vielleicht.

viele Grüße,
xycolon



Komplexitätstheorie
Universität/Hochschule 
Thema eröffnet von: Chris311
MAX SNP  
Beitrag No.1 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2012-10-04
xycolon
J

Hallo,

Experte auf dem Gebiet bin ich auch nicht, aber folgendes kann ich dir sagen:

Max SNP ist keine Teilmenge von NP, sondern von NPO. Außerdem ist Max SNP Teilmenge von APX, das heißt, für jedes Problem in Max SNP gibt es einen Approximationsalgorithmus mit konstantem Approximationsfaktor.

Weiterhin ist der Abschluss von Max SNP unter PTAS-Reduktionen ganz APX. Das heißt, dass es für jedes Problem in APX einen PTAS gibt, so dass das Problem auf ein Max SNP-Problem reduziert werden kann.

Ob alle Probleme in Max SNP vollständig sind, kann ich nicht sagen. In dem von dir verlinkten Artikel finde ich dazu aber auch keine Informationen. Oder ich verstehe sie nicht wink

gruß,
xycolon

Berechenbarkeitstheorie
Universität/Hochschule 
Thema eröffnet von: Simon_St
SAT-Problem, disjunktive und konjunktive Normalform  
Beitrag No.3 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2012-10-04
xycolon
 

2012-10-01 14:06 - Simon_St im Themenstart schreibt:
Hallo,
für das SAT-Problem, welches die Erfüllbarkeit einer aussagenlogischen Formel prüft, wurde bis dato kein effizientes Lösungsverfahren mit polynomieller Laufzeit gefunden.
Das Problem wird häufig auf die konjunktive Normalform bezogen. Wäre die Formel in disjunktiver Normalform, könnte man ihre Erfüllbarkeit (meines Wissens) leicht prüfen.
Meine Frage nun:

1. Erfordert es exponientiellen Aufwand eine Formel von der konjunktiven Normalform in die disjunktive Normalform zu bringen?

2. Hat jede aussagenlogische Formel überhaupt eine konjunktive und disjunktive Normalform?

Du kannst dir 1. übrigens leicht so überlegen: Wenn es möglich wäre, ohne exponentiellen Aufwand in disjunktive Normalform umzuformen, wäre das ein Polynomialzeitalgorithmus.

Das heißt nicht, dass es nicht Formeln gibt, die leicht in disjunktive Form umgeformt werden können. Aber allgemein geht es eben nicht.

gruß,
xycolon

Tagesgespräch
  
Thema eröffnet von: Bernhard
Schwere Sicherheitslücke in fast allen Versionen des Internet Explorer  
Beitrag No.19 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2012-09-21
xycolon
 

2012-09-21 09:25 - OmmO in Beitrag No. 17 schreibt:
Ich habe neulich Windows 95 installiert und konnte damit nicht surfen.
Nicht einmal die google-Hauptseite konnte mit dem Internetexplorer Version 2 (oder 1?) dargestellt werden.
Es war auch nicht möglich, einen anderen Browser zu laden.

Hast du noch so einen alten Rechner, auf dem man das installieren kann? Oder hast du eine virtuelle Maschine benutzt?

Ich wollte letztens auch mal ein paar alte Betriebssysteme in virtuelle Maschinen installieren umd zu sehen wie es früher war biggrin

gruß,
xycolon

Tagesgespräch
  
Thema eröffnet von: Bernhard
Schwere Sicherheitslücke in fast allen Versionen des Internet Explorer  
Beitrag No.8 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2012-09-20
xycolon
 

2012-09-19 21:03 - Bernhard in Beitrag No. 4 schreibt:
Hallo!

Auch bei Java soll eine Sicherheitslücke entdeckt worden sein:
Vulkanausbruch auf Java 

Hier wird sie sich wahrscheinlich noch schlimmer auswirken, da der Fehler hier plattformübergreifend und browserunabhängig ist. Man kann also auch nicht ausweichen. Außerdem soll der Mißbrauch im Code durch eine Antivirensoftware sehr schwer zu erkennen sein.

Ich frage mich allerdings, wieso man in diesem Zusammenhang nicht nur darauf aufmerksam macht, daß die Lücken sehr leicht zu knacken sind bzw. es schon solche Fälle gegeben hat, sondern auch noch, daß im Internet bereits ein Code dazu zu finden ist. confused  
Außerdem - so meine ich - werden die Fehler zu genau beschienen, ja teilweise sogar Codeausschnitte gezeigt.
Das fordert doch geradezu heraus, es selber zu versuchen! frown

Viele Grüße, Bernhard


Neuere Versionen von Firefox erkennen gefährliche Java-Versionen und deaktivieren diese. Hab ich letztens festgestellt, als eine Java-Seite nicht lief und ich mich wunderte, da ich Java installiert hatte wink Sie lassen sich auch nicht einfach wieder aktivieren (ich weiß nicht, ob es mit Hacks funktioniert).

gruß,
xycolon

Sonstiges
Schule 
Thema eröffnet von: Ehemaliges_Mitglied
Linux  
Beitrag No.18 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2012-09-16
xycolon
 

Nix davon biggrin

Da ich "Vist" aber nicht kenne und scheinbar nur diese Alternativen zur Wahl stehen: 7.

Matheplanet
  
Thema eröffnet von: matroid
Neue Senioren  
Beitrag No.10 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2012-08-25
xycolon
 

schon wieder ist es so weit smile

auch von mir ein fettes gz an die neuen senioren smile

Technische Informatik
  
Thema eröffnet von: hingiswiss
Microsoft Exchange Server nur auf Microsoft Server installierbar?  
Beitrag No.1 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2012-08-03
xycolon
 

Kurz: nur server.

Lang: hier ist eine  übersicht

gruß,
xcolon
  

Sie haben sehr viele Suchergebnisse
Bitte verfeinern Sie die Suchkriterien

[Die ersten 20 Suchergebnisse wurden ausgegeben]
Link auf dieses Suchergebnis hier
(noch mehr als 20 weitere Suchergebnisse)

-> [Suche im Forum fortsetzen]
 
 

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2017 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]

used time 0.333541