BME VIK - Felsőbb matematika informatikusoknak C

vissza a tantárgylistához nyomtatható verzió

Felsőbb matematika informatikusoknak C

A tantárgy angol neve: Advanced Mathematics for Informaticians C

Adatlap utolsó módosítása: 2008. december 17.

Budapesti Műszaki és Gazdaságtudományi Egyetem
Villamosmérnöki és Informatikai Kar

Mérnök informatikus szak
MSc képzés

Tantárgykód	Szemeszter	Követelmények	Kredit	Tantárgyfélév
TE90MX42	1	4/0/0/v	4	1/1

3. A tantárgyfelelős személy és tanszék Dr. Rónyai Lajos,

4. A tantárgy előadója

Név:	Beosztás:	Tanszék, Intézet:
Dr. Rónyai Lajos	egyetemi tanár	Algebra Tanszék
Dr. Ferenczi Miklós	egyetemi docens	Algebra Tanszék

5. A tantárgy az alábbi témakörök ismeretére épít

Lineáris algebra

6. Előtanulmányi rend

Kötelező:

NEM ( TárgyEredmény( "BMETE90MX57" , "jegy" , _ ) >= 2
VAGY
TárgyEredmény("BMETE90MX57", "FELVETEL", AktualisFelev()) > 0)

A fenti forma a Neptun sajátja, ezen technikai okokból nem változtattunk.

A kötelező előtanulmányi rend az adott szak honlapján és képzési programjában található.

Ajánlott:
---

7. A tantárgy célkitűzése

Matematikai logika. A Matematikai logika legfontosabb fogalmainak feldolgozása és a témakör néhány informatikai alkalmazásának bemutatása, úgymint: gépi bizonyítás, logikai programozás, modellalkotás a mesterséges intelligencia részére, bonyolultságelmélet. Annak bemutatása, hogy a Matematikai logika minden fontos szintje, így a nyelv, a szemantika és a bizonyításelmélet is– fontos szerephez jut az elméleti számítástudományban. A tantárgy követelményeit eredményesen teljesítő minden hallgatótól elvárható, hogy:
– értse és konkrét feladatokban, példákon alkalmazni tudja a tárgyalt fogalmakat és ismereteket,
– a gyakorlati élet által felvetett problémákban felismerje a tanult módszerek alkalmazási lehetőségeit,
– legyen képes a szakirodalomra támaszkodva bővíteni az idevágó ismereteit.

Alkalmazott algebra. Az Algebra legintenzívebben alkalmazott területének a Lineáris algebrának és informatikai alkalmazásainak haladó tárgyalása. Ilyen alkalmazások például: a kódelméleti és kriptográfiai alkalmazások, a sztochasztikus mátrixok vizsgálata, valamint az SVD alkalmazása az információkeresési gyakorlatban. A Matematikai Logika és az Algebra szoros kapcsolatának bemutatása az állításlogika és a Boole algebrák kapcsolatának elemzésén keresztül. Tárgyaljuk ezen kapcsolat általánosítási lehetőségeit, valamint alkalmazását is.

A tantárgy követelményeit eredményesen teljesítő minden hallgatótól elvárható, hogy:
– értse és konkrét feladatokban, példákon alkalmazni tudja a tárgyalt fogalmakat és ismereteket,
– a gyakorlati élet által felvetett problémákban felismerje a tanult módszerek alkalmazási lehetőségeit,
– legyen képes a szakirodalomra támaszkodva bővíteni az idevágó ismereteit.

8. A tantárgy részletes tematikája Matematikai logika. (7 tényleges oktatási hét: 28 előadási óra). 1. Formális nyelv, formalizálás (2 óra). Tárgynyelv-metanyelv, infix-prefix írásmód, nulladrendű-magasabbrendű nyelv, egyértelmű olvashatóság. A nyelv elemei. Formulák és kifejezések.

2. Logikai szemantika - a halmazelméletre alapozva (6 óra). Struktúra, algebra, modell. Interpretáció. Az „igazság” definíciója – a halmazelméletre építve. Igazsághalmazok és tulajdonságaik. Különféle típusú modellek: állítás, elsőrendű, modális, stb. Példák mesterséges intelligenciabeli alkalmazásokra. A logikai következmény fogalom. Dedukció tétel. Nevezetes logikai ekvivalenciák. Normálformák: konjunktív, prenex, Skolem.

3. Bizonyításelmélet (6 óra). Az axiomatikus módszer. Levezetési és cáfolati bizonyítási rendszerek. Hilbert rendszer, analitikus fák, rezolúció. A logikai programozásról. Elmélet fogalma. Axiomatizálhatóság, eldönthetőség, ellentmondástalanság, teljesség. Kompaktsági tétel (szintaktikai). A gépi bizonyításról.

4. A szemantika és a bizonyításelmélet kapcsolatáról (4 óra). A logika (matematika) szemantikai és bizonyításelméleti megközelítése egyenértékű: Gödel teljességi tétele és változatai. Bizonyításelméleti fogalmak modellelméleti jellemzései, modell módszer. Egy elmélet ellentmondástalan a.cs.a ha kielégíthető. A kompaktsági tétel (szemantikai) és a végesítés fogalma.

A bizonyításelmélet korlátai: Gödel inkomplettségi és Church eldönthetetlenségi tételei. E tételek interpretációi a tudomány metodológiában. A Löwenheim-Skolem típusú tételek és jelentőségük. Kitekintés a magasabb rendű logikákra.

