VIK Wiki - Felhasználó közreműködései [hu]

Operációs rendszerek

2014-06-11T18:15:59Z

Ewsd: /* Egyéb segédanyagok */

{{Tantárgy
|nev=Operációs rendszerek
|targykod=VIMIA219
|szak=info
|kredit=4
|felev=4
|kereszt=vizsgakurzus
|tanszék=MIT
|kiszh=nincs
|hf=nincs
|nagyzh=1 db
|vizsga= írásbeli
|szak=info
|tad=https://www.vik.bme.hu/kepzes/targyak/vimia219
|targyhonlap=http://www.mit.bme.hu/oktatas/targyak/vimia219
}}

[[TargynevAjanlas|Ajánlott rövidítés]]: opre

==Követelmények==

=== Előtanulmányi rend ===
[[Számítógép architektúrák]] tárgyból aláírás megszerzése szükséges a tárgy felvételéhez.

=== A szorgalmi időszakban ===
*Az '''aláírás''' megszerzésének feltétele:
**A '''ZH''' sikeres (min 40%) megírása.
*'''Megajánlott jegy:''' nincs.
*'''Pótlási lehetőségek:'''
**A ZH egyszer félév közben, egyszer pedig a pótlási héten (különeljárási díj fejében) pótolható.
*'''Elővizsga:''' nincs.

===A vizsgaidőszakban===
*'''Vizsga:''' írásbeli. Két részből áll, amelyek 12 és 50 pontosak. az elégséges vizsgához az első (beugró) rész min. 7 pontos (~58%), a második rész min. 20 pontos (40%) teljesítése szükséges. A beugró teljesítése a vizsga folytatásának feltétele. (Mivel nem tudják ott azonnal kijavítani, így a vizsga folytatható, csak a beugró nem teljesülése esetén a vizsga második részét nem javítják ki.) A beugró pontszáma nem számít bele a félévvégi jegybe.
**Előfeltétele: az aláírás megléte.
**A beugró ponthatárai:
::{| class="wikitable" align="left"
|-
! Pont !!
|-
|0 - 5 || nincs meg, és messze a ponthatár (esélytelen sajnos)
|-
|5,5 - 6,5 || nincs meg, de közel a ponthatár (lehet reklamálni, talán elszámolták)
|-
|7 - 12 || rendben
|}

===Félévvégi jegy===
*A jegyet adó pontszámot (P) az aktuális félévben aláírást szerzőknél a ZH és a vizsga második felének (V2) pontszáma adja a következő módon:
*<math>P= 0,3*ZH+0,7*V_2</math>
*Aki korábban szerzett aláírást, annál P= V2.
*''A vizsga első felének (a beugrónak) a pontszáma a végső jegybe nem számít bele, csak a vizsga folytatásának feltétele!''
*Ponthatárok:
:{| class="wikitable" align="center"
|-
! P !! Jegy
|-
|0 - 19 || 1
|-
|20 - 25 || 2
|-
|26 - 31 || 3
|-
|32 - 39 || 4
|-
|40 - 50 || 5
|}

== Segédanyagok ==
=== Könyv ===
* Kóczy A., Kondorosi K. (szerkesztők): Operációs rendszerek mérnöki megközelítésben, Panem Kiadó, Budapest, 2000.
** a tárgy általános részét részben lefedi a könyv 17. és 211.. oldalak közti része
* Silberschatz, Peterson: Operating System Concepts vagy Operating Systems Concept with JAVA (7. vagy későbbi kiadás)
''A tárgy tematikája folyamatosan változik, így mára elég elavultak a segédanyagok. A magyar nyelvű könyvvel is ez a helyzet, régi kiadású, elavult, de még az általános részeket jól leírja. Érdemes az angol nyelvű könyveket beszerezni, mivel ezek évek óta frissülnek, így közelebb állnak az anyaghoz.''

=== Opre nemhivatalos jegyzet ===
Legfrissebb változat: [[Media:OPRE_jegyzet.pdf|OpreJegyzet]]
* NEM HIVATALOS JEGYZET: nincs benne minden, vannak benne hibák/elírások
* 2011-es anyagot tartalmazza
* utolsó szerkesztés dátuma: 2011 nyár
* Továbbfejlesztési lehetőségek:
** Minden évben szükséges lenne frissíteni az aktuális anyagokkal és kiegészíteni, újabb "kiadásban" feltölteni!
** [[Szerkesztő:Ferrero| a készítő elérhetősége]], vele egyeztetve lehet elkérni a forrást és továbbfejlesztésről érdeklődni (mely mindenki számára nyitott, csak pár tanácsot adna)

=== Diák ===
{| style="border-spacing: 1em;"
| style="vertical-align: top;" |
; 1. [[Media:opre_1_intro.pdf|Bevezető előadás]]
; 2. [[Media:opre_2_unix_bevezetes.pdf|UNIX bevezető előadás]]
; 3. [[Media:opre_3_windows_intro.pdf|Windows bevezető előadás]]
; 4. [[Media:opre_4_windows_troubleshooting.pdf|Windows hibakeresés]]
; 5. [[Media:opre_5_windows_utemezes.pdf|Windows ütemezés]]
; 6. [[Media:opre_6_kommunikacio_ellenorzese.pdf|Feladatok közötti kommunikáció ellenőrzése]]
; 7. [[Media:opre_7_scheduling.pdf|Ütemezés]]
; 8. [[Media:opre_8_scheduling2.pdf|Összetett prioritásos és többprocesszoros ütemezés]]
| style="vertical-align: top;" |
; 9. [[Media:opre_9_taskimplementation.pdf|Feladatok implementációja, folyamatok és szálak]]
; 10. [[Media:opre_10_mutex.pdf|Kölcsönös kizárás, szinkronizáció, kommunikáció]]
; 11. [[Media:opre_11_ipc.pdf|Üzenet alapú kommunikáció]]
; 12. [[Media:opre_12_deadlock.pdf|Holtpont és kezelése]]
; 13. [[Media:opre_13_folyamatkezeles.pdf|UNIX folyamatkezelés]]
; 14. [[Media:opre_14_utemezes.pdf|UNIX ütemezés]]
; 15. [[Media:opre_15_kommunikacio.pdf|UNIX kommunikáció]]
; 16. [[Media:opre_16_memory.pdf|Memóriakezelés]]
| style="vertical-align: top;" |
; 17. [[Media:opre_17_ucos.pdf|uC/OS]]
; 18. [[Media:opre_18_windows_memoria.pdf|Windows memóriakezelés]]
; 19. [[Media:opre_19_virtualizacio.pdf|Virtualizáció]]
; 20. [[Media:opre_20_dtrace.pdf|UNIX Dtrace]]
; 21. [[Media:opre_21_files.pdf|A permanens tár kezelése]]
; 22. [[Media:opre_22_unix_fajlrendszerek.pdf|UNIX fájlrendszerek]]
; 23. [[Media:opre_23_hitelesites_engedelyezes.pdf|Hitelesítés és engedélyezés]]
; 24. [[Media:opre_24_windows_biztonsag.pdf|Windows biztonság]]
|}

=== Egyéb segédanyagok ===
* [[Media:opre_mindmap_altalanos.png|Opre általános MindMap]], nem hivatalos [[Media:opre_mindmap_kidolgozas.pdf|kidolgozása]]
* [[Media:opre_mindmap_windows.png|Opre Windows MindMap]]
* [[Media:opre_feladatok_segedanyag.pdf|Számolási példák és algoritmusok]]
* [[Media:opre_raidosszefoglalas_20140610.pdf|RAID összefoglaló a diasor alapján]]
* [[Media:Opre_Vizgya_Jegyztet_2014_tavasz.pdf|2014 tavaszi félév előadásdiáinak tömör jegyzete (41.o)]]

