Institut für Theoretische Informatik, Algorithmik

Theoretische Grundlagen der Informatik

Allgemeines

  • Übungsleiter: Jonas Sauer, Guido Brückner
  • Termine: in der Regel
    • dienstags um 11.30-13.00 Uhr im Gerthsen-HS (30.21) und
    • donnerstags um 11.30-13.00 Uhr im Gerthsen-HS (30.21)
  • Hauptklausur: am 20. Juni 2020 von 10:00-12:00 Uhr
  • Nachklausur: am 16. September 2020 von 16:00-18:00 Uhr
Die Klausurergebnisse sind da! Ihre Klausur-ID entspricht einer Stadt, an deren Stelle auf der Karte Ihr Ergebnis eingetragen ist. Notenverteilung und Punkteschlüssel finden Sie hier.

operating instructions

Various functions are available as part of the map.

mouse/touch operation
  • moving by grabbing the map with a mouse-click you can move the map around
  • overview map using the < button in the bottom right of the map you can expand an overview map
  • zooming in and out using the + and - buttons in the top left of the map you can obtain more or less detail in the map
  • switching themes or maps clicking on the ≡ icon on the right-hand side of the map you can view and select available maps and themes
  • retrieving information the map may contain elements that contain more information, by clicking these a popup will show this information
  • fullscreen display using the ✈ button the map can be maximized to fullscreen display, use the ✕ button to return to page display.
keyboard operation

Keyboard operation becomes available after activating the map using the tab key (the map will show a focus indicator ring).

  • moving using the arrow keys you can move the map
  • overview map using the + button in the bottom right of the map you can expand an overview map
  • zooming in and out using the + and - buttons in the top left of the map or by using the + and - keys you can obtain more or less detail in the map
  • switching themes or maps clicking on the ≡ icon on the right-hand side of the map you can view and select available maps and themes
  • retrieving information the map may contain elements that contain more information, using the i key you can activate a cursor that may be moved using the arrow keys, pressing the enter will execute an information retrieval. press the i or the escape key to return to navigation mode
  • fullscreen display using the ✈ button the map can be maximized to fullscreen display, use the ✕ button to return to page display.

It's possible that some of the functions or buttons describe above have been disabled by the page author or the administrator

 

Points of Interest
id symbol latitude longitude description
1 marker-green 42.9075º 20.8403º

Zveçan (ZVECAN): 30.5 Punkte inkl. Bonus

2 marker-red 46.2750º 15.7939º

Žetale (ZETALE): 12.5 Punkte inkl. Bonus

3 marker-green 41.9825º 21.0624º

Želino (ZELINO): 20 Punkte inkl. Bonus

4 marker-green 35.8719º 14.4411º

Żebbuġ (ZEBBUG): 42.5 Punkte inkl. Bonus

5 marker-green 40.2184º 47.7121º

Zərdab (ZARDAB): 32.5 Punkte inkl. Bonus

6 marker-green 44.3562º 21.2143º

Žabari (ZABARI): 27 Punkte inkl. Bonus

7 marker-red 45.3741º 20.0707º

Žabalj (ZABALJ): 17 Punkte inkl. Bonus

8 marker-green 42.4833º 26.5000º

Yambol (YAMBOL): 39.5 Punkte inkl. Bonus

9 marker-green 40.6550º 29.2769º

Yalova (YALOVA): 37.5 Punkte inkl. Bonus

10 marker-red 39.9130º 46.7903º

Xocalı (XOCALI): 5.5 Punkte inkl. Bonus

11 marker-red 36.0500º 14.2644º

Xagħra (XAGHRA): 18.5 Punkte inkl. Bonus

12 marker-red 41.4643º 48.8057º

Xaçmaz (XACMAZ): 12.5 Punkte inkl. Bonus

13 marker-green 0.4044º 32.4594º

Wakiso (WAKISO): 54 Punkte inkl. Bonus

14 marker-green 42.5560º 21.9002º

Vranje (VRANJE): 26 Punkte inkl. Bonus

15 marker-green 46.2933º 15.3033º

Vojnik (VOJNIK): 33 Punkte inkl. Bonus

16 marker-green 46.2000º 14.5000º

Vodice (VODICE): 39 Punkte inkl. Bonus

