Diff for ''

Revision 2
Author:
black
Time:
2025-04-01 20:18
Comment:
Smazat neplatnou nabídku práce
Revision 2
Author:
black
Time:
2025-04-01 20:18
Comment:
Smazat neplatnou nabídku práce
Deletions are marked like this. Additions are marked like this.
Line 1: Line 1:
# Stáž v oddělení Řízení IT rizik - Praha # Vypracovani semestralky
Line 3: Line 3:
<{ForumPost(poster="careermarket", timestamp=2016-07-21 07:23:14)}>
** Nejde Vám PwC a IT dohromady?
    Hledáme nové kolegy na stáže v našem oddělení Řízení IT rizik**
<{ForumPost(poster="aliandroo", timestamp=2010-11-27 02:40:05)}>
Potreboval bych pomoc s vypracovanim teto semestralky:
Line 7: Line 6:
    Jako součást našeho týmu rozvinete své znalosti a zkušenosti v oblastech jakou jsou:
    • mapování business procesů, testování interního kontrolního prostředí v oblasti IT, posouzení rizik
    • revize implementace a migrace ERP systémů (typicky SAP), řízení nebo posouzení IT projektů
    • posouzení zabezpečení síťové infrastruktury a datových skladů, penetrační testování
Mate-li zajem napiste mi [aliandro@seznam.cz](mailto:aliandro@seznam.cz)
Line 12: Line 8:
    Jako člen tohoto týmu budete využívat procesní a technické znalosti a zkušenosti pro zhodnocení kontrolního prostředí v auditovaných společnostech. Kromě této činnosti můžete poskytovat i řadu dalších konzultačních služeb v oblasti procesních kontrol, informačních systémů a zpracování dat přímo našim klientům. Zadání
Line 14: Line 10:
**Požadavky**
    • student/ka 3. - 5. ročníku studia na vysoké škole
    • přehled a zájem o podnikového oblast IT - fyzická i logická infrastruktura, procesy, rizika, IT bezpečnost a hrozby
    • analytické a logické myšlení
    • výborná znalost češtiny a dobrou znalost angličtiny
    • ochota cestovat v rámci ČR/regionu