=== Videó ===
2011. őszén az EHK felvette a tárgy előadásait. [http://bme.videotorium.hu/hu/channels/details/900,Operacios_rendszerek A videók innen letőlthetöek]

== ZH ==
2011-ben a ZH szerkezete megváltozott kicsit:
* 10 kiskérdés ''(vizsga beugró jellegű)''
* 20 pontos teszt ''(korábbi ZH és vizsga teszt)''
* 2 nagy feladat, feladatonként 10 pontért ''(összesen 20 pont)''

A ZH 50 pontos, 20 ponttól van meg. A szerzett pontokat az aláírást szerzőknél 30%-ban veszik figyelembe a végső vizsgajegy megállapításában (hogy megérje jól felkészülni a ZH-ra is).

==== Számolós példára lehetőségek ====
* Alap ütemezési algoritmusok: ''(FIFO, RR, SJF, SRTF ütemezéssel kapcsolatos mértékek számolása, lásd: Harmadik hét diasora )''
* Klasszikus UNIX ütemezés: ''(lásd: könyv)''
* Holtpont bankár algoritmus: ''(lásd: Ötödik hét diasora)''
* Memória foglalás: ''(lásd: Hatodik hét diasora)''
* Lapcsere algoritmusok: ''(lásd: Hatodik hét diasora) 2011-ben nem kell''

==== Zárthelyi feladatsorok ====
* [[Media:opre_2010_mintazh.pdf|2010-es MintaZH]], [[Media:opre_2010_mintazh_megoldas.pdf|megoldása]]
* [[Media:opre_2011_mintazh.pdf|2011-es MintaZH]]
* [[Media:opre_20100426_ZH_megoldas.pdf|2010.04.26. ZH megoldással]]
* [[Media:opre_20100507_ZH_megoldas.pdf|2010.05.07. ZH megoldással]]
* [[Media:opre_20100520_ZH_megoldas.pdf|2010.05.20. ZH megoldással]]

==Vizsga==
A tárgyból írásbeli vizsga van, ami két részből áll. Beugró és nagyfeladat. A beugrót csak a nagyfeladat megírása után javítják ki. Aki a beugró alapján reménytelennek tartja a helyzetét, a beugró után elmehet. Eredmények a tárgyhonlapra kerülnek fel, ott olvashattok a megtekintések időpontjáról is.

=== Beugró ===
* A 12 elméleti kérdésböl 7-et kell megválaszolni (60%), 15 perc van rá.
* Elméleti kérdéseket tartalmaz, tehát a beugró teljesítéséhez tudni kell az anyagot részletesen.

==== Beugró kidolgozások ====
* [[OpReVizsgaBeugrokMegoldassal|Vizsgabeugrók és azok megoldásai ÖSSZEGYŰJTVE, ABC-rendbe szedve, egy helyen]] (javítsátok, egészítsétek ki! :) ) -- [[PeteHaro|Pete]] - 2011.06.19.
* [[OpReVizsgaKisKerdesek|Kidolgozott beugró kérdések]] - nem hibátlan, aki hibát talál benne javítsa

==== Beugró feladatsorok ====
* [[Media:opre_vizsga_beugro_20110606.pdf|2011.06.06. beugró]]
* [[Media:opre_vizsga_beugro_20110523.pdf|2011.05.23. beugró]]
* [[Media:opre_vizsga_beugro_20110117.pdf|2011.01.17. beugró]]
* [[Media:opre_vizsga_beugro_20110111.pdf|2011.01.10. beugró]]
* [[Media:opre_vizsga_beugro_20101220.pdf|2010.12.20. beugró]]
* [[Media:opre_vizsga_beugro_20100615.pdf|2010.06.15. beugró]]
* [[Media:opre_vizsga_beugro_20100608.pdf|2010.06.08. beugró]]
* [[Media:opre_vizsga_beugro_20100601.pdf|2010.06.01. beugró]]
* [[Media:opre_vizsga_beugro_pelda.pdf|2010-es minta beugró]], [[Media:opre_vizsga_beugro_pelda_megoldas.pdf|megoldása]]

==== Igaz-hamis ====
[[Operációs rendszerek - Igaz-hamis vizsgakérdések|Igaz-hamis kikérdező]]

=== Nagyfeladatlap ===
* A beugrót követi a nagyfeladatlap kitöltése. A nagyfeladatlap 30 tesztkérdést (8 kérdéscsoport), és 2 nagyfeladaot tartalmaz. A vizsgában nagyobb arányban szerepelnek benne Windows, UNIX/Linux, virtualizáció, biztonság, stb. kérdések a ZH-hoz képest.
==== Nagyfeladatlap feladatsorok és kidolgozások ====
* [[Media:opre_vizsga_20100615_megoldas.pdf|2010.06.15. vizsga nagyfeladata hivatalos megoldással]]
* [[Media:opre_vizsga_20100608_megoldas.pdf|2010.06.08. vizsga nagyfeladata hivatalos megoldással]]
* [[Media:opre_vizsga_20100601_megoldas.pdf|2010.06.01. vizsga nagyfeladata hivatalos megoldással]]
* [[Media:opre_vizsga_20100125.jpg|2010.01.25. vizsga nagyfeladata]]
* [[OpReVizsga20100118PrioritasInverzio|2010.01.18. vizsga nagyfeladatai nem hivatalos megoldás]]
* [[Media:opre_vizsga_20100106.jpg|2010.01.06. vizsga nagyfeladata]]
* [[OpReVizsga20090615|2009.06.15. vizsga nagyfeladatai]]
* [[OpReVizsga20090608|2009.06.08. vizsga nagyfeladatai]]
* [[Media:opre_vizsga_20090122.jpg|2009.01.22. vizsga nagyfeladata]]
* [[Media:opre_vizsga_20090112.pdf|2009.01.12. vizsga nagyfeladata]]
* [[Media:opre_vizsga_20081222.jpg|2008.12.22. vizsga nagyfeladata]]
* [[Media:opre_vizsga_20081215.jpg|2008.12.15. vizsga nagyfeladata]]
* [[OpReVizsga2008junius19|2008.06.19. vizsga nagyfeladatai]]
* [[OpReVizsga2008junius11megoldas|2008.06.11. vizsga nagyfeladatai és beugró nem hivatalos megoldással]]
* [[OpReVizsga2008majus20megoldas|2008.05.01. vizsga nagyfeladatai és beugró nem hivatalos megoldással]] '''(hiányzik: beugró 3 nagykérdések 2)'''
* [[OpReVizsga2007junius12megoldas|2007.06.12. vizsga nagyfeladatai és beugró nem hivatalos megoldással]] '''(hiányzik: nagykérdések 1, 2, 3)'''

== Kedvcsináló ==
[[OpReKedvcsinalo|Kedvcsináló]]

==Egyéb anyagok/linkek==
===Észrevételek===
Több probléma is akad a tárgy wiki adatlapjával ill. a felkészüléssel kapcsolatban:
* Hiányos, hibás kidolgozások. Arról van szó, hogy hibás/téves információkat tanulunk meg belőlük.
* Magolás, beugrókérdések betanulása. Amikor nem az anyagrész megértése, hanem a "beseggelése" történik. Vizsgán gyakran szokott olyan történni, hogy felteszik a kérdés ellenkezőjét, vagy kicsit változtatnak rajta. Az a tapasztalat, hogy az emberek ilyenkor is a standard (wikis bemagolt) választ adják vissza, ami természetesen nem jó.
* A wikin található tartalomért, az esetlegesen hiányzó anyagrészekért és az előforduló hibákért nem vállalunk felelősséget. Konzultáltunk az oktatókkal: szerintük minden előadáson elhangzott anyag szerepel, a jelenlegi állapot már alkalmas lehet egy sikeres zh/vizsga felkészüléshez. Ha hibát / hiányosságot találtál az oldalon található anyagokban, vagy esetleg téves információt közöltünk, kérlek írj a tárgy levelezési listájára, vagy a vitalapra.

{{Lábléc_-_Mérnök_informatikus_alapszak}}

Operációs rendszerek

2014-06-11T18:14:17Z

Ewsd: /* Egyéb segédanyagok */

{{Tantárgy
|nev=Operációs rendszerek
|targykod=VIMIA219
|szak=info
|kredit=4
|felev=4
|kereszt=vizsgakurzus
|tanszék=MIT
|kiszh=nincs
|hf=nincs
|nagyzh=1 db
|vizsga= írásbeli
|szak=info
|tad=https://www.vik.bme.hu/kepzes/targyak/vimia219
|targyhonlap=http://www.mit.bme.hu/oktatas/targyak/vimia219
}}

[[TargynevAjanlas|Ajánlott rövidítés]]: opre

==Követelmények==

=== Előtanulmányi rend ===
[[Számítógép architektúrák]] tárgyból aláírás megszerzése szükséges a tárgy felvételéhez.

=== A szorgalmi időszakban ===
*Az '''aláírás''' megszerzésének feltétele:
**A '''ZH''' sikeres (min 40%) megírása.
*'''Megajánlott jegy:''' nincs.
*'''Pótlási lehetőségek:'''
**A ZH egyszer félév közben, egyszer pedig a pótlási héten (különeljárási díj fejében) pótolható.
*'''Elővizsga:''' nincs.

