de it fr

411 Datenstrukturen und Algorithmen entwerfen und anwenden

Modul
Datenstrukturen und Algorithmen entwerfen und anwenden
Kompetenz
Problemstellung analysieren und mit geeigneten Datenstrukturen und Algorithmen eine Lösung umsetzen, testen und dokumentieren.
Handlungsziele
1 Für ein gegebenes Problem eine geeignete Datenstruktur definieren und mit den Mitteln einer Programmiersprache, wie Structs, Referenzen / Zeiger und Arrays umsetzen.
  Handlungsnotwendige Kenntnisse:
1 Kennt den Unterschied zwischen Wertevariablen und Referenzvariablen / Zeigervariablen.
2 Kennt Sprachmittel einer Programmiersprache für das Deklarieren und das Arbeiten mit Werte- und Referenzvariablen.
3 Kennt Konzept und Nutzen von verketteten Datenstrukturen.
4 Kennt eine Notation für die Darstellung von verketteten Datenstrukturen.
 
2 Ein Problem analysieren und einen geeigneten Algorithmus zur Lösung mit den Grundelementen Zuweisung, Verzweigung und Schleife entwerfen und mit Prozeduren und Funktionen umsetzen.
  Handlungsnotwendige Kenntnisse:
1 Kennt eine systematische Vorgehensweise für die Analyse eines Problems.
2 Kennt die Grundelemente von Algorithmen und deren Umsetzung in einer Programmiersprache.
3 Kennt die Sprachmittel einer Programmiersprache für das Deklarieren und Aufrufen von Funktionen und Prozeduren.
4 Kennt Notationen um Algorithmen dazustellen wie z.B. Struktogrammen, PAP usw.
 
3 Algorithmen und Datenstrukturen hinsichtlich Speicher- und Zeitkomplexität analysieren und dokumentieren.
  Handlungsnotwendige Kenntnisse:
1 Kennt Möglichkeiten zur Analyse von Zeit- und Speicherkomplexität von Algorithmen und Datenstrukturen.
2 Kennt Komplexitätsklassen von Algorithmen (z.B. lineare, exponentielle Komplexität).
3 Kennt Notationen zur Dokumentation der Speicher- und Zeitkomplexität eines Algorithmus.
 
4 Ein komplexeres Problem auf kleinere Teilprobleme zurückführen und je nach Problemstellung Iteration oder Rekursion einsetzen.
  Handlungsnotwendige Kenntnisse:
1 Kennt ein Vorgehen bei der Aufteilung eines komplexen Problems in kleinere Teilprobleme.
2 Kennt den Aufbau von iterativen Algorithmen.
3 Kennt den Aufbau von rekursiven Algorithmen.
4 Kennt Vor- und Nachteile sowie geeignete Einsatzgebiete des iterativen und des rekursiven Ansatzes.
 
5 Abstrakte Datentypen, wie Liste, Set, Map etc. und die darauf definierten Operationen kennen und zielgerichtet einsetzen können.
  Handlungsnotwendige Kenntnisse:
1 Kennt eine Programmbibliothek, die ADTs wie Liste, Set, Map, etc. zur Verfügung stellt und deren Anwendung.
2 Kennt Eigenschaften von einzelnen abstrakten Datentypen.
 
6 Datenstrukturen und Algorithmen mit dem Debugger und weiteren Tools untersuchen und dabei speziell die Situation auf Stack und Heap Analysieren und in geeigneter Form darstellen.
  Handlungsnotwendige Kenntnisse:
1 Kennt das Speicherlayout für einen Prozess mit den Bereichen Programmcode, globale Variablen, Stack und Heap.
2 Kennt die Anordnung von lokalen Variablen und Parametern in einem Stackframe.
3 Kennt die Funktionsweise des Stacks bei einem Funktionsaufruf.
4 Kennt die Funktionsweise im Heap bei dynamisch erzeugten Objekten.
5 Kennt die Anwendung eines Debuggers für die Untersuchung von Heap und Stack zur Laufzeit und/oder ein Tool zur Laufzeitanalyse für Grössen wie Memory Leaks, Aufrufhäufigkeit und Verweildauer von Funktionen, etc.
 
