TCS-Unterricht an Gymnasien - bestehende Programme

16

Mir wurde angeboten, ein neuartiges TCS-Highschool-Programm zu unterrichten, für das ein Lehrplan erstellt werden muss. Ich würde sehr gerne Meinungen und Vorschläge dazu hören.

Erstens, kennt jemand Hochschulen, an denen ein TCS-Programm erfolgreich (oder erfolglos) unterrichtet wurde?

Die Idee ist ein 3-jähriges Programm (10.-12. Klasse, 16-18 Jahre), ungefähr 8 Wochenstunden, für ausgewählte herausragende Studenten, was bedeutet, dass es anspruchsvoll sein kann und sollte. Im Gegensatz zum Standardprogramm "Computer" sollte sich dieses Programm nicht auf die Programmierung konzentrieren, sondern auf ausgewählte Themen in CS, hauptsächlich in TCS. Die Themen, die wir bisher im Auge haben, sind im Großen und Ganzen:

  • Asymptotische Analyse
  • Grundlegende Datenstrukturen und Algorithmen (Listen, Arrays)
  • Graph-Algorithmen, auch als Demonstration von Greedy-Algorithmen gegen dynamische Programmierung.
  • Andere Algorithmen (zB probabilistisch)
  • Berechenbarkeit - das Konzept eines TM, Reduktion, Entscheidbarkeit.
  • Komplexität - NP, P, vielleicht PSPACE und NL. Vollständigkeit.
  • Automatentheorie

Grundsätzlich umfasst dies den TCS-Teil der ersten zwei Jahre eines B.Sc in CS. Wir müssen jedoch bedenken, dass diesen Schülern die mathematischen Grundlagen fehlen, die für den größten Teil dieses Materials erforderlich sind. Insbesondere werden Dinge wie Mengenlehre, Kombinatorik, Wahrscheinlichkeit und modulare Artihmetik (leider) nicht in der High School unterrichtet.

Um es zusammenzufassen und präzise Fragen zu stellen:

  1. Kennt jemand ein ähnliches Programm irgendwo?
  2. Gibt es Vorschläge für konkrete / allgemeine Themen, die Ihrer Meinung nach zusätzlich / anstelle der oben genannten Themen vermittelt werden können und sollten, während das Programm interessant sowie wichtig und direkt relevant bleibt (z. B. Gruppentheorie ist wichtig und interessant, aber nicht relevant genug)? die Zeit zu rechtfertigen, die es dauern wird)
  3. Ich hätte das maschinelle Lernen gerne in irgendeiner Form eingeführt, da es heutzutage ein sehr heißes Thema ist. Anregungen, wie maschinelles Lernen ohne Hilfsmittel wie Maßkonzentrationssätze dargestellt werden kann, sind willkommen.
Shaull
quelle
2
Es scheint, dass Sie die Automatentheorie am Ende als eine Art Nachdenken auflisten. Ich würde mich dafür einsetzen, die Automatentheorie zum zentralen und einheitlichen Thema zu machen. Es kann den Schülern formales mathematisches Denken ohne spezifischen mathematischen Hintergrund vermitteln. Es hat scharfe bedingungslose Theoreme, die grundlegend, aber relativ einfach zu beweisen sind. Es kann direkt mit maschinellem Lernen verbunden werden , obwohl es meiner Erfahrung nach schwierig ist, Studenten in einem ersten Theoriekurs zu unterrichten.
Artem Kaznatcheev
1
Ich habe noch nie davon gehört! "ausgewählte" Studenten? heißt das wohl auch fortgeschritten? Versuchen Sie, populärwissenschaftliche Bücher auf TCS oder auch Online-Blogs abzubauen [einige gute da draußen]. Turing Machines, Quantencomputing andere wichtige / interessante Bereiche. Ich denke, dies könnte durchgezogen werden, wenn die Mathematik nicht schwer und eher konzeptionell als mathematisch ist. Auch diese Seite taucht häufig bei Fragen zu Edus auf: cs unplugged . Viel Glück!
vzn
2
Ich frage mich, ob es am besten ist, einen Teil Ihrer Zeit dem Unterrichten der von Ihnen genannten mathematischen Fähigkeiten (z. B. Wahrscheinlichkeit) zu widmen. Dies würde Ihnen möglicherweise auch dabei helfen, fortgeschrittenere Themen zu behandeln, aber auch die Schüler auf zukünftige Studien in Mathematik / Cs vorzubereiten .
usul
1
@vzn - ja, das sind fortgeschrittene (ich wage zu sagen - begabte) Studenten.
Shaull
1
@vzn Das ist ein sehr interessanter Vorschlag. Irgendwie ist TCS noch nicht Teil der Populärkultur. Das heißt, selbst neugierige Schüler sind sich normalerweise Fragen wie P gegen NP nicht bewusst. Aber wir werden aktuelle CS-Studenten auf jeden Fall um Vorschläge bitten und sehen, was sie sich einfallen lassen. Ich vermute, dass Kryptographie eine zentrale Rolle spielen würde.
Shaull