===A vizsgaidőszakban===
*'''Vizsga:''' írásbeli. Két részből áll, amelyek 12 és 50 pontosak. az elégséges vizsgához az első (beugró) rész min. 7 pontos (~58%), a második rész min. 20 pontos (40%) teljesítése szükséges. A beugró teljesítése a vizsga folytatásának feltétele. (Mivel nem tudják ott azonnal kijavítani, így a vizsga folytatható, csak a beugró nem teljesülése esetén a vizsga második részét nem javítják ki.) A beugró pontszáma nem számít bele a félévvégi jegybe.
**Előfeltétele: az aláírás megléte.
**A beugró ponthatárai:
::{| class="wikitable" align="left"
|-
! Pont !!
|-
|0 - 5 || nincs meg, és messze a ponthatár (esélytelen sajnos)
|-
|5,5 - 6,5 || nincs meg, de közel a ponthatár (lehet reklamálni, talán elszámolták)
|-
|7 - 12 || rendben
|}

===Félévvégi jegy===
*A jegyet adó pontszámot (P) az aktuális félévben aláírást szerzőknél a ZH és a vizsga második felének (V2) pontszáma adja a következő módon:
*<math>P= 0,3*ZH+0,7*V_2</math>
*Aki korábban szerzett aláírást, annál P= V2.
*''A vizsga első felének (a beugrónak) a pontszáma a végső jegybe nem számít bele, csak a vizsga folytatásának feltétele!''
*Ponthatárok:
:{| class="wikitable" align="center"
|-
! P !! Jegy
|-
|0 - 19 || 1
|-
|20 - 25 || 2
|-
|26 - 31 || 3
|-
|32 - 39 || 4
|-
|40 - 50 || 5
|}

== Segédanyagok ==
=== Könyv ===
* Kóczy A., Kondorosi K. (szerkesztők): Operációs rendszerek mérnöki megközelítésben, Panem Kiadó, Budapest, 2000.
** a tárgy általános részét részben lefedi a könyv 17. és 211.. oldalak közti része
* Silberschatz, Peterson: Operating System Concepts vagy Operating Systems Concept with JAVA (7. vagy későbbi kiadás)
''A tárgy tematikája folyamatosan változik, így mára elég elavultak a segédanyagok. A magyar nyelvű könyvvel is ez a helyzet, régi kiadású, elavult, de még az általános részeket jól leírja. Érdemes az angol nyelvű könyveket beszerezni, mivel ezek évek óta frissülnek, így közelebb állnak az anyaghoz.''

=== Opre nemhivatalos jegyzet ===
Legfrissebb változat: [[Media:OPRE_jegyzet.pdf|OpreJegyzet]]
* NEM HIVATALOS JEGYZET: nincs benne minden, vannak benne hibák/elírások
* 2011-es anyagot tartalmazza
* utolsó szerkesztés dátuma: 2011 nyár
* Továbbfejlesztési lehetőségek:
** Minden évben szükséges lenne frissíteni az aktuális anyagokkal és kiegészíteni, újabb "kiadásban" feltölteni!
** [[Szerkesztő:Ferrero| a készítő elérhetősége]], vele egyeztetve lehet elkérni a forrást és továbbfejlesztésről érdeklődni (mely mindenki számára nyitott, csak pár tanácsot adna)

=== Diák ===
{| style="border-spacing: 1em;"
| style="vertical-align: top;" |
; 1. [[Media:opre_1_intro.pdf|Bevezető előadás]]
; 2. [[Media:opre_2_unix_bevezetes.pdf|UNIX bevezető előadás]]
; 3. [[Media:opre_3_windows_intro.pdf|Windows bevezető előadás]]
; 4. [[Media:opre_4_windows_troubleshooting.pdf|Windows hibakeresés]]
; 5. [[Media:opre_5_windows_utemezes.pdf|Windows ütemezés]]
; 6. [[Media:opre_6_kommunikacio_ellenorzese.pdf|Feladatok közötti kommunikáció ellenőrzése]]
; 7. [[Media:opre_7_scheduling.pdf|Ütemezés]]
; 8. [[Media:opre_8_scheduling2.pdf|Összetett prioritásos és többprocesszoros ütemezés]]
| style="vertical-align: top;" |
; 9. [[Media:opre_9_taskimplementation.pdf|Feladatok implementációja, folyamatok és szálak]]
; 10. [[Media:opre_10_mutex.pdf|Kölcsönös kizárás, szinkronizáció, kommunikáció]]
; 11. [[Media:opre_11_ipc.pdf|Üzenet alapú kommunikáció]]
; 12. [[Media:opre_12_deadlock.pdf|Holtpont és kezelése]]
; 13. [[Media:opre_13_folyamatkezeles.pdf|UNIX folyamatkezelés]]
; 14. [[Media:opre_14_utemezes.pdf|UNIX ütemezés]]
; 15. [[Media:opre_15_kommunikacio.pdf|UNIX kommunikáció]]
; 16. [[Media:opre_16_memory.pdf|Memóriakezelés]]
| style="vertical-align: top;" |
; 17. [[Media:opre_17_ucos.pdf|uC/OS]]
; 18. [[Media:opre_18_windows_memoria.pdf|Windows memóriakezelés]]
; 19. [[Media:opre_19_virtualizacio.pdf|Virtualizáció]]
; 20. [[Media:opre_20_dtrace.pdf|UNIX Dtrace]]
; 21. [[Media:opre_21_files.pdf|A permanens tár kezelése]]
; 22. [[Media:opre_22_unix_fajlrendszerek.pdf|UNIX fájlrendszerek]]
; 23. [[Media:opre_23_hitelesites_engedelyezes.pdf|Hitelesítés és engedélyezés]]
; 24. [[Media:opre_24_windows_biztonsag.pdf|Windows biztonság]]
|}

=== Egyéb segédanyagok ===
* [[Media:opre_mindmap_altalanos.png|Opre általános MindMap]], nem hivatalos [[Media:opre_mindmap_kidolgozas.pdf|kidolgozása]]
* [[Media:opre_mindmap_windows.png|Opre Windows MindMap]]
* [[Media:opre_feladatok_segedanyag.pdf|Számolási példák és algoritmusok]]
* [[Media:opre_raidosszefoglalas_20140610.pdf|RAID összefoglaló a diasor alapján]]
* [[Opre_Vizgya_Jegyztet_2014_tavasz.pdf|2014 tavaszi félév előadásdiáinak tömör jegyzete (41.o)]]

=== Videó ===
2011. őszén az EHK felvette a tárgy előadásait. [http://bme.videotorium.hu/hu/channels/details/900,Operacios_rendszerek A videók innen letőlthetöek]

== ZH ==
2011-ben a ZH szerkezete megváltozott kicsit:
* 10 kiskérdés ''(vizsga beugró jellegű)''
* 20 pontos teszt ''(korábbi ZH és vizsga teszt)''
* 2 nagy feladat, feladatonként 10 pontért ''(összesen 20 pont)''

A ZH 50 pontos, 20 ponttól van meg. A szerzett pontokat az aláírást szerzőknél 30%-ban veszik figyelembe a végső vizsgajegy megállapításában (hogy megérje jól felkészülni a ZH-ra is).

==== Számolós példára lehetőségek ====
* Alap ütemezési algoritmusok: ''(FIFO, RR, SJF, SRTF ütemezéssel kapcsolatos mértékek számolása, lásd: Harmadik hét diasora )''
* Klasszikus UNIX ütemezés: ''(lásd: könyv)''
* Holtpont bankár algoritmus: ''(lásd: Ötödik hét diasora)''
* Memória foglalás: ''(lásd: Hatodik hét diasora)''
* Lapcsere algoritmusok: ''(lásd: Hatodik hét diasora) 2011-ben nem kell''

==== Zárthelyi feladatsorok ====
* [[Media:opre_2010_mintazh.pdf|2010-es MintaZH]], [[Media:opre_2010_mintazh_megoldas.pdf|megoldása]]
* [[Media:opre_2011_mintazh.pdf|2011-es MintaZH]]
* [[Media:opre_20100426_ZH_megoldas.pdf|2010.04.26. ZH megoldással]]
* [[Media:opre_20100507_ZH_megoldas.pdf|2010.05.07. ZH megoldással]]
* [[Media:opre_20100520_ZH_megoldas.pdf|2010.05.20. ZH megoldással]]

==Vizsga==
A tárgyból írásbeli vizsga van, ami két részből áll. Beugró és nagyfeladat. A beugrót csak a nagyfeladat megírása után javítják ki. Aki a beugró alapján reménytelennek tartja a helyzetét, a beugró után elmehet. Eredmények a tárgyhonlapra kerülnek fel, ott olvashattok a megtekintések időpontjáról is.

=== Beugró ===
* A 12 elméleti kérdésböl 7-et kell megválaszolni (60%), 15 perc van rá.
* Elméleti kérdéseket tartalmaz, tehát a beugró teljesítéséhez tudni kell az anyagot részletesen.

==== Beugró kidolgozások ====
* [[OpReVizsgaBeugrokMegoldassal|Vizsgabeugrók és azok megoldásai ÖSSZEGYŰJTVE, ABC-rendbe szedve, egy helyen]] (javítsátok, egészítsétek ki! :) ) -- [[PeteHaro|Pete]] - 2011.06.19.
* [[OpReVizsgaKisKerdesek|Kidolgozott beugró kérdések]] - nem hibátlan, aki hibát talál benne javítsa