Kompetenzfeld
Application Engineering
Objekt
Durchführung einer Analyse und darauffolgende Realisierung mit Datenstrukturen und Algorithmen.
Niveau
2
Voraussetzung
Prozedurales Programmieren Objektbasiertes Programmieren
Anzahl Lektionen
40
Anerkennung
Eidg. Fähigkeitszeugnis
Publiziert: 10.09.2014 17:54:22
Titel LBV Modul 411-1 - 3 Elemente - Praktische Umsetzungsarbeit, Praktische Umsetzungsarbeit, Schriftliche Einzelprüfung / Schriftlicher Test
Institution Berufsbildungszentrum Solothurn-Grenchen
Übersicht Handlungsorientiert Problemstellungen analysieren und mit geeigneten Datenstrukturen und Algorithmen Lösungen umsetzen.
Ergänzung

Teil 1
Gewichtung 33%
Richtzeit (Empfehlung) 2
Element-Beschreibung Realisieren eines Programmes, das die Datenstrukturen zweidimensionales Array und Enumeration anwendet. Das Programm muss entworfen, implementiert und die korrekte Funktionsweise nachgewiesen werden. Die korrekte Dokumentation des Programmes wird bewertet.
Hilfsmittel Betriebssytem Basisinstallation
Office Paket
Entwicklungsumgebung für gewählte Programmiersprache
Code - Entwurfswerkzeug
Bewertung Verwendung von Enumerations 5 Punkte
Einsatz von Konstanten 1 Punkt
Verwendung von zweidimenionalen Arrays 3 Punkte
Algorithmus zur Lösung des Problems 7 Punkte
Nachweis korrekte Funktion 4 Punkte
Dokumentation 3 Punkte
Praxisbezug Software - Qualität durch den Einsatz von Enumerations und Konstanten erhöhen
adäquater Einsatz von mehrdimensionalen Arrays

Teil 2
Gewichtung 33%
Richtzeit (Empfehlung) 2
Element-Beschreibung Dynamische Datenstrukturen, insbesondere die einfach verkettete Liste, in Aufbau verstehen und Basisfunktionalität implementieren und anwenden. Das Programm muss entworfen, implementiert und die korrekte Funktionsweise nachgewiesen werden. Die korrekte Dokumentation des Programmes wird bewertet.
Hilfsmittel Betriebssytem Basisinstallation
Office Paket
Entwicklungsumgebung für gewählte Programmiersprache
Code - Entwurfswerkzeug
Bewertung Basismethode eins entwerfen und implementieren 8 Punkte
Basismethode zwei entwerfen und implementieren 7 Punkte
Anwendung dieser dynamischen Datenstruktur 2 Punkte
Nachweis korrekte Funktion 4 Punkte
Dokumentation 5 Punkte
Praxisbezug Die Verarbeitung von grossen Datenmengen im Hauptspeicher lässt sich nur mit dynamischen Datenstrukturen effizient durchführen

Teil 3
Gewichtung 34%
Richtzeit (Empfehlung) 1
Element-Beschreibung Sortieralgorithmen verstehen und nachvollziehen. Auf einer Baumstruktur einen einfachen rekursiven Suchalgorithmus entwerfen.
Hilfsmittel keine - auf Papier
Bewertung Sortieralgorithmen verstehen 5 Punkte
Effizienz von Sortieralgorithmen beurteilen 5 Punkte
rekursiven Algorithmus entwerfen 10 Punkte
Praxisbezug In Datenbanken sind Sortieralgorithmen von zentraler Bedeutung
Effizientes Suchen und Sortieren von Millionen von Elementen
Publiziert: 23.02.2016 08:12:32
Ablaufdatum: Kein Ablaufdatum
Titel LBV Modul 411-3 - 3 Elemente - Praktische Umsetzungsarbeit, Praktische Umsetzungsarbeit, Praktische Umsetzungsarbeit
Institution Informatikschule Olten GmbH
Übersicht Problemstellungen sowohl als Rekursion, als auch als Loop umsetzen. Sortier-Algorithmen kennen und einsetzen. Verkettete Liste verstehen und erweitern. Abstrakte Datentypen richtig einsetzen. Analyse von vorgegebenen Programm-Codes bzgl Funktionalität und Laufzeitkomplexität.
Ergänzung