Antworten:

8

Viele Länder organisieren Sommerschulen für ihre IOI-Teams (bestehend aus Schülern im Alter von ungefähr 16 Jahren). Die, die wir im Iran haben, hatten die folgenden Kurse:

  • Programmierung,
  • Datenstruktur und Algorithmen,
  • Kombinatorik und
  • Graphentheorie.

Ich denke, die Computer Science Teachers Association von ACM hat einen K12-Lehrplan auf ihrer Seite mit Lehrplanressourcen, obwohl er für talentierte Teenager wahrscheinlich viel zu leicht ist.


Ich denke, Programmierung muss definitiv Teil des Lehrplans sein. Python sollte eine gute Muttersprache sein.

Möglicherweise möchten Sie auch einige zugängliche Themen mit Anwendungen abdecken (die Freude am Erstellen von etwas Coolem kann einen großen Einfluss auf deren Interesse haben). Ich denke, Andrew Ngs ML-Kurs über Coursera sollte für talentierte Studenten zugänglich sein (insbesondere für diejenigen in Ländern wie Ihrem, in denen es einen ernsthafteren K12-Mathematiklehrplan gibt).

Ein nicht standardmäßiges Thema, das Sie in Betracht ziehen sollten, ist die kombinatorische Spieltheorie. Mit 16 Jahren ist es vielleicht nicht sehr interessant (ich habe keine Erfahrung damit), aber meiner Erfahrung nach funktioniert es ziemlich gut für ein bisschen jüngere Schüler.

Ich persönlich denke, das zentrale und verbindende Thema sollte Algorithmen sein, ich denke, es würde besser funktionieren als die Automatentheorie, da das zentrale Thema und wohl die algorithmische Perspektive (nicht Turing-Maschinen, Automaten usw.) die Essenz der Informatik ist.