==== Beugró feladatsorok ====
* [[Media:opre_vizsga_beugro_20110606.pdf|2011.06.06. beugró]]
* [[Media:opre_vizsga_beugro_20110523.pdf|2011.05.23. beugró]]
* [[Media:opre_vizsga_beugro_20110117.pdf|2011.01.17. beugró]]
* [[Media:opre_vizsga_beugro_20110111.pdf|2011.01.10. beugró]]
* [[Media:opre_vizsga_beugro_20101220.pdf|2010.12.20. beugró]]
* [[Media:opre_vizsga_beugro_20100615.pdf|2010.06.15. beugró]]
* [[Media:opre_vizsga_beugro_20100608.pdf|2010.06.08. beugró]]
* [[Media:opre_vizsga_beugro_20100601.pdf|2010.06.01. beugró]]
* [[Media:opre_vizsga_beugro_pelda.pdf|2010-es minta beugró]], [[Media:opre_vizsga_beugro_pelda_megoldas.pdf|megoldása]]

==== Igaz-hamis ====
[[Operációs rendszerek - Igaz-hamis vizsgakérdések|Igaz-hamis kikérdező]]

=== Nagyfeladatlap ===
* A beugrót követi a nagyfeladatlap kitöltése. A nagyfeladatlap 30 tesztkérdést (8 kérdéscsoport), és 2 nagyfeladaot tartalmaz. A vizsgában nagyobb arányban szerepelnek benne Windows, UNIX/Linux, virtualizáció, biztonság, stb. kérdések a ZH-hoz képest.
==== Nagyfeladatlap feladatsorok és kidolgozások ====
* [[Media:opre_vizsga_20100615_megoldas.pdf|2010.06.15. vizsga nagyfeladata hivatalos megoldással]]
* [[Media:opre_vizsga_20100608_megoldas.pdf|2010.06.08. vizsga nagyfeladata hivatalos megoldással]]
* [[Media:opre_vizsga_20100601_megoldas.pdf|2010.06.01. vizsga nagyfeladata hivatalos megoldással]]
* [[Media:opre_vizsga_20100125.jpg|2010.01.25. vizsga nagyfeladata]]
* [[OpReVizsga20100118PrioritasInverzio|2010.01.18. vizsga nagyfeladatai nem hivatalos megoldás]]
* [[Media:opre_vizsga_20100106.jpg|2010.01.06. vizsga nagyfeladata]]
* [[OpReVizsga20090615|2009.06.15. vizsga nagyfeladatai]]
* [[OpReVizsga20090608|2009.06.08. vizsga nagyfeladatai]]
* [[Media:opre_vizsga_20090122.jpg|2009.01.22. vizsga nagyfeladata]]
* [[Media:opre_vizsga_20090112.pdf|2009.01.12. vizsga nagyfeladata]]
* [[Media:opre_vizsga_20081222.jpg|2008.12.22. vizsga nagyfeladata]]
* [[Media:opre_vizsga_20081215.jpg|2008.12.15. vizsga nagyfeladata]]
* [[OpReVizsga2008junius19|2008.06.19. vizsga nagyfeladatai]]
* [[OpReVizsga2008junius11megoldas|2008.06.11. vizsga nagyfeladatai és beugró nem hivatalos megoldással]]
* [[OpReVizsga2008majus20megoldas|2008.05.01. vizsga nagyfeladatai és beugró nem hivatalos megoldással]] '''(hiányzik: beugró 3 nagykérdések 2)'''
* [[OpReVizsga2007junius12megoldas|2007.06.12. vizsga nagyfeladatai és beugró nem hivatalos megoldással]] '''(hiányzik: nagykérdések 1, 2, 3)'''

== Kedvcsináló ==
[[OpReKedvcsinalo|Kedvcsináló]]

==Egyéb anyagok/linkek==
===Észrevételek===
Több probléma is akad a tárgy wiki adatlapjával ill. a felkészüléssel kapcsolatban:
* Hiányos, hibás kidolgozások. Arról van szó, hogy hibás/téves információkat tanulunk meg belőlük.
* Magolás, beugrókérdések betanulása. Amikor nem az anyagrész megértése, hanem a "beseggelése" történik. Vizsgán gyakran szokott olyan történni, hogy felteszik a kérdés ellenkezőjét, vagy kicsit változtatnak rajta. Az a tapasztalat, hogy az emberek ilyenkor is a standard (wikis bemagolt) választ adják vissza, ami természetesen nem jó.
* A wikin található tartalomért, az esetlegesen hiányzó anyagrészekért és az előforduló hibákért nem vállalunk felelősséget. Konzultáltunk az oktatókkal: szerintük minden előadáson elhangzott anyag szerepel, a jelenlegi állapot már alkalmas lehet egy sikeres zh/vizsga felkészüléshez. Ha hibát / hiányosságot találtál az oldalon található anyagokban, vagy esetleg téves információt közöltünk, kérlek írj a tárgy levelezési listájára, vagy a vitalapra.

{{Lábléc_-_Mérnök_informatikus_alapszak}}

Fájl:Opre Vizgya Jegyztet 2014 tavasz.pdf

2014-06-11T18:12:13Z

Ewsd: 2014 tavaszi előadásdiák tömör jegyzete

2014 tavaszi előadásdiák tömör jegyzete

Algoritmuselmélet - PZH, 2013.04.24.

2014-03-30T15:29:21Z

Ewsd: /* 7. Feladat */

{{Vissza|Algoritmuselmélet}}

==2013.04.24. PZH megoldásai==
===1. Feladat (Van megoldás)===
Egy algoritmus lépésszámáról tudjuk, hogy <math> T(n) = T\left(\left \lfloor \frac{n}{4} \right \rfloor\right) + O(n^2)</math> és tudjuk azt is, hogy <math> T(1)=T(2)=T(3)=1</math>. Bizonyítsa be, hogy <math> T(n)=O(n^2)</math>.
{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=

Van olyan <math> c > 0</math> és <math> n_0</math>, hogy <math> n>n_0</math> esetén
<math> T(n)=T\left(\left \lfloor \frac{n}{4} \right \rfloor\right)+O(n^2) \leq T\left(\left \lfloor \frac{n}{4} \right \rfloor\right)+cn^2 \leq T\left(\left \lfloor \frac{n}{16} \right \rfloor\right)+c\left(n^2+\left(\frac{n^2}{4^2} \right)\right) \leq T\left(\left \lfloor \frac{n}{64} \right \rfloor\right) + c\left(n^2+\left(\frac{n^2}{4^2} \right)+\left(\frac{n^2}{16^2} \right)\right) \leq \dots </math>
<math> \dots \leq 1+cn^2\cdot\left(\sum_{i=0}^{\left \lfloor log_4n \right \rfloor} \left (\frac{1}{16} \right )^i\right)</math>

Azt kell észrevennünk, hogy ez tulajdonképpen egy mértani sor, amire van képletünk: 
<math>\sum_{i=0}^{k} r^i = \frac{1-r^{k+1}} {1-r} </math>, ahol <math> k = \left \lfloor log_4n \right \rfloor, r = \frac{1}{16}</math>, vagyis <math>\frac{1-\frac{1}{16}^{\left \lfloor log_4n \right \rfloor+1}} {1-\frac{1}{16}}</math> 

<math>\frac{1-\frac{1}{16}^{\left \lfloor log_4n \right \rfloor+1}} {1-\frac{1}{16}} < 2 ,</math><big>ha</big> <math> n \geq 1</math> ''(A lényeg, hogy felülről becsüljük!)''

Tehát <math> T(n) = \dots \leq 1+2 \cdot cn^2=O(n^2)</math>
}}

