TMA381 Tillämpade diskreta strukturer V 01

(Applied Discrete Structures)

I många kommunikationssystem översätter man information till följder av nollor och ettor. Antag att man vill sända två meddelanden 0 och 1. Överföringen sker med hjälp av t ex ledningar eller radiovågor eller på något annat sätt. Resultatet kan bli att beroende på störningar i kommunikations-kanalen nollan förvandlas till en etta eller tvärtom. Finns det någon möjlighet att skydda sig mot en sådan störning? En möjlig lösning är att upprepa 0 och 1 till exempel två gånger. Om den mottagna sekvensen är nu 01 eller 10 så kan man konstatera att det har inträffat ett fel. För att kunna rätta ett fel måste 0 och 1 upprepas minst tre gånger. För långa meddelanden blir en sådan procedur kostsam. Med algebraiska hjälpmedel kan betydligt bättre koder konstrueras.

Kursen behandlar datorinriktade matematiska strukturer av algebraisk och aritmetisk karaktär, som tillämpas bl a på kodning, kryptering och snabb addition och multiplikation.

I kursen ingår en datorlaboration byggd på det symbolhanterande språket REDUCE; laborationsmaterial och laborationsuppgifter utdelas under kursens gång. Den som så önskar kan istället använda t ex MAPLE eller MATHEMATICA.

• Tid och plats:

  Undervisningen äger rum onsdagar 8-12 och fredagar 13-17 i sal MD1, Matematiskt centrum med början onsdagen den 17 januari.

  OBS. Vi pröver en annan tid på fredagar: 9.00-12.00. Plats: Fr 09 feb i G7, rum 5312, Fr 16 feb i G2, 1339, Fr 23 feb i G5, 2340.

• Kurslitteratur:

  Juliusz Brzezinski och Jan Stevens: Tillämpade diskreta strukturer, kompendium, och stencilerat kursmaterial som utdelas på föreläsningarna.

• Examinationen sker genom en skrivning med teori- och problemuppgifter (50 poäng, 20 krävs för godkänt) samt redovisning av laborationsuppgiften, som skall vara inlämnad senast vecka 10. Den som klarar minst 50% av utdelade inlämningsuppgifter får 4 poäng tillgodo på skrivningen (gäller vt 01).

  Tentan: måndagen den 5 mars 2001, 14.15--18.15.

  Tentan är rättad. Lösningar finns.

  Gamla tentor:

  970318.

  980307 med losningar.

• Schema för föreläsningarna

  
  

  Vecka	Dag	Stoff	Kapitel	Inlämninguppgifter
  3	17/1	gruppkoder	11
  3	19/1	avkodning	11
  4	24/1	relationer, grupper	2--4	910312:1, 940905:1
  4	26/1	primtal, restgrupper	1,5
  5	31/1	kryptering, transformationsgrupper	14, 6	940905:3, 920317:5
  5	2/2	Lagrange's sats, ringar och kroppar	7, 8, 9
  6	7/2	kroppsutvidningar	10	960318:8, 920423:6
  6	9/2	polynomkoder	13
  7	14/2	booleska algebror, logik	15, app.	960318:4, 970318:4
  7	16/2	ändliga automater	16
  8	21/2	FFT	17	980307:4, 970318:2
  8	23/2	snabb multiplikation	18
  9	28/2	reserv		970318:5, 960318:7
  9	2/3	repetition
  10		tentamen

  (Stoffet som är grönt är avklarat, det som är rött utgår.)

  ---

  Jan Stevens <stevens@math.chalmers.se>
  Matematiskt Centrum, Eklandagatan 86, rum 1234, Telefon 772 5345.

  Last modified: Fri Mar 16 12:27:48 MET 2001