Fogalomlista

by pts@fazekas.hu at Tue Jan 23 19:41:20 CET 2007 -- Tue Jan 23 21:45:53 CET 2007

Ha oktatóként jutottál ide, és jót akarsz a hallgatóknak, akkor az alábbi igen terjedelmes fogalomlistából válaszd ki azokat, amiket jónak látod, hogy a köv. félévben INFO2-ből a hallgatók heti 45 perc előadás és 45 perc gyakorlat alatt megtanuljanak. Vélhetően az alábbiaknak több, mint a felét ki kell húzni időhiány miatt. De melyik fele maradjon meg? Ha van ötleted, hogy mi maradjon meg, akkor írd a wiki felhasználóneved a megmaradó sorokba, és ne írd a nem megmaradókba.

• algoritmus
  • leállási probléma
• szoftver
  • operációs rendszer
  • alkalmazás
    • interaktív alkalmazás
    • szerver, daemon
    • kötegelt alkalmazás (batch job)
  • firmware (pl. mobiltelefonban, DVD-fevevőben, videókamerában, gépkocsi elektronikájában)
• RAM-gép
  • processzor
  • memória
  • gépi utasítás
  • regiszter
    • utasításszámláló
    • akkumulátor
    • indexregiszter
    • általános célú regiszter
    • flagek
  • feltétel nélküli elágazás
  • feltételes elágazás
• fordító (compiler)
• interpreter
• szintaktikai elemek
  • kulcsszó
  • megjegyzés
  • konstans
    • egész szám
      • decimális (10-es számrendszerbeli)
      • oktális (8-as számrendszerbeli, 0...)
      • hexadecimális (16-os számrendszerbeli, 0xDeadBeaf)
      • méret jelzése (l, L)
      • előjel nélküliség jelzése (u)
    • lebegőpontos szám
      • lebegőpontos szám tudományos jelöléssel (...e...)
      • méret jelzése (f, l, L)
    • karakter
    • string
      • backslash-es escape
        • \n
        • \r
        • \t
        • bájt beszúrása oktálisan: \0123
        • bájt beszúrása hexadeximálisan: \xFa
        • \<soremelés>
        • \"
        • \\
  • azonosító (identifier)
  • operátor
    • prefix operátor
    • postfix operátor
    • infix operátor
      • balra asszociatív infix operátor
      • jobbra asszociatív infix operátor
      • nem asszociatív infix operátor (ilyen C-ben nincs)
    • hármas operátor
      •  ?:
    • lusta kiértékelés
      • &&
      • ||
      •  ?:
    • operátor-precedencia
      • először a postfix operátorok a tapadóval kezdve
      • majd a prefix operátorok a tapadóval kezdve
      • majd az infix és hármas operátorok, precedencia-sorrendben és az asszociativitásuknak megfelelően
      • az asszociativitás csak azonos precedenciájú operátorok között számít
    • 3["nyami"] == "nyami"[3]
• C preprocesszor direktívák
  • lehet szóköz és megjegyzés a # után
  • folytathatók sorvégi \ után
  • makródefiníció
    • #define
      • példa #define isalpha(c) ( ((c)|32U)-'a'<='z'-'a'+0U )
    • #undef
  • feltételes fordítás
    • #if egész-kifejezés
    • #else
    • #elseif (nem szabványos)
    • #endif
    • #ifdef
    • #ifndef
  • más fájlokat betöltő preprocesszor-direktívák
    • #include <...>
    • #include "..."
    • #line n "..."
• egész szám
  • előjel nélküli egész szám (unsigned)
  • előjeles egész szám (signed)
  • kettes komplemens ábrázolás
  • egészszám-típusok C-ben
    • char (>=8 bit)
    • unsigned char
    • short (>=16 bit)
    • unsigned short
    • int (>=16 bit)
    • unsigned int == unsigned
    • long (>=32 bit)
    • unsigned long
    • long long (>= 64 bit, nem szabványos)
    • unsigned long long
  • bitenkénti művelet
    • és (and, &)
    • vagy (or, |)
    • kizáró vagy (xor, ^)
    • nem (not, ~)
    • balra eltolás (shl, <<)
    • jobbra eltolás (shr, >>)
  • sizeof operátor C-ben
  • kerekítés a nulla felé (C-ben)