Teil 1
Gewichtung 30%
Richtzeit (Empfehlung) 2
Element-Beschreibung 1) Aufgabenstellung (z.B. Summe der ersten n positiven, ganzen Zahlen) sowohl als Rekursion, als auch als Loop umsetzen und deren Laufzeitkomplexität angeben (O-Notation). Visualisieren der Rekursion (z.B. für die Summe der ersten 3 Zahlen) auf dem Stack.
2) Vorgegebenen Pseudocode umsetzen und dessen Funktionalität erkennen (z.B. ggT).
3) Vorgegebenen Sortier-Algorithmus (z.B. InsertionSort) ohne Computer analysieren und für jeden Durchgang die Situation des Arrays aufzeigen sowie die Laufzeitkomplexität angeben.
Hilfsmittel 1) und 2) frei
3) ohne Hilfsmittel
Bewertung 1) je 3 Punkte für Rekursion und Loop, je 1 Punkt für Laufzeitkomplexität, 2 Punkte für Stack-Visualisierung = 10 Punkte
2) 4 Punkte für die Implementation des Pseudocodes inkl. Test-Programm, 1 Punkt für das Erkennen der Funktionalität = 5 Punkte
3) 4 Punkte für die korrekte Darstellung der Arrays, 1 Punkt für Laufzeitkomplexität = 5 Punkte
Praxisbezug Vor- und Nachteile von Rekursion und Loop kennen.
Umsetzen von Rekursionen und Loops.
Laufzeitkomplexitäten beurteilen können (z.B. was passiert wenn statt 1'000 später 1'000'000 Elemente sortiert werden müssen).
Fremde Code-Stücke analysieren können.
Verhalten von Programm-Code bzgl. Stack und Heap erkennen können.

Teil 2
Gewichtung 40%
Richtzeit (Empfehlung) 2
Element-Beschreibung 1) Greedy-Algorithmus umsetzen und erklären (z.B. minimale Anzahl Münzen für einen vorgegebenen Betrag).
2) Eigene Klasse erstellen und Comparable-Interface implementieren inkl. Test-Programm.
3) Aufgabenstellung (z.B. x^y) sowohl als Rekursion, als auch als Loop umsetzen.
4) Vorgegebenen Algorithmus (z.B. Min/Max in einem Array) ohne Computer analysieren und Funktionalität erkennen und eine Zusatzfrage zum Code beantworten (z.B. Anzahl Vergleiche für ein Array der Grösse n)
Hilfsmittel 1) bis 3) frei
4) ohne Hilfsmittel
Bewertung 1) 2 Punkte für die Umsetzung, 1 Punkt für die Erklärung = 3 Punkte
2) je 1 Punkt für die Klasse, die Interface-Implementation und das Test-Programm = 3 Punkte
3) je 1 Punkte für Rekursion und Loop = 2 Punkte
4) je 1 Punkt für das Erkennen der Funktionalität und das Beantworten der Zusatzfrage = 2 Punkte
Praxisbezug Greedy-Algorithmus kennen und einsetzen können.
Interface verstehen und implementieren können.
Umsetzen von Rekursionen und Loops.
Fremde Code-Stücke analysieren können.

Teil 3
Gewichtung 30%
Richtzeit (Empfehlung) 2
Element-Beschreibung 1) Vorgegebene Implementation einer verketteten Liste erweitern und erklären (visualisieren)
2) Geeigneten abstrakten Datentyp aufgrund von vorgegebenen Daten wählen, einsetzen und erklären.
Hilfsmittel frei
Bewertung 1) Gesamthaft 7 Punkte für z.B. 2 Erweiterungen, 3 Punkte für die Visualisierungen = 10 Punkte
2) 3 Punkte für die Wahl des geeigneten Datentyps, 3 Punkte für den korrekten Einsatz nach Vorgabe, 2 Punkte für die Erklärungen = 8 Punkte
Praxisbezug Datenstrukturen verstehen und richtig einsetzen können.
Publiziert: 08.07.2016 13:34:34
Ablaufdatum: Kein Ablaufdatum
Titel LBV Modul 411-4 - 2 Elemente - Schriftliche Einzelprüfung / Schriftlicher Test, Praktische Umsetzungsarbeit
Institution gibb Gewerblich-Industrielle Berufsschule Bern
Übersicht Zweiteilige LB mit einer schriftlichen Prüfung sowie einer praktischen Einzelarbeit
Ergänzung