17 marker-green 45.8467º 13.9631º

Vipava (VIPAVA): 28.5 Punkte inkl. Bonus

18 marker-red 41.8828º 22.5092º

Vinica (VINICA): 6 Punkte inkl. Bonus

19 marker-red 46.5836º 16.1653º

Veržej (VERZEJ): 18 Punkte inkl. Bonus

20 marker-red -13.7555º -172.3070º

Vailoa (VAILOA): 3 Punkte inkl. Bonus

21 marker-red 41.9283º 19.2064º

Ulcinj (ULCINJ): 7.5 Punkte inkl. Bonus

22 marker-red 4.8028º 114.6492º

Tutong (TUTONG): 14.5 Punkte inkl. Bonus

23 marker-green -9.1031º 160.1506º

Tulagi (TULAGI): 25 Punkte inkl. Bonus

24 marker-green 56.9676º 23.1555º

Tukums (TUKUMS): 41.5 Punkte inkl. Bonus

25 marker-red 54.6399º 24.9360º

Trakai (TRAKAI): 15 Punkte inkl. Bonus

26 marker-red 44.2544º 20.6824º

Topola (TOPOLA): 17.5 Punkte inkl. Bonus

27 marker-green 46.1864º 13.7361º

Tolmin (TOLMIN): 62.5 Punkte inkl. Bonus

28 marker-red 62.0978º -6.7369º

Toftir (TOFTIR): 12 Punkte inkl. Bonus

29 marker-red 46.6581º 16.0917º

Tišina (TISINA): 11.5 Punkte inkl. Bonus

30 marker-red 36.5897º 2.4475º

Tipasa (TIPASA): 17.5 Punkte inkl. Bonus

31 marker-red 41.9198º 45.4732º

Telavi (TELAVI): 10 Punkte inkl. Bonus

32 marker-green 42.0767º 21.0531º

Tearce (TEARCE): 20 Punkte inkl. Bonus

33 marker-green 40.3420º 46.9316º

Tərtər (TARTAR): 27 Punkte inkl. Bonus

34 marker-red 53.4597º -6.2181º

Swords (SWORDS): 8.5 Punkte inkl. Bonus

35 marker-red 41.1780º 20.6778º

Struga (STRUGA): 18.5 Punkte inkl. Bonus

36 marker-red 45.7800º 15.0728º

Straža (STRAZA): 13.5 Punkte inkl. Bonus

37 marker-red 46.4658º 15.7672º

Starše (STARSE): 19 Punkte inkl. Bonus

38 marker-red 48.1566º 28.2849º

Soroca (SOROCA): 13 Punkte inkl. Bonus

39 marker-green 47.6864º 16.5906º

Sopron (SOPRON): 33.5 Punkte inkl. Bonus

40 marker-red 45.7742º 19.1151º

Sombor (SOMBOR): 16.5 Punkte inkl. Bonus

41 marker-red 0.7373º 127.5588º

Sofifi (SOFIFI): 19 Punkte inkl. Bonus

42 marker-green 51.5000º -0.5833º

Slough (SLOUGH): 38.5 Punkte inkl. Bonus

43 marker-green 37.5139º 42.4543º

Şırnak (SIRNAK): 30 Punkte inkl. Bonus

44 marker-red 55.3453º 21.4733º

Šilutė (SILUTE): 3 Punkte inkl. Bonus

45 marker-green 33.1757º 68.7304º

Sharan (SHARAN): 20 Punkte inkl. Bonus

46 marker-green 45.7069º 13.8722º

Sežana (SEZANA): 52 Punkte inkl. Bonus

47 marker-red 1.5180º 33.4589º

Serere (SERERE): 15.5 Punkte inkl. Bonus

48 marker-red 46.2456º 14.4197º

Šenčur (SENCUR): 19.5 Punkte inkl. Bonus

49 marker-red 36.6092º 127.2919º

Sejong (SEJONG): 19.5 Punkte inkl. Bonus

50 marker-green 45.3676º 20.7732º

Sečanj (SECANJ): 26.5 Punkte inkl. Bonus

51 marker-red 47.1661º 9.5096º

Schaan (SCHAAN): 9.5 Punkte inkl. Bonus

52 marker-red 26.8990º 89.0995º