Úkolem je realizovat program, který dokáže vypočítat efektivní průchod labyrintem s diamanty.
Line 21: Line 12:
[http://careermarket.cz/hledam-uplatneni ... il?id=1889](http://careermarket.cz/hledam-uplatneni/inzeraty/detail?id=1889) Vstupem programu je mapa labyrintu. Mapa je předaná v textové podobě na standardním vstupu. Pro jednoduchost předpokládáme, že mapa má obdélníkový tvar. V mapě jsou naznačené diamanty (znaky *), nepřekonatelné zdi (znak #) a volné prostranství (znak mezera). Labyrint má jediný vchod v některé z obvodových zdí. Zadávání labyrintu probíhá po řádcích. Každý řádek vstupu představuje jeden řádek mapy. Zadávání celého labyrintu je signalizováno koncem souboru (feof(stdin) je aktivní).
  
Výstupem programu je informace o tom, kolik diamantů lze z labyrintu odnést a dále informace o tom, kolik kroků v labyrintu je na to nejméně potřeba. Předpokládáme, že se můžeme pohybovat pouze ve směru vlevo/vpravo/nahoru/dolů, kde každý pohyb (o jedno políčko) je právě jeden krok. Cesta vždy začíná a končí vstupem do labyrintu.
  
Program musí být schopen detekovat nesprávný vstup. Pokud je zadaná neplatná mapa, program vypíše chybové hlášení a ukončí se. Formát chybového hlášení je zřejmý z ukázek níže. Za chybu je považováno:
  
    *
      v zadání labyrintu byly jiné znaky než mezera, hvězdička, křížek a odřádkování,
    *
      labyrint není obdélníkového tvaru,
    *
      labyrint není obehnán zdí,
    *
      do labyrintu není žádný vstup nebo naopak více než jeden vstup,
    *
      v labyrintu je celkem více než 20 diamantů (pro jednoduchost předpokládáme toto omezení).
  
Program je testován v omezeném prostředí. Je omezena doba běhu i dostupná paměť. Doba běhu je nastavena tak, aby vyhovělo i řešení hrubou silou bez heuristik. Výjimkou je bonusový test, který řešení bez alespoň základní heuristiky (zahazování neperspektivních průchodů) nezvládne časově.
Nápověda
  
    *
      Nejprve si spočtěte matici vzdáleností mezi jednotlivými diamanty a mezi vstupem a diamanty. Zde se hodí algoritmus procházení do šířky (BFS) ve variantě semínkového vyplňování (seed fill).
    *
      Sestavte cestu, která začíná a končí vstupním bodem a prochází všemi diamanty. Takových cest existuje mnoho (počet_diamantů faktoriál), postupně vypočtěte jejich délky (vzdálenosti znáte z matice vzdáleností vypočtené v předchozím bodě) a určete nejkratší z nich.
    *
      Pro vygenerování všech možných cest budete potřebovat rekurzi.
    *
      Může se stát, že některé diamanty nebudou dostupné, takové musíte z výpočtu cest vyloučit.
    *
      Popsané řešení (hrubou silou) není příliš rychlé. Proto je volen malý rozsah úlohy (do 20 diamantů), aby výpočet skončil v rozumné době. Řešená úloha (nalezení nejkratší cesty mezi diamanty) je optimalizační variantou problému obchodního cestujícího (TSP - traveling salesman problem). Úloha TSP patří mezi tzv. NP-úplné problémy, tedy problémy, pro které neznáme efektivní algoritmus jejich řešení. Úlohy tohoto typu dokážeme řešit pouze zkoušením všech možností, což mívá vysokou operační složitost (zde například faktoriální). Řešení bývá možné urychlit heuristikami, kdy se preferují perspektivní řešení (zde např. krátké cesty), naopak neperspektivní možnosti řešení (zde např. velmi dlouhé cesty) se buď vůbec nepočítají nebo se odkládají na později.
    *
      Referenční řešení používá dvě jednoduché heuristiky - pokud v průběhu vytváření cesty mezi diamanty zjistí, že cesta je delší než dosavadní nalezené minimum, dále již cestu nedokončuje a začne vytvářet cestu jinou. Druhou možností je preference cesty směrem k nejbližšímu diamantu (při vytváření cesty se první zkusí nejbližší diamant). Tím se program relativně brzy dostane k rozumné délce cesty (ale pozor - takto nalezená cesta nemusí být nejkratší). Výhodné je obě popsané heuristiky spojit.
  
Ukázka práce programu:

    Zadejte mapu:
    # ######
    # * *#
    # * #
    ########
    Diamantu: 3
    Delka cesty: 14
    
    Zadejte mapu:
    ##############
                 #
    ############ #
    #* #
    ##############
    Diamantu: 1
    Delka cesty: 50
    
    Zadejte mapu:
    ##################### ######
    #* # #
    ############ # #############
    # # # #
    # ############ # ######### #
    # *# # #
    # ############## # #########
    # # #
    # ######################## #
    #* * * #
    ############################
    Diamantu: 5
    Delka cesty: 148
    
    Zadejte mapu:
    #############
    #*# * # * #*#
    # # # # # # #
    # * # * # * #
    ###### ######
    Diamantu: 7
    Delka cesty: 46
    
    Zadejte mapu:
    ############################
    # * * #
    # ######## #
    # * # * # #
    # # ###### #
    # * * #
    # ############ * #
    # # * * # #
    # # * * # #
    # * ############ * #
    # * #
    ###################### #####
    Diamantu: 10
    Delka cesty: 86
    
    Zadejte mapu:
    #############
    # * # #
    # # #
    # # *#
    ###### ######
    Diamantu: 1
    Delka cesty: 12
    
    Zadejte mapu:
    ##### #######
    # #
    # #
    # *#
    ###### ######
    Nespravny vstup.
    
    Zadejte mapu:
    #############
    # #
    # a #
    # *#
    ###### ######
    Nespravny vstup.