Teil 1
Gewichtung 50%
Richtzeit (Empfehlung) 0
Element-Beschreibung - Terminologie: Problemanalyse, Spezifikation, Algorithmus, Programm.
- Einfache Datenstrukturen wie mehrdimensionale Arrays für ein bestimmtes Problem bestimmen und
- mit einem Algorithmus zur Problemlösung bearbeiten.
- Problemlösung hinsichtlich Zeit- oder Speicherkomplexität bewerten.
- Problemstellung beinhaltet Kontrollstrukturen sowie Iterationen und/oder Rekursionen und benötigte Datentypen.
Hilfsmittel Eine selbsterstellte Zusammenfassung von max 2 Seiten (1 Seite doppelseitig oder 2 Seiten einseitig bedruckt) und/oder
eine Sprachreferenz
Bewertung ca. 20% Handlungsziel 1 - Datenstruktur für Problem finden
ca. 20% Handlungsziel 2 - Analyse
ca. 20% Handlungsziel 3 - Komplexität
ca. 20% Handlungsziel 4 - Problemzerlegung
ca. 20% Handlungsziel 5 - Abstrakte Datentypen und/oder primitive Datentypen
Praxisbezug Siehe Bildungsplan Applikationsentwicklung
A1.1: Bedürfnisse/Anforderungen analysieren
A2.2/3: Problem lösen
B2.2: Bekannte Lösungswege anwenden
B5.1: Testfälle (Komplexität)

Teil 2
Gewichtung 50%
Richtzeit (Empfehlung) 0
Element-Beschreibung Praktische Einzelarbeit unter realen Bedingungen:
- Die Arbeit wird mit einem geeigneten IDE ausgeführt.
- Problem entgegen nehmen und geeignete Lösung (Datenstruktur und Algorithmus finden).
- Lösung implementieren und mit
- geeigneten Testfällen überprüfen.
- Speicher und/oder Zeitkomplexität der Lösung verifizieren und festhalten.
- Fehler mit Hilfe des IDE (Debugger) beheben.
Hilfsmittel Eine selbsterstellte Zusammenfassung von max 2 Seiten (1 Seite doppelseitig oder 2 Seiten einseitig bedruckt) und/oder
eine Sprachreferenz
Bewertung ca. 20% Handlungsziel 2 - Analyse
ca. 20% Handlungsziel 1 - Datenstruktur für Problem finden
ca. 10% Handlungsziel 4 - Problemzerlegung
ca. 20% Handlungsziel 5 - Abstrakte Datentypen und/oder primitive Datentypen
ca. 10% Handlungsziel 3 - Komplexität
ca. 20% Handlungsziel 6 - Fehlersuche mit Debugger
Praxisbezug Siehe Bildungsplan Applikationsentwicklung
A1.4: Anforderungen darstellen (z.B. Zustandsdiagramm, Klassendiagramm o.a.)
B2.1/2 und B3.7: Umsetzung
B3.5: Entwurfsmethoden anwenden
B4.6 Anwendung testen
B5.1: Testfälle (Komplexität)
Publiziert: 29.03.2016 13:21:39
Ablaufdatum: Kein Ablaufdatum
Titel LBV Modul 411-5 - 3 Elemente - Schriftliche Einzelprüfung / Schriftlicher Test, Praktische Umsetzungsarbeit, Bearbeiten eines Projekts
Institution BZZ Bildungszentrum Zürichsee
Übersicht Dreiteilige Leistungsbeurteilung mit einer schriftlichen Einzelprüfung, einer praktischen Umsetzungsarbeit als Einzelarbeit und ein Programmierprojekt als Gruppenarbeit
Ergänzung

Teil 1
Gewichtung 25%
Richtzeit (Empfehlung) 1
Element-Beschreibung Schriftliche Leistungsbeurteilung über den Einsatz von einfachen Datenstrukturen und Algorithmen mit mindestens 4 Aufgaben (K1 – K3 Fragetypen) zu den Themen:
Eigenschaften von Algorithmen
Darstellungsformen für Algorithmen
Funktionalität von vorgegebenen Algorithmen als Ablaufdiagramm oder Pseudocode mit einer Tracetabelle analysieren
Hilfsmittel keine
Bewertung 5 Punkte Eigenschaften und Darstellungsmöglichkeiten eines Algorithmus
5 Punkte je Ablaufdiagramm (NSD und PAP) = 10 Punkte
5 Punkte für die Analyse eines Algorithmus mit Tracetabellen
Praxisbezug Ein Problem analysieren
Den Ablauf eines Prozesses darstellen
Funktionalität von vorgegebenen Programmteilen erkennen