Samtse (SAMTSE): 7 Punkte inkl. Bonus

53 marker-green 40.8297º 46.0178º

Şəmkir (SAMKIR): 29 Punkte inkl. Bonus

54 marker-green 39.5962º 48.9848º

Salyan (SALYAN): 20 Punkte inkl. Bonus

55 marker-green 6.7362º 2.6587º

Sakété (SAKETE): 28 Punkte inkl. Bonus

56 marker-red -13.4513º -172.4018º

Safotu (SAFOTU): 8.5 Punkte inkl. Bonus

57 marker-green 39.9321º 48.3689º

Saatlı (SAATLI): 21 Punkte inkl. Bonus

58 marker-red 42.8439º 20.1683º

Rožaje (ROZAJE): 9 Punkte inkl. Bonus

59 marker-red 47.7493º 28.9658º

Rezina (REZINA): 0 Punkte inkl. Bonus

60 marker-green 49.5450º 6.3669º

Remich (REMICH): 33.5 Punkte inkl. Bonus

61 marker-red 43.6744º 21.5492º

Ražanj (RAZANJ): 8.5 Punkte inkl. Bonus

62 marker-green 46.0681º 15.1839º

Radeče (RADECE): 30.5 Punkte inkl. Bonus

63 marker-green 35.8347º 14.4583º

Qrendi (QRENDI): 41.5 Punkte inkl. Bonus

64 marker-red 39.3994º 45.1151º

Qıvraq (QIVRAQ): 15 Punkte inkl. Bonus

65 marker-green 40.9825º 47.8491º

Qəbələ (QABALA): 26.5 Punkte inkl. Bonus

66 marker-green 41.3451º 21.5550º

Prilep (PRILEP): 31.5 Punkte inkl. Bonus

67 marker-red 56.2940º 26.7248º

Preiļi (PREILI): 5.5 Punkte inkl. Bonus

68 marker-green 43.8459º 20.0368º

Požega (POZEGA): 32 Punkte inkl. Bonus

69 marker-green 43.8459º 20.0368º

Požega (POZEGA): 30.5 Punkte inkl. Bonus

70 marker-green 49.0117º 8.4164º

[koeri]werk (POMMES): 23 Punkte inkl. Bonus

71 marker-red 17.1503º -25.0201º

Pombas (POMBAS): 17 Punkte inkl. Bonus

72 marker-red 55.9077º 21.8456º

Plungė (PLUNGE): 17 Punkte inkl. Bonus

73 marker-red 18.3942º 103.6611º

Pakxan (PAKXAN): 4.5 Punkte inkl. Bonus

74 marker-green 12.8489º 102.6093º

Pailin (PAILIN): 23.5 Punkte inkl. Bonus

75 marker-red -17.5000º 14.9833º

Outapi (OUTAPI): 10 Punkte inkl. Bonus

76 marker-red 42.5563º 1.5327º

Ordino (ORDINO): 15.5 Punkte inkl. Bonus

77 marker-red 56.7947º 23.9358º

Olaine (OLAINE): 11.5 Punkte inkl. Bonus

78 marker-red 45.5076º 19.2606º

Odžaci (ODZACI): 18 Punkte inkl. Bonus

79 marker-green 48.3827º 27.4381º

Ocniţa (OCNITA): 60.5 Punkte inkl. Bonus

80 marker-red 42.6869º 21.0703º

Obiliq (OBILIQ): 9.5 Punkte inkl. Bonus

81 marker-red 52.6667º -0.7333º

Oakham (OAKHAM): 19 Punkte inkl. Bonus

82 marker-red 42.7750º 18.9583º

Nikšić (NIKSIC): 14.5 Punkte inkl. Bonus

83 marker-green 52.8619º -8.1967º

Nenagh (NENAGH): 27.5 Punkte inkl. Bonus

84 marker-green 35.9136º 14.4436º

Naxxar (NAXXAR): 41 Punkte inkl. Bonus

85 marker-green 26.1504º 119.9328º

Nangan (NANGAN): 41 Punkte inkl. Bonus

86 marker-green 36.0300º 14.2333º

Munxar (MUNXAR): 37 Punkte inkl. Bonus

87 marker-red 27.2747º 91.2396º

