Informatik - erledigt Flashcards
Aufbau eines Befehls
Hilfe
command [options] arguments
Command ist Kurzname des Befehls
Options für die Parameter der Ausführung (vorgegeben) (und können selbst auch arguments besitzen)
Arguments stellen “Ziel-dateien/ordner etc” dar
Hilfe für Befehle
befehl –help
man befehl
Unterschied zwischen root und normalem User
root
user
sudo befehl
Root bzw Superuser in jedem Linux OS vorhanden
besitzt uneingeschränkte Rechte kann jede Aktion durchführen und alle Ressourcen nutzen
legt Rechte für “normale” User fest
anlegen/entfernen von Usern/groups
User
ist in Manipulation von Dateien auf seine “home-directory” eingeschränkt
Kann seine Rechte auf andere User übertragen.
Sudo befehl um etwas mit den Rechten des roots auszuführen.
Permissions und ihre Bedeutung
Groups
Permissionarten
Groups: werden verwendet um mehreren Usern den Zugriff auf gemeinsame Ressourcen zu ermöglichen
Beim Zugriff eines Users auf ein Objekt werden dessen Rechte vom Kernel gegen Permission geprüft
3Arten: read write execute
können einzeln gesetzt/entfernt werden
jedes Objekt verfügt über
Owner Group User : durch chown veränderbar sind und jeweils die 3 Permission Flags rwx besitzen : veränderbar mit chmod
2Möglichkeiten:
symbolic mode : chmod ugo +- rwx
numeric mode: read 4 write 2 execute 1
1 stelle immer 0
dann für owner dann group dann user
chmod 0764
Packen/Entpacken und Komprimieren/entkomprimieren
Ent/Packen
De/komprimieren
Redundanz
Dateien werden gepackt um eine Menge an zusammengehörenden Dateien nicht einzeln übertragen zu müssen.
-tar Archivformat bei Linux
Größe des Archivs immer größer als alle einzelnen Dateien gemeinsam da Verwaltungsdateien (fürs entpacken) erstellt werden.
Komprimieren um Größenzuwachs zu verhindern
- archivgepackte Dateien werden komprimieret um Netzwerkbandbreite zu sparen.
Formate: gzip bzip LZMA
2Arten
Verlustfrei : vor und nach komprimieren identisch
Verlustbehaftet : nicht mehr identisch (Teile verworfen)
Redundanz: weglassen ohne Informationen zu verlieren
Begriff des Problems
Zu lösende Aufgabe : Probleme
Berechnungs-, Such, Sortier, Entscheidungs, Optimierungsprobleme
3 Aspekte: Menge an Eingabewerten, Operationen, Lösungen
Entscheidbare/unentscheidbare Probleme
Lösbar wenn: Folge von Anweisugnen vorhanden die für jede Instanz in endlicher Zeit zu einem Ergebnis kommt
Unlösbar wenn: min 1 Instanz vorhanden für die keine eindeutige Aussage getroffen werden kann. (bsp Halteproblem)
Begriff des Algorithmus
Entscheidbare Probleme werden durch Algorithmus gelöst
- genau definiert Input
- genau def Abfolge von Operationen führt zur Lösung des Problems,
- läuft nicht endlos
zb touring machine, koch rezept, programmiersprachen
In Form von Programmen definiert.
Compiler
Aufbau
Wandelt Quellcode in Binary um.
Teste syntaktische aber nicht inhaltliche Korrektheit.
Plattformspezifisch
Aufbau:Moduler um mehr als 1 Prog.sprache zu unterstüzten
- Frontend: liest quellcode und übersetzt in interne Repräsentation
- Optimierer: Optimiert Code (schneller)
- Backend: erzeugt Maschinencode für Zielplattform
Umfang von C
Einsatz
C ist eine Imperative prozedurale Programmiersprache
Umfang: Struktur/Syntax, Semantik von Obj/Funktionen, Preprocessor, Stanart Library
Einsatz: Systemprogrammierung, Sprachimplementierung, Anwendungsprogrammierung, EchtzeitAnwendungen,
Schritte vom Quellcode zum Binary
Schreiben : Quellcode im Texteditor
Kompilieren:
1. Preprocessor: verarbeitet - referenzen im Quellcode ersetzt
2. Compieler: Preprocessed code compilieren
3. Assemblierung: Übersetzung des Assemblercodes in ein Objektcodes in ein Objektfile
4.Linker: linkt Objekt mit Libraries zu einem Binary
Ausführen: Binary direkt in Shell aufrufen
Syntaktische Elemente
Wichtig um Aufbau des Programmes zu verstehen
Keywords/Identifier: Benennen von Obj./jedes Obj muss über einzigartigen Namen verfügen
Variablen: Obj. zum Speichern von Werten besitzten Type
Konstanten/Literale: Unveränderliche Werte
Operatoren/Operanden: Bestimmen Art der Operation(sum)/ (+-/*) dürfen nicht Wahlfrei gewählt werden
Expressions: Kombi aus Operatioren/Operanden
Statements: Anweisung an Rechner werden von ; geschlossen
Kommentare: hinzufügen von Text
Blockstrukturen: {}, verschachtelt möglich
Syntactic Sugar: Leerzeichen, Tabs ,,,
Main Funktion: Startpunkt zum Ausführen eines Programms
Datentypen - Def.Bereich/Wertebereich von Ganzzahlen
Jede Variable/Expression verfügt über einen Datentyp. Dieser legt fest welche Werte ein Objekt annehmen darf.
Arithmetische Typen
Pointer Typen
Funktionstypen
Void Typen
Arithmetische Typen: Ganzzahlen/Gleitkommazahlen
Gleitkommazahlen zum Speichern von Zahlenwerten mit Nachkommastelle (Float, double longdouble)
Ganzzahlen: Wertebereich hängt von signedness und bitbreite ab.
Es ergeben sich viele versch. Integer Datentypen
bei Int=Bitbreite entspricht Plattform
char= ausschließlich 8bit für Text
VoidTyp
repräsentiert leeren Wertebereich als Platzhalter
shortint<=longdouble
Def./ Zweck von Pointern
Zum Hantieren mit Objektadressen
Es kann auf Daten von Objekten zugegriffen werden ohne den Identifier angeben zu müssen.
Zugriff über Pointer = Dereferenzieren
Jeder Pointer verfügt über Type.
zb Int Pointer ausschließlich für int Werte
Nicht initialisierter Pointer zeigt auf zufällige Adresse.
Arrays
Sammlung von Objekten des Gleichen Typs
Werden der Reihe nach im Speicher abgelegt
Auf jedes Element kann einzeln zugegriffen werden (Über Angabe des Indexes)
Größe kann zur Laufzeit nicht geändert werden.
Strings zb durch Char-Arrays
Structures
Sammlung von Objekten gleichen oder unterschiedlichen Typs
Objekte –> Members - werden in Deklarationsabfolge im Speicher abgelegt. Zugriff über den Namen
Zur Organisation von Dateien.
ADTS
Abstract Data Type
Kombination aus Daten und Operationen die mit diesen Daten arbeiten.
Ermöglichen die Wiederverwertung von Funktionalität
Kann Qualität vom Code erhöhen
Verringern Aufwand von Änderungen
Listen
Stacks
Queue
Bäume
Listen
Arten
Typische Operationen
Angabe eines elements
geordnete Sammlung von Objekten (Listenelemente)
Elemente können an beliebigen Stellen im Speicher liegen
- Einfach verkettete Listen: jedes Element kennt nur seinen Nachfolger
- Doppelt verkettete Listen: Jedes Element kennt Vorgänger und Nachfolger
zirkuläre Listen : Letztes und Erstes Element Verbunden
(single linked circular, double linked circular)
Typische Ops
Ermitteln der Länge
Hinzufügen/Entfernen/Vertauschen von Elementen
Angabe mittels Iterator.
Dieser Zeigt anfangs auf das Erste element. durch Aufruf einer Operation (iterate(), next()..) wird Iterator verschoben bis gewünschtes Obj. erreicht ist.
Stacks (stapel)
Operationen
Anwendung
Alle Elemente in einer Reihvolge vom Unteren zum Oberen
Ein hinzugefügtes Element wird automatisch am oberen Ende platziert. Es kann immer nur oberstes Element entfernt werden.
Last in First out Prinzip
Operationen: push (hinzufügen) pop(entfernen) isEmpty(Abfrage ob Elemente liegen)
Anwendung:
Verwaltung von verschachtelten Strukturen
Verarbeitung von Ausdrücken mit Klammerung
Ausführung von Aktionen in umgekehrter Reihenfolge
Queues (Warteschlangen)
Operationen
Anwendung
Elemente in Reihenfolge vom Anfang bis Ende
Elemente werden immer Am Ende hinzugefügt
Es kann nur element am Anfang entfernt werden
First in First out Prinzip
Ops: enqueue/put : hinzufügen
dequeue/get : entferen
lenght: Anzahl der El.
Anwendung: Verwalten von Aufgaben für Abarbeitung durch zentrales System
Zwischenspeichern von Daten
Sequenzieren von Daten aus versch. Quellen
Kommunikationsmethode zwischen Prozessen
Bäume
bestimmte Bedingungen
Binäre Bäume
Anwendungen
Binäre Suchbäume
Tree Traversal/Reihenfolgmöglichkeiten
bestehen aus Knoten(Elemente) und Kanten(Verbindungen) - gehören zu den Flexibelsten und am häufigsten eingesetzten Datenstrukturen
bestimmte Bedingungen:
- Kanten laufen nvon einem Knoten zu 0/1/mehreren anderen Knoten.
- genau 1 Knoten hat keinen Parent (Wurzel) alle anderen genau 1 Parent
- Knoten ohne Children = Leaf
Jeder knoten kann von Wurzel aus nur über genau 1 Pfad erreicht werden.
Binäre Bäume: Spezielle Form jeder Knoten hat 1/2/0 Children.
Anwendungen: Speicherung von Daten die eine Ordnung aufweißen (Zahlenwerte, Textstrings)
Alle Werte im linken Teil eines Parent sind Kleiner als der Parent
Alle Werte im rechten Teil eines Parent sind größer als der Parent
–> Binäre Suchbäume: schnelleres Einfügen suchen entfernen als bei einer Liste.
Tree Traversal
Inorder: linker Teilbaum/Wurzel/Rechter Teilbaum
Preorder: Wurzel/linker Teilbaum/Rechter Teilbaum
Postorder: linker Teilbaum/Rechter Teilbaum/Wurzel
Algorithmen
Greedyalgorithmen
Viele Probleme bestehen aus immer wiederkehrenden kleine Teilproblemen. Für diese können Musteralgorithmen geschrieben werden. Werden bei Bedarf nur angepasst und verwenden immer gl. Lösungsstrategie.
Versucht in jedem Schritt immer größtmöglichen Schritt zu nehmen. (entscheidung auf momentanen Informationen).
Für Optimierungsprobleme
Lösung = Kombi aus Eingabewerten
ges. = jede Kombi die in Verbindung den max Wert ergibt
Ideal zum finden des besten/kürzesten Transportweges zb in PCNetzwerken
Backtracking
Rekursion
Oft lassen sich Probleme als eine Abfolge von aufeinanderfolgenden Entscheidungen darstellen.
Alle möglichen Abfolgen bilden Lösungsraum.
Mittels Backtracking kann der gesamte Lösungsraum systematisch durchsucht werden. (Solange bis Lösung gefunden oder alle Wege ausprobiert)
Lösungsraum aknn oft als Baum dargestellt werden.
Start = Wurzel , Entscheidungen bis Blatt erreicht , - wenn keine Lösung schritt rückgängig.
Typischer Anwendungsfall = Rekursion (Algorithmen rufen sich selbst immer wieder für eine verringerte Problemgröße auf)
Divide and Conquer
Problem in immer kleinere Probleme aufgeteilt bis einfach gelöst werden können. Lösung alle Teilprobleme dann zusammengesetzt.
Beruhr auf Prinzip der Rekursion
Anwendung zb Suchalgorithmen (Liste in Hälfte/Hälfte/Hälfte usw. )