• logikai érték (bool, boolean)
  • logikai művelet
    • és (and, &&)
    • vagy (or, ||)
    • kizáró vagy (xor)
    • nem (not, !)
    • lusta kiértékelés (&&, ||)
    • feltételes kiértékelés (?:)
• lebegőpontos szám
  • lebegőpontos szám előjele
  • lebegőpontos szám törtrésze (mantissza)
  • lebegőpontos szám kitevője (karakterisztika)
  • normálás
  • lebegőpontos számok összeadása
  • lebegőpontos számok szorzása
  • túlcsordulás (Inf, -Inf)
  • alulcsordulás (+0, -0)
  • eredmény nincs értelmezve (NaN)
  • legebőpontosszám-típusok C-ben
    • float
    • double
    • long double (nem szabványos)
  • kerekítés
    • kerekítés a plusz végtelen felé
    • kerekítés a mínusz végtelen felé
    • kerekítés a nulla felé
    • kerekítés a legközelebbi ábrázolható érték felé
• karakter
  • Unicode-karakter wchar_t
  • 8-bites karakter (char, unsigned char)
• string (karakterlánc)
  • null-terminált string
  • hosszával megadott string
• változó
  • globális változó
  • lokális változó
    • a lokális változó elrejti a globálisat
  • ciklusváltozó
• típuskonverzió
  • automatikus típuskonverzió
  • explicit (kézi) típuskonverzió
• be- és kimenetkezelés C-ben
  • #include <stdio.h>
  • fájlkezelés C-ben
    • FILE*
    • fopen()
    • fclose()
    • stdin
    • stdout
    • stderr
  • kimenet C-ben
    • putchar(), putc()
    • printf(), fprintf()
      • változó argumentumszám
      • formátumstring
        •  %d
        •  %-5.3g
    • sprintf()
    • fwrite()
  • bemenet C-ben
    • getchar(), getc()
    • fgets()
    • scanf(), fscanf()
      • változóértékek helyett mutatókat vár
    • fread()
• gyors stringkezelés C-ben
  • #include <string.h>
  • strlen()
  • strcpy()
  • strcmp()
  • strncmp()
  • memcpy()
  • memcmp()
• néhány matematikai függvény C-ben
  • #include <math.h>
  • gcc -lm
  • M_PI (nem szabványos)
    • helyette 2*atan2(1,0)
  • osztás nullával
    • egész számok esetén
    • lebegőpontos számok esetén
  • sqrt()
  • fabs()
    • == összehasonlítás helyett különbség abszolút értékének figyelése
  • abs()
  • cbrt() (mindig ábrázolható az eredménye)
  • sin()
  • cos()
  • tan()
  • atan2()
  • exp()
  • log()
  • fpclassify() (POSIX szabványos)
  • ceil(), ceill(), ceilf()
  • floor(), floorl(), floorf()
  • trunc(), truncl(), trncf()
  • pow()
• adatszerkezet
  • struktúra (struct, record)
  • tömb (array)
    • indexelés
    • többdimenziós tömb
    • tömb méretének tárolása a tömbön kívűl
    • tömb deklarásása C-ben
    • többdimenziós tömb deklarálása C-ben
    • tömb definiálása C-ben
    • null-terminált karaktertömb definiálása C-ben
    • indexelés 1-től (vagy egyéb, nem 0 kezdőértéktől) C-ben
    • tömb méretének dinamikus növelése
      • realloc()
  • láncolt lista
    • sima, egy irányba láncolt lista
      • NULL
      • lekódolni: minimális elem megkeresése egy láncolt listában
      • lekódolni: minimális elem megkeresése egy rendezett láncolt listában
    • kétirányba körbeláncolt lista
  • verem (LIFO)
    • futási verem (runtime stack)
    • verem megvalósítása tömmbel
    • verem megvalósítása sima, egy irányba láncolt listával
  • várakozási sor (queue, FIFO)
    • várakozási sor megvalósítása kétirányba körbeláncolt listával
  • prioritásos várakozási sor
    • kupac (heap)
      • prioritásos várakozási sor megvalósítása kupaccal
      • kupacrendezés
      • eratoszthenészi szita kupaccal
  • gráf
    • incidencia mátrix
    • adjacencia (szomszédossági) mátrix
    • komponensek számának meghatározása mélységi bejárással
    • legrövidebb út keresése
      • szélességi bejárás
      • Dijkstra algoritmusa
  • asszociatív tömb
    • asszociatív tömb megvalósítása struktúrák körbeláncolt listájával
    • asszociatív tömb megvalósítása keresőfákkal
    • asszociatív tömb megvalósítása hasheléssel
