Ein Rat an einen Selbstlerner mit rechnerischer Komplexität

Ich bin ein Mathematikstudent (ich werde sehr bald mein drittes Jahr beginnen). Ich versuche mir Rechenkomplexität beizubringen. Leider gibt es an meiner Universität keine Kurse zu diesem Thema und es gibt keine Spezialisten dafür (tatsächlich scheint es, dass meine Universität überhaupt keine Spezialisten für theoretische CS hat). Ich habe also keine andere Wahl, als das Thema selbst zu lernen. Ich habe bereits die ersten Kapitel der Komplexität von Computern durchgearbeitet: Ein moderner Ansatz [aber ich habe keine der Übungen gelöst (außer zwei oder drei im ersten Kapitel, in denen die Probleme von TM und Halting aufgezeigt werden)]

Ich habe einige Probleme mit den Übungen im Text:

1. Eine Sache ist, dass ich der Meinung bin, dass die Art des Denkens, die für die Komplexität der Berechnungen erforderlich ist, ganz anders ist als die der Mathematik, mit der ich vertraut bin (es liegt ein Schwerpunkt auf algorithmischem Denken usw. und darauf, wie man Probleme auf andere Probleme reduziert und ein TM erstellt ein anderes TM simulieren usw.), was mir schwer fällt.

   Können Sie mir helfen, diesen Reifegrad für Algorithmen, Reduzierungen usw. zu entwickeln?

2. Ein Grund für die Schwierigkeit von "1" ist, dass ich nicht weiß, inwieweit ich streng sein soll? Wenn ich zum Beispiel eine Reduktion oder eine Simulation durchführe, kann ich intuitiv erkennen, dass etwas klar ist und getan werden kann, aber die Details wären sehr, sehr mühsam, um sie tatsächlich auszuführen, und daher habe ich das Gefühl, dass ich dies nicht tue verstehe die Sache sehr gut. Der Punkt ist, dass ich weiß, dass es einen Kompromiss zwischen Strenge und intuitivem Denken geben muss. Aber da ich weder einen Führer noch einen Ausbilder habe, weiß ich nicht, wo diese Zeile sein soll.

   Wann sollte ich alle Details ausführen, wenn etwas irgendwie klar ist, und wann sollte ich mit der Intuition zufrieden sein? Es scheint, dass die Komplexität der Berechnungen viel mehr Details enthält, als normalerweise in der mir bekannten Mathematik vorhanden ist, und daher, wo sollte der Kompromiss liegen?

3. Ich frage mich, ob es eine Quelle für Übungen \ Probleme gibt, die einfacher sind als die in der Komplexität der Berechnungen bereitgestellten : Ein moderner Ansatz , mit dem ich mich mit den Grundbegriffen \ Konstruktionen usw. vertraut machen kann, bevor ich kompliziertere Übungen anpacke. Auch eine Quelle für (recht detaillierte) Beweise der Hauptsätze wäre großartig, da viele Sätze nur eine Skizze des Beweises im Text enthalten.

Für meinen Hintergrund habe ich Grundlagen der Programmierung gelernt (ich habe eine Weile in Python, C und C ++ trainiert), aber nicht viel, aber ich bin ziemlich vertraut mit Mathematik, insbesondere mathematischer Logik (bis hin zu Vollständigkeits- und Unvollständigkeitssätzen), fortgeschrittenem Satz Theorie (Forcen), Algebra (lineare, abstrakte, universelle Algebra und einige Kategorietheorien) und Grundlagen der Topologie und Realanalyse. Ich habe auch einen Kurs über diskrete Mathematik belegt (Kombinatorik + Graphentheorie).

Ich entschuldige mich, wenn meine Frage nicht zum Thema gehört, aber ich kenne keinen besseren Ort, um diese Frage vorzuschlagen als hier.

Meine Empfehlung ist, sich auf zwei Dinge zu konzentrieren: Voraussetzungen und Übung.

Voraussetzungen: Es wird schwieriger sein, die Komplexität der Berechnungen zu erlernen, ohne zuvor ein gutes Verständnis der Algorithmen zu haben. An vielen Schulen ist eine Klasse in Algorithmen eine Voraussetzung für die Klasse hinsichtlich der Komplexität der Berechnungen. Sie erwähnen, dass Sie das Gefühl haben, dass Ihnen die Reife der Algorithmen fehlt, und wer würde dies in Ihrer Position nicht tun? Es ist ein nicht triviales Fach, das Sie nicht studiert haben. Mein erster Ratschlag lautet also: Bevor Sie zu viel Zeit mit der Komplexität von Berechnungen verbringen, sollten Sie zunächst einige Zeit mit dem Studium von Algorithmen verbringen. Es gibt viele gute Algorithmen Lehrbücher und Online-Kurse (z. B. über Udacity, Coursera oder EdX). Es kann hilfreich sein, einige Zeit damit zu verbringen, dieses Material zu lernen. Sie müssen nicht jeden Algorithmus der Welt lernen, sondern versuchen, ein Gefühl für einige gängige algorithmische Techniken zu bekommen. Das Entwerfen von Reduktionen ist im Grunde das Entwerfen eines Algorithmus, daher ist dieses Wissen hilfreich. Stellen Sie außerdem sicher, dass Sie mit Korrektheitsnachweisen für Algorithmen und asymptotische Laufzeitanalysen vertraut sind.