Mongar (MONGAR): 7.5 Punkte inkl. Bonus

88 marker-red -0.6842º 30.0700º

Mitoma (MITOMA): 19 Punkte inkl. Bonus

89 marker-red -1.0634º 34.4731º

Migori (MIGORI): 17.5 Punkte inkl. Bonus

90 marker-green 46.5214º 14.8544º

Mežica (MEZICA): 27 Punkte inkl. Bonus

91 marker-red 36.8004º 34.6128º

Mersin (MERSIN): 7 Punkte inkl. Bonus

92 marker-green 49.7489º 6.1061º

Mersch (MERSCH): 21 Punkte inkl. Bonus

93 marker-green 46.1669º 14.5750º

Mengeš (MENGES): 33 Punkte inkl. Bonus

94 marker-red 0.4578º 33.4806º

Mayuge (MAYUGE): 11 Punkte inkl. Bonus

95 marker-green 47.2205º 9.5426º

Mauren (MAUREN): 53 Punkte inkl. Bonus

96 marker-red 56.9032º 24.0467º

Mārupe (MARUPE): 16.5 Punkte inkl. Bonus

97 marker-green -2.6806º 118.8861º

Mamuju (MAMUJU): 23.5 Punkte inkl. Bonus

98 marker-green 46.3172º 15.6672º

Makole (MAKOLE): 28 Punkte inkl. Bonus

99 marker-green 31.7160º 35.7939º

Mādabā (MADABA): 29 Punkte inkl. Bonus

100 marker-green -0.4161º 31.4081º

Lwengo (LWENGO): 41 Punkte inkl. Bonus

101 marker-green 0.8492º 32.4731º

Luwero (LUWERO): 24 Punkte inkl. Bonus

102 marker-red 43.8608º 20.1384º

Lučani (LUCANI): 14.5 Punkte inkl. Bonus

103 marker-green 46.3456º 14.8350º

Ljubno (LJUBNO): 38.5 Punkte inkl. Bonus

104 marker-green 46.0586º 14.8225º

Litija (LITIJA): 37 Punkte inkl. Bonus

105 marker-green 42.5217º 21.1258º

Lipjan (LIPJAN): 29.5 Punkte inkl. Bonus

106 marker-green 42.9171º 21.7294º

Lebane (LEBANE): 21.5 Punkte inkl. Bonus

107 marker-green 5.2803º 115.2475º

Labuan (LABUAN): 44 Punkte inkl. Bonus

108 marker-red 45.6100º 13.9356º

Kozina (KOZINA): 11 Punkte inkl. Bonus

109 marker-green 40.3007º 21.7890º

Kozáni (KOZANI): 41 Punkte inkl. Bonus

110 marker-red 8.9126º 17.5539º

Koumra (KOUMRA): 14.5 Punkte inkl. Bonus

111 marker-green -4.3525º 152.2606º

Kokopo (KOKOPO): 22 Punkte inkl. Bonus

112 marker-green 41.9164º 22.4128º

Kočani (KOCANI): 27.5 Punkte inkl. Bonus

113 marker-green 35.8422º 14.4853º

Kirkop (KIRKOP): 39 Punkte inkl. Bonus

114 marker-green 41.5127º 20.9589º

Kičevo (KICEVO): 31.5 Punkte inkl. Bonus

115 marker-green 1.0433º 33.7975º

Kibuku (KIBUKU): 42 Punkte inkl. Bonus

116 marker-green 36.0419º 14.2267º

Kerċem (KERCEM): 43 Punkte inkl. Bonus

117 marker-green 56.8296º 24.2318º

Ķekava (KEKAVA): 34 Punkte inkl. Bonus

118 marker-green 58.9978º 22.7492º

Kärdla (KARDLA): 24 Punkte inkl. Bonus

119 marker-green 0.1772º 31.8811º

Kanoni (KANONI): 26.5 Punkte inkl. Bonus

120 marker-red 46.2197º 14.6094º

Kamnik (KAMNIK): 14 Punkte inkl. Bonus

121 marker-green 0.8949º 33.5048º

Kaliro (KALIRO): 39 Punkte inkl. Bonus

122 marker-red 0.9378º 30.8089º

Kagadi (KAGADI): 18 Punkte inkl. Bonus