• rendezett tömb
  • bináris keresés rendezett tömbben
    • lekódolni: eldönteni, hogy egy érték eleme-e egy rendezett listának
    • miért nem alkalmazható láncolt lista esetén?
  • stabil rendezés
  • tömb stabil rendezése összefésülő rendezéssel
  • azonos elemek keresése
  • tömbben előforduló különböző értékek megszámolása
• egyszerű számelméleti algoritmusok
  • euklideszi algoritmus legnagyobb közös osztó megkeresésére
    • törtszám egyszerűsítése
    • racionális (tört)számok összeadása
  • átváltás számrendszerek közt leosztogatással
  • moduláris hatványozás négyzetre emeléssel és szorzással
  • prímség ellenőrzése négyzetgyökig próbálgatással
  • prímfelbontás kiírása próbálgatással
  • eratoszthenészi szita
  • négyzetgyökvonás bináris kereséssel
  • négyzetgyökvonás Newton-iterációval
• rekurzió
  • kettőhatványok számolása
  • Fibonacci-számok számolása
  • rekurzió gyorsítása tabellázással
    • binomiális együtthatók rekurzív számolása
    • leghosszabb közös részsorozat (részstring) keresése
    • nyerő stratégia keresése a ,,csak a széléről vehetsz el játékhoz
  • összefésülő rendezés (szerepel máshol is)
• ciklus
  • ciklusváltozó
  • a ciklusutasítás részei
    • kezdeti értékadás
    • továbbmenési feltétel
    • leállási feltétel
    • továbblépési utasítás
    • ciklusmag
    • azonnali kilépés (break)
    • folytatás a következő iterációval (continue)
  • elöltesztelős ciklus
    • while
    • for
  • hátultesztelős ciklus
    • do ... while
  • végtelen ciklus
    • bizonyítás keresése program leállására
      • előrehaladást jelző, csökkenő természetes szám értékű változó keresése
    • a leállási probléma
  • példák ciklusra
    • négyzetszámok kiírása szorzással
    • négyzetszámok kiírása összeadással
    • a gép gondol egy egész számot, a játékos tippelhet
    • a játékos gondol egy egész számot, a gép tippelhet
    • string helyben megfordítása
    • fájlnév kiterjesztésének keresése
    • fájlnév elérési útjának keresése
    • két rendezett lista összefésülése
    • bemenet karaktereinek megszámolása
      • a wc program
• algoritmusok leírása
  • követelményspecifikáció, interfész
    • algoritmus neve
    • bemeneti adatok és típusaik
    • kimeneti változók és típusaik
    • hívás előtt teljesülő feltétel (precondition)
    • hívás után teljesülő feltétel (postcondition)
    • pontos megadása annak, hogy mit csinál (az nem, hogy hogyan)
    • hibalehetőségek listája
    • hibajelzési mód specifikálása
    • letöltéséhez, lefordításához és futtatásához szükséges információk
  • a használt adatszerkezetek leírása
  • a működés leírásának módjai
    • informális leírás (receptszerűen, folyamatos szövegben)
    • precíz formális leírás
      • folyamatábra (flow chart)
        • az elvégzendű műveletek leírása
        • a műveleti sorrend kijelölése
        • UML aktivitás-diagram (activity diagram)
      • stuktogramm (stuki)
      • leírás egyéb matematikai formalizmussal
      • leírás informatikai formalizmussal
      • a forráskód megadása
    • a működés megértését segítő leírás
      • segédábra, szemléltető ábra
      • UML-diagramok
      • szimuláció
• mutató
  • mutatók összehasonlítása
  • mutató növelése és csökkentése
    • az 1-gyel növelés hatása a mutatóra
    • preinkrementálás (++p)
    • posztinkrementálás (p++)
  • void*
  • NULL
