Zusammenfassung WS21/22 PVL Lösungen Theoretische Informatik I
13 views 1 purchase
Course
Theoretische Informatik I (500210)
Institution
Technische Universität Chemnitz (TU Chemnit)
Das Dokument enthällt alle Aufgabenstellungen.
Meine Abgabe zur PVL ist für Übungen 1 bis 6 und 8 bis 10 enthalten
Zu meinen abgegebenen Lösungen ist das erhaltene Feedback sinngemäß wiedergegeben.
Übungen 7 und 11 is 13 sind mit Aufgabenstellung enthalten.
Technische Universität Chemnitz (TU Chemnit)
Angewandte Informatik
Theoretische Informatik I (500210)
All documents for this subject (1)
Seller
Follow
felixmueb
Content preview
Prof. Dr. A. Goerdt TU Chemnitz
Julian Pape-Lange Wintersemester 2021/2022
13.10.2021
Theoretische Informatik I
1. Übung
Abgabe: Lösen Sie Aufgaben 1 und 2 handschriftlich. Ihre Lösungen geben Sie bitte
entweder
• bis zum 21.10.2021 um 13:00 Uhr per Mail
an julian.pape-lange@informatik.tu-chemnitz.de
mit Betreff: TI1 Hausaufgaben oder
• bis zum 21.10.2021 um 13:00 Uhr im Briefkasten der Professur Theoretische Infor-
matik (vor Raum A10.266.4)
ab.
1. Aufgabe: ((1+1+3)P)
Gegeben sei folgender gerichteter Graph G.
1 - 2 3
?
?
?
4 5 6
(a) Stellen Sie G durch Adjazenzlisten dar.
(b) Stellen Sie G durch eine Adjazenzmatrix dar.
(c) Zeigen Sie mit dem Algorithmus aus der Vorlesung, dass G kreisfrei ist und geben
Sie zu jedem Knoten an, in welcher Löschung er entfernt wird. Geben Sie auch eine
topologische Sortierung der Knoten an.
2. Aufgabe: ((3+2)P)
(a) Geben Sie einen Algorithmus an, der die Anzahl der Kreise mit Länge 2 in einem
gegebenen gerichteten Graphen ermittelt.
(b) Geben Sie eine Abschätzung für die Laufzeit Ihres Algorithmus an.
3. Aufgabe: Programmieren Sie eine (Warte-)Schlange (FIFO-Speicher).
4. Aufgabe: Für viele Algorithmen wollen wir, dass die Knoten von Graphen die Zahlen
von 1 bis |V | sind. In der Praxis kann es aber passieren, dass die Knoten andere Namen
haben.
Erklären Sie, wie wir Graphen mit beliebigen Knotennamen in Graphen mit den Knoten
von 1 bis |V | umwandeln können.
1
,
,
,
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller felixmueb. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $5.40. You're not tied to anything after your purchase.