123 marker-green 10.6584º 122.5963º

Jordan (JORDAN): 27 Punkte inkl. Bonus

124 marker-red 55.0801º 24.2754º

Jonava (JONAVA): 13 Punkte inkl. Bonus

125 marker-green 58.7467º 26.3939º

Jõgeva (JOGEVA): 23 Punkte inkl. Bonus

126 marker-red 32.2808º 35.8993º

Jarash (JARASH): 5.5 Punkte inkl. Bonus

127 marker-green 55.6000º -4.6667º

Irvine (IRVINE): 33 Punkte inkl. Bonus

128 marker-red 45.0482º 20.0816º

Inđija (INDIJA): 16 Punkte inkl. Bonus

129 marker-red 39.8724º 48.0649º

İmişli (IMISLI): 18.5 Punkte inkl. Bonus

130 marker-red 35.9206º 14.3664º

Imġarr (IMGARR): 18 Punkte inkl. Bonus

131 marker-green 35.8869º 14.4025º

Imdina (IMDINA): 41 Punkte inkl. Bonus

132 marker-red 17.1485º 121.8892º

Ilagan (ILAGAN): 18 Punkte inkl. Bonus

133 marker-red 40.8788º 45.1485º

Ijevan (IJEVAN): 13 Punkte inkl. Bonus

134 marker-red 15.0339º -24.3250º

Igreja (IGREJA): 10 Punkte inkl. Bonus

135 marker-red 56.5977º 24.2076º

Iecava (IECAVA): 5 Punkte inkl. Bonus

136 marker-green 46.0028º 14.0306º

Idrija (IDRIJA): 24.5 Punkte inkl. Bonus

137 marker-green -0.1539º 30.5319º

Ibanda (IBANDA): 22 Punkte inkl. Bonus

138 marker-red 46.0236º 14.2992º

Horjul (HORJUL): 16 Punkte inkl. Bonus

139 marker-red 40.5858º 46.3189º

Göygöl (GOYGOL): 15 Punkte inkl. Bonus

140 marker-red 42.4689º 21.4633º

Gjilan (GJILAN): 8 Punkte inkl. Bonus

141 marker-green 35.8489º 14.5167º

Għaxaq (GHAXAQ): 26 Punkte inkl. Bonus

142 marker-red 36.0578º 14.2264º

Għasri (GHASRI): 15 Punkte inkl. Bonus

143 marker-green 39.6009º 47.1453º

Füzuli (FUZULI): 38.5 Punkte inkl. Bonus

144 marker-red 47.2109º 9.5216º

Eschen (ESCHEN): 18.5 Punkte inkl. Bonus

145 marker-green 42.5361º 1.5828º

Encamp (ENCAMP): 47.5 Punkte inkl. Bonus

146 marker-green 54.7667º -1.5667º

Durham (DURHAM): 30 Punkte inkl. Bonus

147 marker-green 1.9167º 33.1720º

Dokolo (DOKOLO): 21.5 Punkte inkl. Bonus

148 marker-green 46.3375º 15.2264º

Dobrna (DOBRNA): 45 Punkte inkl. Bonus

149 marker-red 45.6847º 13.9703º

Divača (DIVACA): 7 Punkte inkl. Bonus

150 marker-green 35.8614º 14.3822º

Dingli (DINGLI): 43.5 Punkte inkl. Bonus

151 marker-green 41.2012º 48.9871º

Dəvəçi (DAVACI): 24.5 Punkte inkl. Bonus

152 marker-green 49.4867º 105.9228º

Darhan (DARHAN): 51 Punkte inkl. Bonus

153 marker-red 8.0662º 0.1795º

Dambai (DAMBAI): 13 Punkte inkl. Bonus

154 marker-red 46.2946º 28.6565º

Comrat (COMRAT): 11.5 Punkte inkl. Bonus

155 marker-red 46.1256º 13.9817º

Cerkno (CERKNO): 13 Punkte inkl. Bonus

156 marker-green 52.8408º -6.9261º

Carlow (CARLOW): 25.5 Punkte inkl. Bonus

157 marker-green 27.7006º 83.4484º

Butwāl (BUTWAL): 33 Punkte inkl. Bonus

158 marker-green 1.1942º 33.9222º