• memóriakezelési hibák
  • túl korai felszabadítás
  • túl késői felszabadítás
  • elmaradt felszabadítás (memory leak)
  • többszörs felszabadítás
  • túl rövid terület foglalása
    • puffertúlcsordulás (buffer overflow)
    • puffertúlcsordulásos támadás
  • érvénytelen területre (pl. NULL-ra) való hivatkozás
  • iniciálizálatlan érték felhasználása
  • memóriakezelési hibajelenségek
    • nehezen reprodukálható hibák
    • a program értelmetlenül viselkedik
    • a program értelmetlen kimenetet produkál
    • Segmentation fault
• függvény (function) == szubrutin
  • argumentum == paraméter
  • argumentum típusa
  • visszatérési érték
  • visszatérési érték típusa
  • függvénytörzs
  • paraméterátadás fajtái
    • érték szerinti paraméterátadás
    • név szerinit paraméterátadás == cím szerinti paraméterátadás
      • megvalósítása mutatókkal C-ben
  • return mögötte kifejezéssel
  • a függvénytörzs végén kötelező return (kivéve eljárás esetén)
  • eljárás (procedure)
    • void visszatérési érték
    • return üresen
  • két szomszédos tömbrész megcserélése helybeni megfordítással
    • void visszatérési típus
  • több érték visszadása
    • struktúra visszadása
    • visszadás cím szerinti paraméterátadással
  • változó argumentumszámú függvények
    • #include <stdarg.h>
    • va_list
    • va_start
    • va_arg
    • va_end
  • függvénymutató
    • számok rendezése a qsort() függvénnyel
    • kis- és nagybetűket figyelmen kívül hagyó rendezés a qsort() függvénnyel
  • egymásba ágyazott függvényt C-ben nem lehet
• deklarált függvény, típus, változó honnan érhető el (storage class)
  • static
  • módosító nélküli
  • extern (opcionális)
  • (auto)
  • (register)
• deklaráció
  • többszörös deklaráció
  • előre deklaráció (forward declaration)
• definíció C-ben
  • típusdefiníció
    • typedef
  • függvénydefiníció
  • változódefiníció kezdeti értékkel (inicializálással)
• utasításblokk
  • lokális változó
• feltétel nélküli vezérlésátadás
  • goto
  • goto kiküszöbölési lehetőségei
    • új, kis függvények
    • while, break, continue
• feltételes elágazás
  • if
  • else
  • újabb if az else ágban
  • switch
  • case
• típusdefiníció C-ben
  • egyszerű típuskifejezések
    • pl. char(* )(int*[],unsigned short(*)[42])
  • egyszerű változódeklaráció
    • pl. char(*f)(int*[],unsigned short(*)[42]);
  • typedef
  • struct
    • változódeklarációval kombinálva
    • typedef-fel kombinálva
    • __attribute__ ((packed)) nélkül extra helyet hagyhat ki, pl. struct { char a; long b; }
  • enum
  • union
• fejlécfájl (header, .h)
  • #include
  • szabványos C fejlécfájlok
    • ctype.h
    • (setjmp.h)
    • math.h
    • string.h
    • stdio.h
    • stdlib.h
    • time.h
• hibakeresési módszerek
  • szigorúbb fordítási mód használata
    • gcc -ansi -pedantic
  • szigorúbb fordítási figyelmeztetések kérése
    • gcc -W -Wall -Wunused
    • gcc -Wstrict-prototypes -Wmissing-prototypes -Wmissing-declarations
  • okos szövegszerkesztő használata
    • szintaxis-színezés (syntax highlighting)
    • zárójel párjának mutatása (show matching brace)
    • azonosítók automatikus kiegészítése
  • kiíró utasítások beillesztése
    • kiíró utasítások feltételessé tétele
  • memóriakezelés ellenőrzése
    • valgrind
  • nyomkövetés (debug)
    • utasításléptetés (step)
    • töréspont (breakpoint)
    • változófigyelés (watch)
  • meghívott rendszerhívások mutatása
    • strace