===2. Feladat (Van megoldás)===
Adott egy teljes bináris fa, a csúcsaiba egész számok vannak írva, összesen ''n'' darab (a fa nem feltétlenül bináris keresőfa). Adjon algoritmust, ami <math>O(n)</math> lépésben megkeres egy olyan csúcsot a fában, aminek a részfája kupac, és aminek a magassága a legető legnagyobb az összes ilyen csúcs közül.
{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=
{{Rejtett
|mutatott=<big>''Megjegyzések a feladathoz''</big>
|szöveg=
*Bár nem tartozik a feladathoz, talán érdemes megjegyezzem, hogy bináris kereső fa nem is lehetne, hiszen akkor ott kapásból csak a legalsó szinten lévő elemek lehetnek kupacok (egy 1 elemet tartalmazó kupac), hiszen bináris keresőfánál balra kisebbek, jobbra nagyobbak vannak, míg kupacnál balra és jobbra is nagyobbak vannak.
*Továbbá a teljes bináris fára azért van szükség, mert így "jóval egyszerűbb" a feladat, és nem kell szívózni annak vizsgálatával, hogy az adott részfa teljes bináris fa-e (ugyebár ez a kupac egyik fontos tulajdonsága).
}}
Minden csúcsban 3 adatot fogunk számon tartani: Érték (ez persze adott már), részfa magassága (jelüljük M-mel), és egy bool érték (IGAZ/HAMIS, jelöljük B-vel), hogy igaz-e a részfájára, hogy az kupac.
*Első lépésben a legalsó szinteken lévő csúcsok esetén <math>M:=1, B:=IGAZ</math>.
*Legyen egy változónk, amiben tároljuk, hogy melyik csúcsra igaz, hogy a részfája a "legnagyobb" kupac (kezdeti értéke legyen mondjuk az egyik legalsó szinten lévő csúcs).
*Minden további szinten az a feladatunk, hogy megnézzük az adott csúcs (x) bal, és jobb fiát <math>(JOBB(x), BAL(x))</math>.
**Megnézzük, hogy nagyobbak-e, mint x, majd megnézzük, hogy kupac tulajdonsággal bírnak-e:
***Ha <math>BAL(x),JOBB(x) > x;BAL(x).B=JOBB(x).B=IGAZ\Rightarrow\Rightarrow x.M := BAL(x).M+1, x.B := IGAZ</math> majd a változónkba belerakjuk a csúcsot. ''Vagyis ha mindkettő nagyobb, és mindkettő kupac tulajdonsággal bír, akkor a csúcs részfa magassága 1-gyel nagyobb lesz, mint az egyik (bal, vagy jobb) fia magassága, és kupac tulajdonságú lesz.''
***Ha <math>BAL(x) < x</math> VAGY <math>JOBB(x) < x</math> VAGY <math>BAL(x).B=HAMIS</math> VAGY <math>JOBB(x).B=HAMIS\Rightarrow\Rightarrow x.M := BAL(x).M+1, x.B := HAMIS</math>. ''Vagyis ha bármelyik feltétel nem teljesül (valamelyik fia kisebb, avagy valamelyik gyerekére nem igaz, hogy kupac tulajdonságú), akkor maga a csúcs sem lehet már kupac tulajdonságú (itt a magasságot nem is kéne beállítani, de...hát miért is ne).''
Mivel minden csúcsot csak egyszer látogatunk meg, így <math>O(n)</math> lépésben megyünk végig a gráfon.
}}

===3. Feladat (Van megoldás)===
Kukori és Kotkoda egy-egy bináris fára gondolnak (nem feltétlenül bináris keresőfákra). Következik-e, hogy a két fa azonos, ha

'''(a)''' inorder bejárással kilolvasva a két fát ugyanazt a számsorozatot kapják?

'''(b)''' preorder bejárással kiolvasva a két fát ugyanazt a számsorozatot kapják?
{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=

Mindkét esetben 1-1 ellenpéldát kell szolgáltatni:
*'''a)'''

[[File:Algel_pzh_2013tavasz_Egyik.png|200px]] [[File:Algel_pzh_2013tavasz_Masik.png|200px]]

Mindkét gráfot A-B-C-D-E sorrendben olvassuk ki, de mégsem egyeznek meg, tehát nem következik.

*'''b)'''

[[File:Algel_pzh_2013tavasz_Egyik_1.png|200px]] [[File:Algel_pzh_2013tavasz_Masik_2.png|200px]]

Mindkét gráfot F-G-H-J-K sorrendben olvassuk ki, de mégsem egyeznek meg, tehát nem következik.

}}

===4. Feladat===
Éllistával adott n csúcsú, élsúlyzott, irányítatlan gráfként ismerjük egy ország úthálózatát (a csomópontok a városok, az élek a közvetlen összeköttetések a városok között). Az élek súlya azt adja meg, hogy hány (egész) perc alatt tudjuk megtenni az adott útszakaszt. Nagy havazás várható, de szerencsére pontosan tudjuk a követekző k percre, hogy mely élek (utak) mikortól nem lesznek járhatóak. Ha egyszer járhatatlanná válnak, akkor úgy is maradnak, ezután már az úton nem lehet közlekedni, és ha épp az adott élen vagyunk, amikor az járhatatlanná válik, akkor elakadunk.
Adjon O(k(n+e)) lépést használó algoritmust, ami az adatok ismeretében el tudja dönteni, hogy el lehet-e jutni A városból B városba, ha most azonnal elindulunk!
{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=

TODO
}}

===5. Feladat (Van megoldás)===
Egy <math>n</math> soros és kettő oszlopos táblázatban adott <math>n</math> számpár (egy sor egy számpárt tartalmaz, a számok mind különböző egész számok a táblázatban). Szeretnénk a táblázat sorait úgy átrendezni, hogy a 2. oszlop szerint növekvő sorrendben legyenek a sorok (számpárok). Egy fajta műveletet hajthatunk végre: kijelölhetünk néhány egymást alatti sort (számpárt) és ezeket rendezhetjük az első oszlop szerint növekvően vagy csökkenően. Adjon algoritmust, ami csak ezt a fajta műveletet használva <math>O(n)</math> lépésben megoldja a feladatot!
{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=

*Rendezzük a tömböt az 1. oszlop szerint növekvően.
*A továbbiakban minden <math>i.</math> lépésben megkeressük az <math>i.</math> legkisebb elemet, és a helyére tesszük.
**Megkeressük a 2. oszlopban az <math>i.</math> legkisebbet, az ő helye a tömbben legyen <math>k</math>
**Mivel az 1. oszlop szerint növekvően vannak a számpárok, így ahhoz, hogy a <math>k.</math> elem az <math>i.</math> helyre kerüljön, a számokat csökkenő sorrendbe kell rendezni az <math>[i \rightarrow k] </math> intervallumon.
**Ha ezt megcsináltuk, akkor az első <math>i</math> helyen már rendezve lesz a tömb.
**Az <math>[i+1 \rightarrow n]</math> intervallumon rendezzük a számokat növekvő sorrendben.
**Ezt addig folytatjuk, míg nincs minden számpár a helyén.

*A műveletet minden lépésben <math>\approx 2n</math> alkalommal használjuk:
**Először növekvő sorrendbe rendeztük az egész tömböt.
**Utána minden <math>i.</math> lépésben 2x:
***Egyszer a helyére rakjuk az elemet azzal, hogy csökkenő sorrendbe rakjuk a számpárokat (persze csak a megfelelőket).
***Majd újra növekvőbe a maradék számpárokat.
*Így az algoritmus <math>O(n)</math> lépéssel rendezi a számpárokat a 2. oszlop szerint.
:::::::::::::::::[[File:algel_pzh_2013tavasz_5_1.PNG|400px]]
}}

===6. Feladat (Van megoldás)===
Adott egy <math> n </math> hosszú tömb. Tudjuk, hogy a tömb első néhány (<math> k </math> darab) elem 0, a többi 1, de <math> k </math> értékét nem ismerjük. Adjon <math> O(logk) </math> (nem <math> O(logn) </math> )1 összehasonlítást használó algoritmust, ami meghatározza <math> k </math> értékét.

