100% satisfaction guarantee Immediately available after payment Both online and in PDF No strings attached
logo-home
Zusammenfassung WS21/22 PVL Lösungen Theoretische Informatik I $5.40   Add to cart

Summary

Zusammenfassung WS21/22 PVL Lösungen Theoretische Informatik I

 13 views  1 purchase
  • Course
  • Institution

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.

Last document update: 1 year ago

Preview 4 out of 61  pages

  • February 11, 2023
  • February 11, 2023
  • 61
  • 2021/2022
  • Summary
avatar-seller
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

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

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

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.

Can Stuvia be trusted?

4.6 stars on Google & Trustpilot (+1000 reviews)

60904 documents were sold in the last 30 days

Founded in 2010, the go-to place to buy study notes for 14 years now

Start selling
$5.40  1x  sold
  • (0)
  Add to cart