Als nächstes üben. Niemand beginnt mit einer Fälligkeit mit Reduzierungen. Der Weg, sich damit besser vertraut zu machen, besteht darin, zu üben - machen Sie Übungen, bis Sie sich entweder mit dem Material wohl fühlen oder die Übungen eine Lücke in Ihrem Verständnis aufdecken (über die Sie dann zurückgehen und sich darauf konzentrieren können, mehr darüber zu lernen). Ohne diese Übung können Sie das Material wahrscheinlich nicht lernen.

Zum Üben kann es hilfreich sein, nach einem Online-Kurs (MOOC) zur Komplexität von Berechnungen zu suchen. Sie können Udacity, Coursera oder EdX überprüfen.

Wie streng solltest du sein? Rigoros genug, dass Sie davon überzeugt sind, dass Sie bei Bedarf alle Details eintragen können (und dass ein Mitschüler auf einem ähnlichen Studienniveau alle Details ausfüllen kann, ohne darüber nachzudenken - sie würden zustimmen, die Details auszufüllen) langwierig, aber unkompliziert und offensichtlich).

Da ich das Gegenteil bin (Informatik / Ingenieurwesen studieren, Mathematik selbst studieren), denke ich, dass ich einige Themen beleuchten kann.

Ich habe kürzlich einen Kurs über Algorithmen und Komplexitätstheorie besucht, der sich mit Algorithmen, formalen Sprachen und Komplexitätstheorie befasste. Ich denke, alle drei werden sehr wichtig sein, wenn Sie wirklich verstehen wollen, was Sie tun. Wenn Sie beispielsweise die Auswirkungen von Big-O und die Analyse von Laufzeiten nicht verstehen, werden Sie nicht wirklich verstehen, was P und NP darstellen, und es wird schwieriger sein, in andere Komplexitätsklassen zu wechseln. Wenn Sie TMs, Automaten usw. nicht verstehen, verstehen Sie keine regulären Sprachen, CFGs und die Bedeutung von entscheidbaren und rekursiv aufzählbaren Sprachen. Meine Vorschläge werden sich also aus Verbindungen ergeben, die ich aus der Informatik zur Mathematik hergestellt habe.

1. Sie haben Mengenlehre und reale Analyse genommen. Sie sollten mit der Einführung aus den meisten Ihrer Kurse vertraut sein (ein Tool, das für viele Klassenkameraden der schwierigste Teil der Algorithmusanalyse war), und Rekursion wird höchstwahrscheinlich für Sie selbstverständlich sein. Wenn es um abstraktere Objekte geht, die nicht direkt miteinander verbunden sind, wird sich eine starke Basis in der abstrakten Algebra (und alles andere) als großer Vorteil herausstellen, den Sie haben. Gruppen, Ringe usw. sind algebraische Objekte, die eine gewisse Struktur enthalten und zwischen denen sich Karten und Morphismen befinden. Turing-Maschinen und Automaten sind Rechenstrukturen, die einige Strukturen und Regeln enthalten und Transformationen zwischen sich aufweisen (Thompsons Konstruktion für reguläre Ausdrücke in NFAs, Multi-Tape-TMs in ein einzelnes Tape-TM).

2. Ich bin mir nicht sicher, was genau Sie fragen, aber wenn Sie streng sein können, tun Sie es. Es gibt einige Techniken, die in der Mathematik verwendet werden und in vielen Konstruktionen verwendet werden (reale Analyse unter Verwendung von Epsilon-Delta-Beweisen, die sich aus einfachen Konzepten zum Kalkül aufbauen), und es gibt Techniken, die in der Komplexitätstheorie verwendet werden (Reduktionen von einem Problem auf ein anderes, denken Sie an eine injektive Karte wo Sie die Karte bereitstellen müssen, anstatt zu beweisen, dass sie injektiv ist).

3. Dieser Kurs ( https://courses.engr.illinois.edu/cs374/lectures.html ) enthält Vorlesungsunterlagen und Folien sowie hervorragende einführende Referenzmaterialien. In keiner Weise deckt dies alles ab, aber es könnte ein guter Anfang für Sie sein. Die Laborarbeit ist sehr schön anzusehen und Ihr Verständnis zu testen, aber oft ist es schwieriger als das erforderliche Wissen.

Schließlich wird Ihre diskrete Mathematik dabei eine große Hilfe sein. Sie werden sehen, wie wichtig die Graphentheorie für die Analyse und das Design von Algorithmen sowie für die Kombinatorik für die Analyse der Datenstruktur ist. Viel Glück und ich hoffe du findest was du suchst!

Ich würde vorschlagen, dass Sie (a) bestimmen, welche mathematischen Voraussetzungen Sie benötigen, (b) die ersten 3-4 Probleme in jedem Kapitel wirklich verstehen und durchgehen, vertrauen Sie mir, auch wenn diese lange dauern, werden Sie den Dreh raus bekommen es dann ziemlich schnell mit zukünftigen problemen.