Butebo (BUTEBO): 24.5 Punkte inkl. Bonus

159 marker-green 0.9061º 34.3578º

Bupoto (BUPOTO): 23.5 Punkte inkl. Bonus

160 marker-red 2.1178º 31.4116º

Bulisa (BULISA): 19.5 Punkte inkl. Bonus

161 marker-green 0.3375º 33.0106º

Buikwe (BUIKWE): 54.5 Punkte inkl. Bonus

162 marker-green 1.0112º 34.3311º

Bududa (BUDUDA): 32 Punkte inkl. Bonus

163 marker-green 17.0899º 120.9780º

Bontoc (BONTOC): 20.5 Punkte inkl. Bonus

164 marker-red 53.5833º -2.4333º

Bolton (BOLTON): 18.5 Punkte inkl. Bonus

165 marker-green 43.0142º 21.7180º

Bojnik (BOJNIK): 33 Punkte inkl. Bonus

166 marker-green 1.4167º 34.5333º

Binyin (BINYIN): 36 Punkte inkl. Bonus

167 marker-green 42.8425º 19.8733º

Berane (BERANE): 25 Punkte inkl. Bonus

168 marker-green 46.8316º 29.4777º

Bender (BENDER): 24.5 Punkte inkl. Bonus

169 marker-red 56.4079º 24.1944º

Bauska (BAUSKA): 14 Punkte inkl. Bonus

170 marker-green -8.4757º 126.4563º

Baucau (BAUCAU): 26 Punkte inkl. Bonus

171 marker-green 40.0626º 70.8194º

Batken (BATKEN): 24 Punkte inkl. Bonus

172 marker-red 41.6358º 32.3375º

Bartın (BARTIN): 7 Punkte inkl. Bonus

173 marker-green 35.8897º 14.4425º

Attard (ATTARD): 40 Punkte inkl. Bonus

174 marker-red 38.4560º 48.8750º

Astara (ASTARA): 19 Punkte inkl. Bonus

175 marker-green 54.3481º -6.6496º

Armagh (ARMAGH): 34.5 Punkte inkl. Bonus

176 marker-red 43.7550º 20.0970º

Arilje (ARILJE): 15.5 Punkte inkl. Bonus

177 marker-green -25.3125º -57.3847º

Areguá (AREGUA): 50 Punkte inkl. Bonus

178 marker-red 45.6709º 18.9843º

Apatin (APATIN): 14.5 Punkte inkl. Bonus

179 marker-green 2.0036º 33.6511º

Amuria (AMURIA): 38 Punkte inkl. Bonus

180 marker-red 1.9500º 34.9500º

Amudat (AMUDAT): 16 Punkte inkl. Bonus

181 marker-red 54.3964º 24.0414º

Alytus (ALYTUS): 10 Punkte inkl. Bonus

182 marker-green -8.9969º 125.5050º

Ainaro (AINARO): 38 Punkte inkl. Bonus

Inhalt der theoretischen Informatik

Im Gegensatz zu anderen Grundstudiumsvorlesungen werden in der theoretischen Informatik Themen behandelt, die weiter von den Anwendungen entfernt sind. Es geht um prinzipielle Fragestellungen, d.h. Fragen, die unabhängig von „Programmierungsaspekten“ oder „konkreten Rechnern“ sind: Gibt es Aufgaben, die von einem Rechner — unabhängig von der Art der Programmierung beziehungsweise von physikalischen und elektronischen Beschränkungen — nicht gelöst werden können? Welche Aufgaben können prinzipiell effizient (in vernünftiger Rechenzeit, mit vernünftigem Speicherplatzbedarf) gelöst werden?

Vorlesungs-/Übungstermine

Änderungen vorbehalten!

Literatur

  • Scott Aaronson, P =?= NP
  • Ingo Wegener, Theoretische Informatik, B.G. Teubner Verlag Stuttgart, 1993
  • Uwe Schöning, Theoretische Informatik - kurzgefasst, Hochschultaschenbuch, Spektrum Akademischer Verlag, 1997
  • R. Garey und D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, New York, 1979
  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Introduction to Algorithms, The MIT press, 1997, 2001.
  • Alexander Asteroth, Christel Baier, Theoretische Informatik: eine Einführung in Berechenbarkeit, Komplexität und formale Sprachen mit 101 Beispielen, Pearson Studium, 2002, ISBN 3-8273-7033-7
  • Martin Werner: Information und Codierung, VIEWEG TEUBNER, 2008, ISBN 978-3-8348-0232-3.
  • Sanjeev Arora und Boaz Barak: Computational Complexity: A Modern Approach
  • Juraj Hromkovic: Theoretical Computer Science, Springer-Verlag Berlin Heidelberg, 2011, ISBN 978-3-642-05729-8.