''1 A feladatban <math> O(logk) </math> szerepel, de az csak elgépelés.''
{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=

*Először nézzük meg, hogy az első 2 elem <math>0-1</math>-e, ha igen, akkor <math> k=1 </math>.
*Ha nem, akkor minden további lépésnél ugorjunk a 2x annyiadik cellába (ez legyen <math> m </math>), ha pedig túl lépnénk a tömböt ezzel, akkor az utolsóba.
*Vizsgáljuk meg, hogy "hol vagyunk": ''(az aktuális cellát, és a 2 szomszédját)''
**Ha <math>0-0-0</math>-t látunk, akkor ugrunk megint 2x akkorát ''(ugyanazzal a kritériummal, mint előbb)''.
**Ha <math>0-0-1</math>-t látunk, akkor <math> k=m </math>.
**Ha <math>0-1-1</math>-t látunk, akkor <math> k=m-1 </math>.
**Ha <math>1-1-1</math>-t látunk, akkor egy bináris keresés segítségével<big>(1)</big> a 2 legutóbbi vizsgált elem közötti cellákban megkeressük a <math>0-1-1</math>, vagy <math>0-0-1</math> felállást, és a <math>k</math> értékét a látottak alapján beállítjuk <math>( k=m-1 </math> vagy <math> k=m )</math>.

<big>(1)</big> '' Ha <math>0-0-0</math>-t lát, jobbra lép, ha <math>1-1-1</math>-t, akkor balra, másik 2 esetben pedig találatunk van.''
:::::::::::[[File:algel_pzh_2013tavasz_6_1.PNG|400px]]

*Az algoritmus működése alapján belátható, hogy <math> O(logk) </math> időben fut.
}}

===7. Feladat===
Adott egy n és egy k elemet tartalmazó kupac. Adjon olyan O(n + k) összehasonlítást használó algoritmust, ami létrehoz egy olyan kupacot, ami a két kupacban tárolt elemek halmazának únióját tartalmazza. (TFH a két kupacban csupa különböző számocska áll.)
{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=

TODO
}}

===8. Feladat (Van megoldás)===
Bizonyítsa be, hogy egy piros-fekete fában egy levél testvére vagy levél, vagy piros csúcs!
{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=

*Összesen 5 felállás lehet: [[File:algel_pzh_2013tavasz_8_1.png|400px]]
**Ebből az 1. és a 4. jó is ''(a 4. persze csak akkor, ha X az nem a főgyökér)''.
**A 3. - kis módosítással - látszik, hogy szintén fenn állhat gond nélkül: [[File:Algel pzh 2013tavasz 8 2.png|100px]]
**Egyedül a 2. és az 5. problémás. Ezek viszont rosszak is, hiszen mindkét esetben elmondható, hogy X-nek a fekete magassága jobbra 1, balra viszont legalább 2, mert az Y csúcsnak legalább 1-1 levél fia van. Tehát belső csúcsnál ilyen állapot nem állhat fent.

*Az első 2 esetben azt bizonyítottuk, hogy levél testvére lehet levél, vagy piros csúcs.
*A 3. esetben pedig azt, hogy nem lehet fekete csúcs a levél testvére.
*Így be is bizonyítottuk, hogy levél testvére CSAK levél, vagy piros csúcs lehet.
}}

[[Kategória:Infoalap]]

Algoritmuselmélet - PZH, 2013.04.24.

2014-03-30T14:56:13Z

Ewsd: /* 4. Feladat */

{{Vissza|Algoritmuselmélet}}

==2013.04.24. PZH megoldásai==
===1. Feladat (Van megoldás)===
Egy algoritmus lépésszámáról tudjuk, hogy <math> T(n) = T\left(\left \lfloor \frac{n}{4} \right \rfloor\right) + O(n^2)</math> és tudjuk azt is, hogy <math> T(1)=T(2)=T(3)=1</math>. Bizonyítsa be, hogy <math> T(n)=O(n^2)</math>.
{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=

Van olyan <math> c > 0</math> és <math> n_0</math>, hogy <math> n>n_0</math> esetén
<math> T(n)=T\left(\left \lfloor \frac{n}{4} \right \rfloor\right)+O(n^2) \leq T\left(\left \lfloor \frac{n}{4} \right \rfloor\right)+cn^2 \leq T\left(\left \lfloor \frac{n}{16} \right \rfloor\right)+c\left(n^2+\left(\frac{n^2}{4^2} \right)\right) \leq T\left(\left \lfloor \frac{n}{64} \right \rfloor\right) + c\left(n^2+\left(\frac{n^2}{4^2} \right)+\left(\frac{n^2}{16^2} \right)\right) \leq \dots </math>
<math> \dots \leq 1+cn^2\cdot\left(\sum_{i=0}^{\left \lfloor log_4n \right \rfloor} \left (\frac{1}{16} \right )^i\right)</math>

Azt kell észrevennünk, hogy ez tulajdonképpen egy mértani sor, amire van képletünk: 
<math>\sum_{i=0}^{k} r^i = \frac{1-r^{k+1}} {1-r} </math>, ahol <math> k = \left \lfloor log_4n \right \rfloor, r = \frac{1}{16}</math>, vagyis <math>\frac{1-\frac{1}{16}^{\left \lfloor log_4n \right \rfloor+1}} {1-\frac{1}{16}}</math> 

<math>\frac{1-\frac{1}{16}^{\left \lfloor log_4n \right \rfloor+1}} {1-\frac{1}{16}} < 2 ,</math><big>ha</big> <math> n \geq 1</math> ''(A lényeg, hogy felülről becsüljük!)''

Tehát <math> T(n) = \dots \leq 1+2 \cdot cn^2=O(n^2)</math>
}}

===2. Feladat (Van megoldás)===
Adott egy teljes bináris fa, a csúcsaiba egész számok vannak írva, összesen ''n'' darab (a fa nem feltétlenül bináris keresőfa). Adjon algoritmust, ami <math>O(n)</math> lépésben megkeres egy olyan csúcsot a fában, aminek a részfája kupac, és aminek a magassága a legető legnagyobb az összes ilyen csúcs közül.
{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=
{{Rejtett
|mutatott=<big>''Megjegyzések a feladathoz''</big>
|szöveg=
*Bár nem tartozik a feladathoz, talán érdemes megjegyezzem, hogy bináris kereső fa nem is lehetne, hiszen akkor ott kapásból csak a legalsó szinten lévő elemek lehetnek kupacok (egy 1 elemet tartalmazó kupac), hiszen bináris keresőfánál balra kisebbek, jobbra nagyobbak vannak, míg kupacnál balra és jobbra is nagyobbak vannak.
*Továbbá a teljes bináris fára azért van szükség, mert így "jóval egyszerűbb" a feladat, és nem kell szívózni annak vizsgálatával, hogy az adott részfa teljes bináris fa-e (ugyebár ez a kupac egyik fontos tulajdonsága).
}}
Minden csúcsban 3 adatot fogunk számon tartani: Érték (ez persze adott már), részfa magassága (jelüljük M-mel), és egy bool érték (IGAZ/HAMIS, jelöljük B-vel), hogy igaz-e a részfájára, hogy az kupac.
*Első lépésben a legalsó szinteken lévő csúcsok esetén <math>M:=1, B:=IGAZ</math>.
*Legyen egy változónk, amiben tároljuk, hogy melyik csúcsra igaz, hogy a részfája a "legnagyobb" kupac (kezdeti értéke legyen mondjuk az egyik legalsó szinten lévő csúcs).
*Minden további szinten az a feladatunk, hogy megnézzük az adott csúcs (x) bal, és jobb fiát <math>(JOBB(x), BAL(x))</math>.
**Megnézzük, hogy nagyobbak-e, mint x, majd megnézzük, hogy kupac tulajdonsággal bírnak-e:
***Ha <math>BAL(x),JOBB(x) > x;BAL(x).B=JOBB(x).B=IGAZ\Rightarrow\Rightarrow x.M := BAL(x).M+1, x.B := IGAZ</math> majd a változónkba belerakjuk a csúcsot. ''Vagyis ha mindkettő nagyobb, és mindkettő kupac tulajdonsággal bír, akkor a csúcs részfa magassága 1-gyel nagyobb lesz, mint az egyik (bal, vagy jobb) fia magassága, és kupac tulajdonságú lesz.''
***Ha <math>BAL(x) < x</math> VAGY <math>JOBB(x) < x</math> VAGY <math>BAL(x).B=HAMIS</math> VAGY <math>JOBB(x).B=HAMIS\Rightarrow\Rightarrow x.M := BAL(x).M+1, x.B := HAMIS</math>. ''Vagyis ha bármelyik feltétel nem teljesül (valamelyik fia kisebb, avagy valamelyik gyerekére nem igaz, hogy kupac tulajdonságú), akkor maga a csúcs sem lehet már kupac tulajdonságú (itt a magasságot nem is kéne beállítani, de...hát miért is ne).''
Mivel minden csúcsot csak egyszer látogatunk meg, így <math>O(n)</math> lépésben megyünk végig a gráfon.
}}