Teil 2
Gewichtung 35%
Richtzeit (Empfehlung) 2
Element-Beschreibung Einfache lineare Datenstrukturen wie zweidimensionale Arrays mit einem Algorithmus bearbeiten.
Vorgegebene dynamische Datenstrukturen (wie z.B. einer verketteten Liste) erklären / darstellen und mit neuen Funktionalitäten bzw. Methoden erweitern.
Iterative und rekursive Implementation eines Algorithmus umsetzen.
Hilfsmittel Als Hilfsmittel steht eine selbsterstellte Zusammenfassung als 2-seitiges DIN A4-Blatt zur Verfügung
Bewertung Abstrakte Datentypen:
3 Punkte pro neue Funktion/Methode
2 Punkte je Darstellung der Datenstruktur = 4 Punkte
4 Punkte für die iterative und rekursive Umsetzung
Praxisbezug Dynamische Datenstrukturen verstehen, anwenden und erweitern.
Einfache rekursive und iterative Algorithmen entwerfen und umsetzen.

Teil 3
Gewichtung 40%
Richtzeit (Empfehlung) 12
Element-Beschreibung Praktische Gruppenarbeit unter realen Bedingungen:
Eine Problemstellung analysieren
Geeignete Datenstrukturen wählen und einsetzen
Eine Lösung entwerfen, implementieren und testen
Hilfsmittel Als Hilfsmittel stehen alle Unterlagen inkl. Internetzugang zur Verfügung
Bewertung 2 Punkte für die Analyse des Problems und Zerlegung des Projekt ist in sinnvolle Elemente
3 Punkte für geeignete Datenstrukturen oder ADTs für die Problemlösung
2 Punkte für die Darstellung von Algorithmen
3 Punkte für die effiziente Umsetzung von Algorithmen
2 Punkte für die Fehlersuche mit dem Debugger
2 Punkte für die Testfälle
Praxisbezug Anforderungen darstellen und effizient umsetzen
Korrekter und adäquater Einsatz von Datenstrukturen / ADTs
Applikationen testen
Publiziert: 16.12.2016 08:23:10
Ablaufdatum: Kein Ablaufdatum
Titel LBV Modul 411-6 - 2 Elemente - Schriftliche Einzelprüfung / Schriftlicher Test, Praktische Umsetzungsarbeit
Institution Zürcher Lehrbetriebsverband ICT (ZLI)
Übersicht Mittels zwei unabhängiger Elemente soll das Planen und das Realisieren von Applikationen mit grösseren Datenmengen und anspruchsvollen Algorithmen geprüft werden.
Ergänzung Wir wollen die Dauer der ganzen Leistungsbeurteilung auf 2 Lektionen beschränken.

Teil 1
Gewichtung 40%
Richtzeit (Empfehlung) 1
Element-Beschreibung Eine Applikation bzw. einen Teil einer Applikation planen, z.B. Structure Chart einer ganzen Applikation (Modularisierung, Schnittstellen) oder Struktogramm einer verarbeitenden Funktion (Algorithmus).
Hilfsmittel Alle Kursunterlagen
Bewertung Vollständigkeit der Lösung
Richtigkeit der Lösung
Korrekte Notation
Dokumentgestaltung
Praxisbezug Entspricht der täglichen Arbeit in der Applikationsentwicklung.

Teil 2
Gewichtung 60%
Richtzeit (Empfehlung) 1
Element-Beschreibung In einer bestehenden Applikation, welche einen grösseren Datenbestand verarbeitet, eine zusätzliche Verarbeitung implementieren.
Mögliche Datenbestände: Mehrere Datensätze mit Text und Zahlen.
Mögliche Datenhaltung: Dynamisches Struktur-Array, verkettete Liste.
Mögliche Verarbeitung: Sortieren, suchen, Berechnung/Auswertung über alle Datensätze oder über jene Datensätze, welche ein bestimmtes Merkmal erfüllen.
Hilfsmittel Alle Kursunterlagen
Bewertung Vollständige Umsetzung
Korrekte Funktionalität
Wartungsfreundliche Code-Gestaltung
Praxisbezug Entspricht der täglichen Arbeit in der Applikationsentwicklung.
Publiziert: 22.09.2016 11:57:18
Ablaufdatum: Kein Ablaufdatum
Zurück