• szkriptnyelv
• memóriakezelés
  • fix memóriaterület használata (pl. TeX)
  • dinamikus memóriakezelés: memóriaterület kérése az operációs rendszertől
    • kézi memóriafoglalás és -felszabadítás
      • malloc()
      • free()
      • realloc()
      • calloc()
    • kézi memóriafoglalás, automatikus memóriafelszabadítás
      • hivatkozásszámlálás (reference counting)
        • körkörös hivatkozások
      • szemétgyűjtés
        • megjelöl és kiseper (mark and sweep) szemétgyűjtű
        • többgenerációs (generational) szemétgyűjtő
        • másoló szemétgyűjtő
• parnacssori argumentumok és a környezet kezelése C-ben
  • argc
  • argv
  • #include <stdlib.h>
  • environ
  • getenv()
  • putenv()
• Ruby változóérvényesség-fajták (scope)
  • Ruby globális változó
  • Ruby lokális változó
  • tagváltozó (példányváltozó, attribútum)
  • osztályváltozó (statikus változó)
  • Ruby konstans
• modul
  • egymásba ágyazott modulok
• objektum-orientált programozás
  • objektum
  • osztály
  • metódus (tagfüggvény)
    • nem virtuális metódus
    • virtuális metódus
      • virtuállismetódus-tábla
    • absztrakt metódus
  • konstruktor
  • destruktor
    • miért nincs Rubyban destruktor
  • osztálymetódus
  • öröklődés
    • egyszeres öröklődés
    • többszörös öröklődés
    • super
    • a konstruktor nem öröklődhet
      • szülő osztály konstuktorának hívása
  • interfész
    • interfész többszörös öröklése
  • absztrakt osztály
  • egységbe zárás (encapsulation)
  • információrejtés
    • public
    • protected
    • private
    • friend
  • polimorfizmus
    • virtuálismetódus-hívás
    • függvény többszörös definiálása (function overloading)
    • operátor többszörös definiálása (operator overloading)
  • kompozíció
    • bővíthető programkód
    • újrafelhasználható programkód
• iterálás
  • iterátor
  • blokk
  • blokkparaméterek
  • yield
• reguláris kifejezés (regular expression, regexp)
  • illesztés reguláris kifejezésre (regexp match)
  • végignézés reguláris kifejezéssel (regexp scan)
  • csere reguláris kifejezéssel (regexp substitution)
  • darabolás reguláris kifejezéssel (regexp split)
• példa: racionális számok osztálya
• példa: vektorok és mátrixok osztálya
  • mátrixszorzás
• kivételkezelés
  • kivétel
  • raise
  • begin ... rescue ... end
  • begin ... ensure ... end
  • Exception#backtrace
  • a kivételkezelés memóriafelszabadítási problémája C++-ban
• kötés ideje
  • korai kötés
  • késői kötés
• típusosság foka
  • statikus, méret ismert
  • dinamikus: a változóba bármit bele lehet tölteni (a Ruby ilyen)
  • automatikus: dinamikus, és bármi bármivé konvertálódik (a Ruby nem ilyen)
• típusellenőrzés ideje
  • fordításkor
  • értékadáskor
  • az érték felhasználásakor

TODO:

• Ruby beépített osztályok, p()
• Ruby hatékony programozás
• standard C reference kétoldalas PDF fekete-fehér nyomtatása, kiosztása
• hangadók
• előadás célcsoportja
• ne üljenek bambán feladatmegoldáskor

Rácz Balázs ötletei:

• cout-ot jobb tanítani, mint a printf-et
• C++ programban hibakeresés legyen
• vector<int> -et tudják használni, ami biztonságosabb, mint a malloc()

pts öteletei:

• ne tanítsuk meg azt, ami később Algoritmuselméletből tananyag lesz
• Cékla házi feladatok kiírása (jól gyakorlható velük a rekurzió)
• ZH-n lehessen használni a standard C reference-t
• ZH-ra összeállíthassanak maguknak egy Ruby-puskát. Aki olyan puskát

tesz fel a wikibe, ami alapján 5-ösre meg lehet írni a Ruby ZH-t, az 5-öst kap a Ruby ZH-jára (be se kell jönnie megírni)

Ötlet: első ZH C-ből, második ZH Ruby-ből