===3. Feladat (Van megoldás)===
Kukori és Kotkoda egy-egy bináris fára gondolnak (nem feltétlenül bináris keresőfákra). Következik-e, hogy a két fa azonos, ha

'''(a)''' inorder bejárással kilolvasva a két fát ugyanazt a számsorozatot kapják?

'''(b)''' preorder bejárással kiolvasva a két fát ugyanazt a számsorozatot kapják?
{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=

Mindkét esetben 1-1 ellenpéldát kell szolgáltatni:
*'''a)'''

[[File:Algel_pzh_2013tavasz_Egyik.png|200px]] [[File:Algel_pzh_2013tavasz_Masik.png|200px]]

Mindkét gráfot A-B-C-D-E sorrendben olvassuk ki, de mégsem egyeznek meg, tehát nem következik.

*'''b)'''

[[File:Algel_pzh_2013tavasz_Egyik_1.png|200px]] [[File:Algel_pzh_2013tavasz_Masik_2.png|200px]]

Mindkét gráfot F-G-H-J-K sorrendben olvassuk ki, de mégsem egyeznek meg, tehát nem következik.

}}

===4. Feladat===
Éllistával adott n csúcsú, élsúlyzott, irányítatlan gráfként ismerjük egy ország úthálózatát (a csomópontok a városok, az élek a közvetlen összeköttetések a városok között). Az élek súlya azt adja meg, hogy hány (egész) perc alatt tudjuk megtenni az adott útszakaszt. Nagy havazás várható, de szerencsére pontosan tudjuk a követekző k percre, hogy mely élek (utak) mikortól nem lesznek járhatóak. Ha egyszer járhatatlanná válnak, akkor úgy is maradnak, ezután már az úton nem lehet közlekedni, és ha épp az adott élen vagyunk, amikor az járhatatlanná válik, akkor elakadunk.
Adjon O(k(n+e)) lépést használó algoritmust, ami az adatok ismeretében el tudja dönteni, hogy el lehet-e jutni A városból B városba, ha most azonnal elindulunk!
{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=

TODO
}}

===5. Feladat (Van megoldás)===
Egy <math>n</math> soros és kettő oszlopos táblázatban adott <math>n</math> számpár (egy sor egy számpárt tartalmaz, a számok mind különböző egész számok a táblázatban). Szeretnénk a táblázat sorait úgy átrendezni, hogy a 2. oszlop szerint növekvő sorrendben legyenek a sorok (számpárok). Egy fajta műveletet hajthatunk végre: kijelölhetünk néhány egymást alatti sort (számpárt) és ezeket rendezhetjük az első oszlop szerint növekvően vagy csökkenően. Adjon algoritmust, ami csak ezt a fajta műveletet használva <math>O(n)</math> lépésben megoldja a feladatot!
{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=

*Rendezzük a tömböt az 1. oszlop szerint növekvően.
*A továbbiakban minden <math>i.</math> lépésben megkeressük az <math>i.</math> legkisebb elemet, és a helyére tesszük.
**Megkeressük a 2. oszlopban az <math>i.</math> legkisebbet, az ő helye a tömbben legyen <math>k</math>
**Mivel az 1. oszlop szerint növekvően vannak a számpárok, így ahhoz, hogy a <math>k.</math> elem az <math>i.</math> helyre kerüljön, a számokat csökkenő sorrendbe kell rendezni az <math>[i \rightarrow k] </math> intervallumon.
**Ha ezt megcsináltuk, akkor az első <math>i</math> helyen már rendezve lesz a tömb.
**Az <math>[i+1 \rightarrow n]</math> intervallumon rendezzük a számokat növekvő sorrendben.
**Ezt addig folytatjuk, míg nincs minden számpár a helyén.

*A műveletet minden lépésben <math>\approx 2n</math> alkalommal használjuk:
**Először növekvő sorrendbe rendeztük az egész tömböt.
**Utána minden <math>i.</math> lépésben 2x:
***Egyszer a helyére rakjuk az elemet azzal, hogy csökkenő sorrendbe rakjuk a számpárokat (persze csak a megfelelőket).
***Majd újra növekvőbe a maradék számpárokat.
*Így az algoritmus <math>O(n)</math> lépéssel rendezi a számpárokat a 2. oszlop szerint.
:::::::::::::::::[[File:algel_pzh_2013tavasz_5_1.PNG|400px]]
}}

===6. Feladat (Van megoldás)===
Adott egy <math> n </math> hosszú tömb. Tudjuk, hogy a tömb első néhány (<math> k </math> darab) elem 0, a többi 1, de <math> k </math> értékét nem ismerjük. Adjon <math> O(logk) </math> (nem <math> O(logn) </math> )1 összehasonlítást használó algoritmust, ami meghatározza <math> k </math> értékét.

''1 A feladatban <math> O(logk) </math> szerepel, de az csak elgépelés.''
{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=

*Először nézzük meg, hogy az első 2 elem <math>0-1</math>-e, ha igen, akkor <math> k=1 </math>.
*Ha nem, akkor minden további lépésnél ugorjunk a 2x annyiadik cellába (ez legyen <math> m </math>), ha pedig túl lépnénk a tömböt ezzel, akkor az utolsóba.
*Vizsgáljuk meg, hogy "hol vagyunk": ''(az aktuális cellát, és a 2 szomszédját)''
**Ha <math>0-0-0</math>-t látunk, akkor ugrunk megint 2x akkorát ''(ugyanazzal a kritériummal, mint előbb)''.
**Ha <math>0-0-1</math>-t látunk, akkor <math> k=m </math>.
**Ha <math>0-1-1</math>-t látunk, akkor <math> k=m-1 </math>.
**Ha <math>1-1-1</math>-t látunk, akkor egy bináris keresés segítségével<big>(1)</big> a 2 legutóbbi vizsgált elem közötti cellákban megkeressük a <math>0-1-1</math>, vagy <math>0-0-1</math> felállást, és a <math>k</math> értékét a látottak alapján beállítjuk <math>( k=m-1 </math> vagy <math> k=m )</math>.

<big>(1)</big> '' Ha <math>0-0-0</math>-t lát, jobbra lép, ha <math>1-1-1</math>-t, akkor balra, másik 2 esetben pedig találatunk van.''
:::::::::::[[File:algel_pzh_2013tavasz_6_1.PNG|400px]]

*Az algoritmus működése alapján belátható, hogy <math> O(logk) </math> időben fut.
}}

===7. Feladat===
TODO
{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=

TODO
}}

===8. Feladat (Van megoldás)===
Bizonyítsa be, hogy egy piros-fekete fában egy levél testvére vagy levél, vagy piros csúcs!
{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=

*Összesen 5 felállás lehet: [[File:algel_pzh_2013tavasz_8_1.png|400px]]
**Ebből az 1. és a 4. jó is ''(a 4. persze csak akkor, ha X az nem a főgyökér)''.
**A 3. - kis módosítással - látszik, hogy szintén fenn állhat gond nélkül: [[File:Algel pzh 2013tavasz 8 2.png|100px]]
**Egyedül a 2. és az 5. problémás. Ezek viszont rosszak is, hiszen mindkét esetben elmondható, hogy X-nek a fekete magassága jobbra 1, balra viszont legalább 2, mert az Y csúcsnak legalább 1-1 levél fia van. Tehát belső csúcsnál ilyen állapot nem állhat fent.

*Az első 2 esetben azt bizonyítottuk, hogy levél testvére lehet levél, vagy piros csúcs.
*A 3. esetben pedig azt, hogy nem lehet fekete csúcs a levél testvére.
*Így be is bizonyítottuk, hogy levél testvére CSAK levél, vagy piros csúcs lehet.
}}

[[Kategória:Infoalap]]

Mérés 1 Ellenőrző kérdések 3

2013-10-11T22:39:44Z

Ewsd: /* 4. kérdés */

{{Vissza|Mérés laboratórium 1.}}