Die KIT-Bibliothek stellt einen Semesterapparat mit diesen Titeln im Lesesaal Geisteswissenschaften im 3. OG bereit.

(Veraltete) Skripte

Bitte beachten Sie, dass diese Skripte nicht mehr gepflegt werden. Es kann Abweichungen zum aktuellen Stoff der TGI-Vorlesung geben.

Übung, Übungsblätter und Tutorien

Neue Übungsblätter werden voraussichtlich alle zwei Wochen veröffentlicht. Die Aufgaben sollen schriftlich bearbeitet und die handschriftlichen Lösungen in den mit „Theoretische Grundlagen der Informatik“ beschrifteten Einwurfschlitz im Keller des Informatik-Hauptgebäudes (50.34) eingeworfen werden. Es gilt der Abgabetermin, der direkt auf dem Übungsblatt steht.
Die Bearbeitung und Abgabe der Aufgaben kann dabei in Zweiergruppen erfolgen! (Wichtig: Dazu ist bitte darauf zu achten, dass beide Studenten im selben Tutorium sind.) Ausgedruckte oder kopierte Lösungsblätter werden NICHT akzeptiert, das heißt, es müssen handschriftliche Lösungen abgegeben werden. Für abgeschriebene Lösungen gibt es auf das gesamte Übungsblatt keine Punkte. Wenn auf mehreren Übungsblättern abgeschrieben wird, werden keine Bonuspunkte vergeben.

Übungsblätter Lösungsvorschläge
Übungsblatt 1 (Update 3.11.) Lösungsvorschlag (Update 11.3.)
Übungsblatt 2 (Update 7.11.) Lösungsvorschlag
Übungsblatt 3 Lösungsvorschlag
Übungsblatt 4 (Update 16.12.) Lösungsvorschlag
Übungsblatt 5 (Update 13.1.) Lösungsvorschlag
Übungsblatt 6 (Update 14.1.) Lösungsvorschlag (Update 24.1.)
Übungsblatt 7 (Update 27.1.) Lösungsvorschlag

Klausurbonus

Werden mindestens 25% (50%, 75%) der möglichen Gesamtpunktzahl auf allen Übungsblättern erreicht, werden auf die bestandene Klausur 1 (2, 3) Bonuspunkte angerechnet. Es wird voraussichtlich 7 Übungsblätter mit jeweils ca. 30 Punkten geben. Die erreichbare Punktzahl pro Übungsblatt ist nicht unbedingt jedes Mal genau dieselbe! Die Bonuspunktegrenzen sind:

  • Bei insgesamt 52 Punkten oder mehr gibt es einen Bonuspunkt.
  • Bei insgesamt 105 Punkten oder mehr gibt es zwei Bonuspunkte.
  • Bei insgesamt 157 Punkten oder mehr gibt es drei Bonuspunkte.

Nur Bonuspunkte, die im WS 19/20 erworben wurden, werden auf die Klausur angerechnet. Bonuspunkte aus zurückliegenden Semestern werden nicht anerkannt. Ebenso gibt es keine Garantie, dass Bonuspunkte aus dem WS 19/20 in späteren TGI-Klausuren anerkannt werden. Studierende, die die Vorlesung bereits gehört, jedoch die Klausur noch nicht geschrieben haben und ihre alten Bonuspunkte nicht mehr anrechnen können, haben die Möglichkeit, sich im WS 19/20 erneut für ein Tutorium einzutragen und die Übungsblätter erneut zu bearbeiten.

Beschriftung der Übungsblätter

Bitte beschriften Sie das Deckblatt Ihrer Abgabe gut sichtbar mit Name, Matrikelnummer und Nummer des Tutoriums.

Klausur und Klausurvorbereitung

Alte Klausuren