5. A Matematikai logika néhány további alkalmazása (4 óra). Néhány bonyolultsági osztály jellemzése logikai problémákkal, Fagin tétele. A végtelen kicsiny mennyiség (infinitezimális) bevezetése egy modell konstrukció, az ultrahatvány ill. a kompaktsági tétel segítségével. A valós számfogalom bővítése: a hipervalós számok. Newton és Leibniz analízisének rekonstrukciója e fogalmak segítségével: Nem-standard analízis. A folytonosság, differenciálhatóság és integrálhatóság nem-standard definíciói.

6. Matematikai logika és az Algebra kapcsolatáról (4 óra). Néhány párhuzamba állítható logikai és Boole algebrai fogalom: elmélet – szűrő, komplettség – prím, levezethető – kisebb, axiómák üres halmaza – szabad algebra, axiómák feltételezése – relativizálás, stb. A szóban forgó kapcsolat alkalmazása a valószínűségszámításban (eseményalgebrák) és hálózatok elemzésénél. Általánosítások elsőrendű logikára.

Alkalmazott algebra. (7 tényleges oktatási hét: 28 előadási óra).

1. A lineáris algebra tanult fogalmainak áttekintése (4 óra). Vektorterek, alterek, bázis, dimenzió. Lineáris leképezések, képtér, magtér, dimenzió tétel, műveletek lineáris leképezésekkel. Mátrixok, mint formális objektumok. Lineáris leképezések és műveleteik reprezentátálása mátrixokkal. Báziscsere. Sajátérték, sajátvektor, sajátaltér. Diagonizálás, spektrál felbontás. Mátrix hatványa.

Lineáris egyenletrendszerek disszkussziója. Megoldás Gauss eliminációval. Determináns fogalma.

2. Lineáris operátorok véges dimenziós euklídeszi terekben, normálformák (4 óra). Euklideszi tér fogalma. Szimmetrikus, önadjungált, unitér, normális, projektor operátorok és mátrixaik. Jordan normálforma.

3. Nemnegatív elemű mátrixok (6 óra). Pozitív, reducibilis és irreducibilis mátrixok. Frobenius és Perron tételei (irreducibilis nemnegatív mátrixokra). Egyenlőtlenségek a spektrálsugárra. Sztochasztikus és duplán sztochasztikus mátrixok. Kapcsolat a Markov-láncokkal. Birkhoff tétele, kapcsolat a párosítási feladattal, a Frobenius–König-tétel.

4. Szinguláris értékek szerinti felbontás (SVD) (6 óra). Létezése, egyértelműsége, kapcsolata a poláris felbontással. SVD és alacsony rangú közelítések, Eckart–Young-tétel. Az SVD számítása. A módszer néhány alkalmazása (pszeudoinverz számítása, homogén lineáris egyenletrendszer megoldása, legkisebb négyzetek módszere). A QR-felbontás fogalma. Householder-tükrözések, alkalmazásuk a QR-felbontás számítására.

5. A lineáris algebra további alkalmazásairól (6 óra). A lineáris algebra néhány nevezetes alkalmazása: nemnegatív és szimmetrikus mátrixok az internetes lapokat rangsoroló algoritmusokban; SVD az információkeresés gyakorlatában (vektorteres indexelés, a mögöttes szemantikájú indexelés lineáris algebrai vonatkozásai); hibajavító kódok; titokmegosztás.

9. A tantárgy oktatásának módja (előadás, gyakorlat, laboratórium)

A tárgy anyaga előadásokon kerül ismertetésre.

10. Követelmények

a. A szorgalmi időszakban: két zárthelyi

b. A vizsgaidőszakban: a két tárgyblokkból közös vizsga. A vizsgajegy megállapítása felerészben a zárthelyik eredménye és felerészben a vizsga alapján történik

Az aláírás megszerzésének feltétele a zárthelyi dolgozatok teljesítése egyenként legalább 40%-ra. A vizsgára bocsátás feltétele az aláírás megléte.

11. Pótlási lehetőségek

- mindenki legfeljebb egy zárthelyit pótolhat, de azt esetleg kétszer

- két pótzárthelyit tartunk a szorgalmi időszakban, de minden hallgató legfeljebb az egyiken vehet részt (akinek két sikertelen zh-ja van, nem kaphat aláírást)

- egy további pót-pótzárthelyit tartunk a pótlási héten (két feladatsorral, amelyiken mindenki a pótlandó (egy) zárthelyijét pótolhatja).

12. Konzultációs lehetőségek Vizsgák előtt a hallgatókkal egyeztetve.

13. Jegyzet, tankönyv, felhasználható irodalom

[1] Ferenczi Miklós: Matematikai logika, Műszaki kiadó, 2002.

[2] V.V. Praszolov: Lineáris algebra, Typotex, 2005.

[3] Rózsa Pál: Lineáris algebra és alkalmazásai, Tankönyvkiadó, 1991.

[4] Halmos Pál: Véges dimenziós vektorterek, Műszaki Kiadó, 1984.

14. A tantárgy elvégzéséhez átlagosan szükséges tanulmányi munka

Kontakt óra	56
Félévközi készülés órákra	10
Felkészülés zárthelyire	28
Házi feladat elkészítése
Kijelölt írásos tananyag elsajátítása
Vizsgafelkészülés	26
Összesen	120

15. A tantárgy tematikáját kidolgozta

Név:	Beosztás:	Tanszék, Int.:
Dr. Rónyai Lajos	egyetemi tanár	Algebra Tanszék
Dr. Ferenczi Miklós	egyetemi docens	Algebra Tanszék

Budapest University of Technology and Economics, Faculty of Electrical Engineering and Informatics

Felsőbb matematika informatikusoknak C