'''AZ ELLENŐRZŐ KÉRDÉSEKRE ÖSSZEÍRT VÁLASZOK BEMAGOLÁSA/MEGTANULÁSA NEM HELYETTESÍTI A MÉRÉSI ÚTMUTATÓ ÁTOLVASÁSÁT!!! OLVASSÁTOK ÁT A JEGYZETEKET, MÉRÉSI ÚTMUTATÓKAT IS!!!'''

'''Erre a mérésre el kell készíteni a közös, nagy házitok részletes blokkvázlatát!'''

==1. kérdés==
;A megismert soros adatátviteli módszerek közül melyiknél nem szükséges az órajelet is továbbítani?
:Az UART-nál, ott az adategységek azonosítása a lokális rendszerórák használatán alapul.
==2. kérdés==
;Miért nem könnyű elérni néhány Mbit/s sebességet UART átvitelnél?
:Az ok: nem igényel külön dedikált órajelvezetéket, ez korlátozza az elérhető maximális sebességet.
==3. kérdés==
;Melyik soros adatátviteli mód nem támogatja busz kialakítását?
:Az UART, mivel ott a kapcsolat pont-pont típusú. (pl. számítógép-modem, számítógép-terminál)
==4. kérdés==
;Milyen módon vezéreljük a 4 számjegyű 7 szegmenses kijelzőt?
:Az a, b, c, d, e, f, g és tizedespont szegmensjeleket időosztásban küldjük sorban az anódokra, a megfelelő anódjel kiválasztásával.

==5. kérdés==
;Milyen adatátviteli paraméterek állíthatók be a PC soros kommunikációs csatornáin?
:bit/sec, adatbitek, paritás, stopbitek, átvitelvezérlés
==6. kérdés==
;Egy 100 byte méretű fájl átvitele aszinkron soros csatornán 115200 b/s sebesség mellett 8N1 (8 bit adat, nincs paritás, 1 STOP bit) formátumban minimum menyi ideig tart?
:100 byte = 800 bit, byte-onként 1 stopbit ÉS EGY START BIT = 200 bit, összesen 1000 bit, 115200 bit/sec sebességgel ez 8,68 ms alatt megy át
==7. kérdés==
;Egy 115200 b/s, 8N1 beállítású UART átvitel esetén mekkora eltérés engedhető meg az adó és a vevő bitidejében, ha sikeres átvitelt szeretnénk?
:A vevőnek elvileg bitidőnként, a bitidő közepén kellene mintavételezni az adatokat. Mivel az adó és a vevő frekvenciája kicsit eltér, ezért ez nem teljesül. Ha a hiba 1 bitidő alatt dt (delay time), akkor ez az N-edik bit mintavételezésekor N*dt-re nő, ami akkor okoz hibát, ha a legutolsó bitnél eléri a bitidő határát. Mivel a mintevételezés a bitidő közepén kezdődik, ezért N*dt < T/2-nek teljesülni kell (minden START bitnél újra szinkronizálódik a vevő).

:Mindez számokkal:
:8N1 beállításból tudjuk, hogy 1 Start bit + 8 Adat bit + 1 Stop bit == 10 bitet kell átküldeni. (N = 10)
:115200 b/s : 115200 bit megy át másodpercenként -> 1 bit: 1/115200 => 8.68 us.

:Képletbe behelyettesítve:
:10 * dt < 8.68/2
:dt < 0.434 us

:(0.434/8.86)*100 = 5% eltérés.

:Megj.: Sebességtől független, csak beállítástól függ, hiszen
:x bit/s esetén:
:t= 1/x,
:n db dt<1/x/2 ahol n a bitek száma, dt delay time,
:dt < 1/x/2/n.
:dt/t = (1/x/2/n)/(1/x)=1/2n
:8N1 esetén n=10, így dt/t= 0,05 ami 5 %. -- [[AndorSzabo]]
==8. kérdés==
;Hasonlítsa össze sebesség szerint a soros adatátviteli módokat!
:SPI 10 Mbit/sec > I²C 3400 Kbit/sec > UART 115 Kbit/sec
==9. kérdés==
;Mi alapján osztályozódik az SPI 4 átviteli módja?
:Az adatok kiléptetése és a beérkezett adatok mintavételezése az órajel egymással ellentétes éleire történik. Ennek megfelelően, továbbá figyelembe véve az órajel kiindulási nyugalmi értékét is, alapvetően 4 fajta SPI átviteli ciklus definiálható.
==10. kérdés==
;Mit jelent a START bit az UART keretben, milyen a polaritása?
:A tetszőleges időpontban beérkező adatkeret START bitjének lefutó éle szolgál egyfajta szinkronizációs pont kijelölésére, ami után a küldő és fogadó egység az adatkeret időtartamára összeszinkronizálódik, legalábbis ami az adatkeretben megjelenő bitértékek értelmezését illeti. A START bit polaritása alacsony (0).
==11. kérdés==
;Mit jelent a páros paritás, az AB hexadecimális értékű adathoz milyen érték tartozik?
:Ha az adatbitek páratlanul tartalmaztak 1-est és a paritásbit értéke is 1, vagy az adatbitek páros számú 1-est tartalmaztak és a paritásbit értéke 0, akkor páros (even) paritásról beszélünk. (Ha az adatbitek párosan tartalmaztak 1-est és a paritásbit értéke is 1, vagy az adatbitek páratlan számú 1-est tartalmaztak és a paritásbit értéke 0, akkor páratlan (odd) paritásról beszélünk.) 
:http://en.wikipedia.org/wiki/Parity_bit

:(HEX) AB = (BIN) 10101011, 1-es paritásbit tartozik hozzá.
==12. kérdés==
;Hány vezeték kell 4 periféria SPI buszon használatához?
:3+4 = 7 vezeték, mivel SPI esetén 3 + n kell, ahol n a perifériák száma.
:MISO,MOSI,SCK,SSN (N=0,1,2,3)

==Régebbi kérdések==
;Mik a tipikus UART adatátviteli sebességek?
:110, 300, 1200, 2400, 4800, 9600, 19200, 28800, 38400, 57600, 76800, 115200 bit/sec

;Miért nem könnyű elérni néhány Mbit/s sebességet I²C (ejtsd: eye-squared-see) átvitelnél?
:Az I²C buszon a karakterek átvitele keretekben történik és 9 órajel ütemet vesz igénybe. A kereteket a START és STOP fázisok határolják. Az I²C buszon a címzés hagyományosan 7 biten történik (ez komoly korlát). Ezt a kompatibilitás megtartásával kiterjesztették 10 bitesre.

:Az átviteli sebesség 4 kategóriában választható, 0 - 100kHz, 0 - 400kHz, 0 – 1MHz és 3,4MHz.

;Mit jelent a küldő és a fogadó egység az I²C ciklus során?
:küldő (adó): adatokat küld, fogadó (vevő): adatokat fogad

:Olvasás módban:
:küldő: szolga, fogadó: mester

:Írás módban:
:küldő: mester, fogadó: szolga

;Mekkora a legnagyobb beállítható átviteli sebesség a PC soros portjain a laborban?
:921600 bit/sec

;Mi a szerepe az adó ill. a vevő oldali FIFO puffereknek? Mi a mérete ezeknek a PC-ben ill. a mérőkártyán? Hogyan használható a pufferek tele ill. félig tele jelzése az adatvesztés megakadályozására?
:adó oldali puffer: tárolja az adatokat, ha gyorsabban állnak rendelkezésre, mint ahogy ki tudjuk küldeni; vevő oldali puffer: tárolja az adatokat, ha azok gyorsabban érkeznek, mint ahogy fel tudnánk azokat dolgozni; FIFO: elején teszünk be, végén veszünk ki; a PC-ben és a mérőkártyán is 8 byte a mérete; a tele és a félig tele jelzés az adatforgalom szabályozására szolgál

;Hogyan érzékelhető a START és a STOP fázis az I²C buszon az egységek által?
:A START és STOP fázisok esetén az SDA adatvonal az SCL órajel magas értéke alatt vált értéket. START: le, STOP: fel

;Melyik buszciklus ideje hosszabb az I²C buszon (írás vagy olvasás)?
:I²C buszon az olvasás

;Hány bitet használnak az I²C busz kiterjesztett címzésénél?
:10 bitet

;Milyen keretformátumokat képes egy UART vezérlő előállítani ill. fogadni?
:1 START bit, értéke logikai alacsony
:Választható számú, 5, 6, 7, 8, esetleg 9 bit adat
:Paritásbit, amely ha van, akkor lehet páros, páratlan, mindig 1, mindig 0
:STOP bit, ami lehet 1, 1.5, 2

[[Category:Infoalap]]