Kaveh
quelle
Der Programmierteil wird durch das Standard-CS-Programm abgedeckt, das sie alle übernehmen. Dies sind zusätzliche Themen. Haben Sie zufällig einen Link zu einer solchen Sommerschulwebsite? Bei der Fokussierung auf Algorithmen bin ich mir zwar einig, dass sie für CS von zentraler Bedeutung sind, aber ich denke, dass Berechenbarkeit und Komplexität gleichermaßen die Essenz der Informatik sind. Ich erinnere mich, dass mich die Tatsache beeindruckt hat, dass es Dinge gibt, die wir nicht lösen können, und nicht clevere Algorithmen. Aber wahrscheinlich werden beide abgedeckt sein.
Shaull
In gewisser Weise dreht sich bei Turing-Maschinen alles um Algorithmen . Auch Ruby ist eine ausgezeichnete Option, die mit Python vergleichbar ist . auf dem gleichen subj eine andere ausgezeichnete Option, um Entwicklung zu lernen, ist Javascript aus vielen Gründen, z. B. seine Verbreitung in Browsern, viele öffentliche / Beispielcode, breite Funktionen, hohe Nutzung, etc.
vzn
1
@Shaull, sie haben eine Seite ( Young Scholars Club ), aber sie ist auf Persisch und enthält in keiner Weise viel darüber, was in der Sommerschule behandelt wird.
Kaveh
1
@vzn, ich glaube nicht, dass Sie viel Erfahrung im Unterrichten von TCS an Gymnasiasten haben, und ich habe Ihnen sehr deutlich erklärt, dass mich Ihre Meinung nicht interessiert . Hör auf, meine Antworten zu durchsuchen.
Kaveh
k, plz rate nicht bei meinem bkg & werde das gleiche mit freundlicher Genehmigung tun. Kommentar ist im Grunde in Unterstützung von Ihre Meinungen ... klingt wie ein Thema für meta = (
VZN
5

Seltsamerweise gibt es jemanden, der argumentiert, dass maschinelles Lernen einzigartig istUnter den Informatik-Themen ist es eines der wenigen Unterfelder, in denen Sie durch grundlegende Mathematik genügend Verständnis für die wichtigen Herausforderungen erlangen können. Ich bin mit dieser Behauptung nicht einverstanden - grundlegende Algorithmen (z. B. zum Suchen, Sortieren) können als Rätsel dargestellt werden, und Sie können sehr schnell zu sehr einfachen Aussagen gelangen, aber grundlegende offene Probleme wie "können mit im Wesentlichen der gleichen Anzahl von Operationen multipliziert werden als Addition "oder Sortieren von ganzen Zahlen in linearer Zeit oder Factoring (Ich gehe davon aus, dass das Konzept der Primzahlen für die ausgewählte Gruppe von Schülern nicht neu wäre?). Andererseits wäre viel maschinelles Lernen ohne ein gutes Maß an Erfahrung mit Statistik und Wahrscheinlichkeitstheorie schwer zu verstehen. Dennoch,

In Bezug auf ein Lehrprogramm gibt es ein ausführlicheres von Essinger und Rosen bei Drexel.

Darüber hinaus könnte man versuchen, einige der übergeordneten Ideen der Lerntheorie zu skizzieren:

  • Was ist das grundlegende Klassifizierungsproblem?
  • Was ist eine Konzeptklasse und was bedeutet es, ein Konzept zu lernen?
  • Warum Sie nicht hoffen können, Konzepte aus einer uneingeschränkten Konzeptklasse mit weniger als exponentiellem Stichprobenaufwand zu lernen (als Einführung in das Zählen von Argumenten)
  • Was ist VC-Dimension

Ein weiterer Vorschlag ist, Schaltkreise einzuführen und eine Skizze von Shannons Untergrenze zu versuchen. Kommt darauf an, wie gut die Schüler mit dem Zählen umgehen können. Wenn dies zu schwer ist, kann es dennoch hilfreich sein, das Argument zu führen, während die Schüler das Zählen der Schaltkreise selbst anhand des Glaubens durchführen. Ich denke, die Idee "Die meisten Probleme erfordern große Schaltkreise, weil es zu viele Probleme und zu wenige kleine Schaltkreise gibt" wird auffallen. Diese Idee ist wichtig und durchdringend in ihrer Komplexität.

Sasho Nikolov
quelle
Beide Vorschläge sind sehr nett. Vielen Dank! Ich habe das Gefühl, dass für die High School das Erlernen einer VC-Dimension ungefähr 3 Monate dauern kann, was zu viel sein kann. Aber es ist definitiv eine Überlegung wert, zumal bereits darüber nachgedacht wurde.
Shaull
Ich denke, auch nur zu verstehen, was es bedeutet, ein Konzept zu lernen und eine vage Vorstellung davon zu haben, dass man nicht willkürlich komplizierte Dinge lernen kann, bevor die Sonne zufriert, wird ein Gewinn sein.
Sasho Nikolov
3

Hier ist eine vielversprechende Richtung, um dies zu tun. AP / NSF kündigte kürzlich eine neue CS-Programminitiative für Fortgeschrittene an. Die Verwendung eines solchen Programms bietet viele Vorteile, z. B. einen standardisierten Stundenplan, eine Hochschulakkreditierung usw.

Es befindet sich derzeit in der Entwicklung und soll für 2016 fertig sein. Der vorläufige Lehrplan und die Materialien sind online verfügbar. (Für akademische Experten könnte es an dieser Stelle sogar eine Möglichkeit geben, den zukünftigen Inhalt über eine Zusammenarbeit vom Typ "kollektive Intelligenz" zu beeinflussen.)

Das Advanced Placement Program des College Board teilte am Donnerstag mit, dass ein neues Informatik-Programm zu seinem Klassenangebot hinzugefügt werden soll, der erste neue Test seit sieben Jahren. Der Schritt spiegelt ein wachsendes Interesse an der Ausbildung von Studenten für eine Karriere in den Wissenschaften wider, während die US-Wirtschaft weltweit wettbewerbsfähiger werden soll.

Das neue Programm, AP Computer Science Principles, konzentriert sich auf die "kreativen Aspekte" des Rechnens und wird zum Teil durch einen Zuschuss von 5,2 Millionen US- Dollar von der National Science Foundation finanziert. Die Bundesbehörde beabsichtigt, bis 2016 weitere 10.000 Informatiklehrer an derselben Anzahl von Gymnasien im ganzen Land auszubilden, um die Ausbildung in den Bereichen Naturwissenschaften, Technik, Ingenieurwesen und Mathematik oder MINT zu verbessern. Das College Board wird etwa 3,5 Millionen US- Dollar für die Unterstützung und Ausrüstung der Lehrer aufbringen.

Das bestehende Programm heißt AP Computer Science A und das neue Programm heißt AP Computer Science Principles. Die bestehende Klasse gibt es schon seit vielen Jahren und sie ist auch als Modell für Lehrkräfte hilfreich, die Lehrpläne entwickeln.

vzn
quelle
3
Übrigens haben Baker Franke und ich auf der SIGCSE '14 einen Vorschlag für eine BOF-Sitzung (Birds-of-a-Feather) eingereicht, um zu erörtern, wie Themen in der Theorie für den Lehrplan der CS Principles zugänglich gemacht werden können.
Rahulmehta95
@ rahulmehta95 - gibt es einen Link zu dem Vorschlag, den ich lesen kann?
Shaull
2
Hier gehts: cs.ucls.uchicago.edu/~rahulmehta/papers/BOF-Theory.pdf . Hoffe das hilft!
Rahulmehta95
2

Eine Idee, mit der ich mich in letzter Zeit beschäftigt habe, ist, HS-Studenten den Begriff der Reduktion zwischen Problemen beizubringen. Ich fand dies eines der interessantesten und zugleich herausforderndsten Themen, als ich in die Komplexität eingeführt wurde, da es (zumindest anfangs) ziemlich schwierig ist, sich darüber hinwegzusetzen, dass ein Problem wie 3-SAT "genauso schwer" ist als Vertex-Cover.

Das Beispiel, das ich mir ausgedacht habe, war eine Reduzierung zwischen Vertex Cover (VC) und Independent Set (IND-SET), die wie folgt lautet:

"Sie sind der Direktor eines Museums und haben die Aufgabe, Sicherheitspersonal für die Bewachung der Gänge einzustellen. Wenn Sie sich an einer Kreuzung von Gängen befinden, kann ein Wachmann ALLE ihm benachbarten Gänge im Auge behalten. Wie viele Wachen sind mindestens erforderlich? das ganze Museum patrouillieren? "

"Ein wenig später beschließen einige Kinder, im Museum ein Versteckspiel zu spielen. Ihr Ziel ist es, sich so zu verstecken, dass kein anderes Kind sie sehen kann. Die Wachen wollen jedoch nicht, dass sie im Museum herumlaufen Flure, so dass sie in den Kreuzungen "versteckt" werden. Was ist die größte Anzahl von Kindern, die sich im Museum verstecken können, ohne sich zu sehen? "

VCPIND-SET

G=(V,E)SV VS

SVSG

rahulmehta95
quelle
CLIQUEpINDSET
Was die Kürzungen angeht, so ist der Beweis, dass es eine universelle Turingmaschine gibt, ein einfacher Weg und wahrscheinlich für fortgeschrittene Highschooler verständlich die Tseitin-Transformation ?
vzn