Leidsid 33 sarnast õppematerjali, mis on seotud failiga "Algoritmid ja andmestruktuurid eksamiks kordamine". Need materjalid aitavad sul teemat sügavamalt mõista.
algoritm, algoritmi, massiiv, graaf, algoritmid, andmestruktuuri, keerukus, andmestruktuurid, graafi, juur, pinu, node, loend, aadres, järjekord, järjekorra, juhu, sõlmed, tipus, viit, avaldis, puus, elementid, prev, operatsioonid, kuhja, viita, label, halvim, sisend, täisarv, tipud, järjestatud, realiseerimine, tippe, tsükkel, kuhi, loendur1. Algoritm. Algoritmi omadused. Keerukus. Ajalise keerukuse asümptoodiline hinnang. Erinevad keerukusklassid. Algoritm on mingi meetod probleemi lahendamiseks, mida saab realiseerida arvutiprogrammi abil. Algoritm peab olema määratud nii täpselt, et seda suudaks täita isegi arvuti. Täidetavaid samme ei tohi olla liiga palju. Algoritm peab lahendama ülesande õigesti erinevate sisendandmete korral. Algoritmi 5 olulist omadust: 1. Lõplikkus. Algoritmi töö peab lõppema peale lõpliku arvu sammude läbimist. 2. Määratletus. Algoritmi iga samm peab olema rangelt ja ühemõtteliselt määratud iga juhu jaoks. 3. Sisend. Algoritmil on sisendandmed, mille hulk võib olla null. 4. Väljund. Algoritmil on vastus(ed), millel on täpselt määratud seos sisendandmetega. 5. Efektiivsus (tulemuslikkus). Algoritm peab olema nii lihtne, et on lõpliku ajavahemiku jooksul pliiatsi ja
Esitus Eeldame, et iga tipu puhul on ajaga O(1) kättesaadav tema ülemus, kui see leidub (lisaks muidugi alluvatele). ajaga O(1) on teostatav viimase taseme viimase tipu likvideeri- mine ja uue tipu lisamine sinna. Kui kahendkuhja esitamiseks kasutada kompaktse kahendpuu esitust massiivina ja kasutada lisaks üht välja kirjete reaalse arvu hoidmiseks, siis need tingimused on täidetud, välja arvatud uue tipu lisamine juhul, kui massiiv on täis. 1 Kahendkuhjad 10 1.1 Operatsioonid Operatsioonid 1 Kahendkuhjad 11 1.1 Operatsioonid Lisamisülesanne Lisada antud kahendkuhja antud kirje. Sisend: kahendkuhi, kirje. 1 Kahendkuhjad 12 1.1 Operatsioonid Lahendus
Output of non-deterministic algorithm may be different for different runs with the same input data Mittedetermineeritud algoritmi tulemus samade lähteandmete korral võib erinevatel lahenduskordadel olla erinev. Tõene Partial algorithm terminates for any set of input data. Osaline algoritm peatub mistahes sisendandmete korral. Väär Average time complexity of binary search is O(log n). Kahendotsimise keskmine ajaline keerukus on O(log n). Tõene Worst case time complexity of merge sort is O(n). Ühildusmeetodi (merge sort) halvima juhu ajaline keerukus on O(n). Väär (it is O(n log n)) Sorting method is quick if it has average time complexity O(n lon n). Järjestamismeetod on kiire, kui selle keskmine ajaline keerukus on O(n log n). Tõene Jah, üldjuhul ei saa kiiremini Last element added to the stack is removed first. Magasini (stack) viimati lisatud element eemaldatakse esimesena. Tõene
Graafid Graaf koosneb tippudest(sõlmedest) ja neid ühendavatest kaartest. Kaarega võib ühendada suvalisi graafi tippe, sealhulgas on võimalik kaar samale tipule (iseendale). Iga kaar on määratud kahe tipuga. Orienteeritud graaf: kaared on järjestatud tipupaarid. Def: Graaf on paar (V,E), kus V on mittetühi hulk ning E hulk, mille elementideks on hulga V kaheelemendilised alamhulgad. Näide lk 47 (Palm) Tipu aste tipust väljuvate servade arv. Teoreem: Igas graafis on kõigi tippude astmete summa võrdne servade arvu kahekordsega. Järeldus: Igas graafis on paaritu astemga tippe paarisarv. Ahel graafis tippude järjend, kus iga kaks järjestikust tippu on servaga ühendatud (esimene ja viimane on otstipud vahepeal sisetipud).
SISUKORD SISUKORD......................................................................................................... 1 SISSEJUHATUS........................................................................................................ 2 1. Tarkvara arendusmeetodid ja tehnikad...............................................................3 2. Andmestruktuurid ja algoritmid..........................................................................4 2.1 ALGORITMI MÕISTE, STRUKTUUR JA ESITAMINE.............................................4 2.2 Erinevad andmestruktuurid ja nende omadused..............................................5 Programmeerimiskeelte tüübid.............................................................................. 8 3.1 PROGRAMMEERIMISE AJALUGU......................................................................8 3
PÄRNUMAA KUTSEHARIDUSKESKUS AA-09 Ermo Mägi PROGRAMMEERIMINE Referaat Juhendaja: Kristi Lorents Pärnu 2010 SISUKORD 1. Tarkvara arendusmeetodid ja tehnikad 3 1.1. Tarkvara 3 1.2. Tarkvaratehnika 3 1.3. Tarkvaratehnika raamistik 3 2. Andmebaaside struktuur ja algotrim 4 2.1. Algoritmi mõiste, struktuur ja esitamine 4 2.2. Erinevad andmestruktuurid ja nende omadused 5 3. Programmkeelte põhitüübid 7 3.1. Programmeerimise ajalugu 7 3.2. Programmeerimiskeelte põhitüübid 8 3.3. Programmeerimiskeele semantika ja süntaks 9 Page 2 1. Tarkvara arendusmeetodid ja tehnikad 1.1 TARKVARA - Arvutile antavad käsud
PÄRNUMAA KUTSEHARIDUSKESKUS AA-09 Ermo Mägi PROGRAMMEERIMINE Referaat Juhendaja: Kristi Lorents Pärnu 2010 SISUKORD 1. Tarkvara arendusmeetodid ja tehnikad 3 1.1. Tarkvara 3 1.2. Tarkvaratehnika 3 1.3. Tarkvaratehnika raamistik 3 2. Andmebaaside struktuur ja algotrim 4 2.1. Algoritmi mõiste, struktuur ja esitamine 4 2.2. Erinevad andmestruktuurid ja nende omadused 5 3. Programmkeelte põhitüübid 7 3.1. Programmeerimise ajalugu 7 3.2. Programmeerimiskeelte põhitüübid 8 3.3. Programmeerimiskeele semantika ja süntaks 9 Page 2 1. Tarkvara arendusmeetodid ja tehnikad 1.1 TARKVARA - Arvutile antavad käsud
1 , F 2 , . . . , F n on tõesed, on ka F 1 & F 2 & . . . & F n tõene, mistõttu valem G on samuti tõene. Teoreemid järeldumise ja samaväärsuse taandamisest ühe valemi omaduse kontrollimisele o Samaväärus F ↔ G o Järeldumine F → G 7 6. Literaal, täielik elementaarkonjunktsioon, täielik disjunktiivne normaalkuju, nende tõesuspiirkondade kirjeldused. TDNK olemasolu ja ühesus. TDNK-le teisendamise algoritm, tema etappidel kasutatavad samaväärsused. [1] Literaal o DEF: Literaaliks nimetatakse lausemuutujat või selle eitust, literaale loetakse positiivseks või negatiivseks vastavalt selelle, kas ta on puhas lausemuutuja või koos eitusega. N: A, B, ¬C Täielik elementaalkonjuktsioon o DEF: Muutujate X1, X2…, Xn täielikuks elementaarkonjunktsiooniks nimetatakse literaalide konjunktsiooni L1&L2&,..., &Ln Täielik disjunktiivne normaalkuju
2. Algoritmi ajaline keerukus (jätk) 2.1. Olulisemad mõisted ([J.Kiho] põhjal ) Def: Algoritmi ajalist keerukust väljendab funktsioon f, mis igale antud algoritmi järgi lahendatavale konkreetsele ülesandele andmemahuga n seab vastavusse ülesande lahendamisel sooritatavate algoritmi sammude arvu f(n). Üldiselt eeldatakse,et antud algoritmi alusel koostatud programmide töö aeg on ajalise keerukuse funktsiooni kordne c*f(n), kus c on konstant. Eriti oluline on algoritmi ajalist keerukust väljendava funktsiooni käitumine alg- andmete mahu piiramatul kasvamisel. Vastavat hinnangut nimetatakse asümptootiliseks hinnanguks. Lahendusaja suhtelist kasvu kirjeldab järgmine tabel: Programmi töö aeg kujul c*f(n) Lahendamise aja suhteline kasv f(25)/f(5) c1*log(n) 2 c2*n2 25 c3*n3 125 c4*2n 1048576
vaid 1 kindel element). Lõpmatut hulka nimetatakse loenduvaks, kui see on võrdvõimas naturaalarvude hulgaga. |H| on hulga võimsus ehk lõpliku hulga korral elementide arv hulgas. Lõpmatu hulga võimsus leitakse, seades tema elemendid bijektiivsesse vastavusse (üks- ühesesse) mõne tuntud võimsusega hulga (näiteks naturaalarvude hulga) elementidega. 4. Graafid. Puude esitused. Programmide esitamine puuna Mittejärjestatud ja mitteorienteeritud graaf on paar G = (A,R), kus A on tippude hulk ja kaarte hulk R on seos hulgal A. Graafi saab esitada paaride hulgana (A + R analüütiliselt, või predikaadina) või joonisena. Graafide võrdsus: Graafid G1 = (A1, R1) ja G1 = (A2, R2) on võrdsed ehk isomorfsed, kui leidub selline bijektiivne kujutus f: A1 A2 nii, et aR1b = f(a)R2f(b) Kui igale tipule a G1-st leidub tipp b G2-st, millele saab vastavusse seada samade tippude kaared ja kõik G2 tipud saavad ka kaetud.
..........................................................................14 Esimese teema kokkuvõte.........................................................................15 TEINE TEEMA: PÕHIMÕISTED. OMISTAMISLAUSE. .............................................16 Sissejuhatus...............................................................................................16 Programmeerimise mõisted.......................................................................16 Algoritm..................................................................................................16 Programmeerimiskeel.............................................................................17 Lause......................................................................................................18 Võtmesõna..............................................................................................18 Andmeobjekt........................................
Statistiline tõenäosus. Bernoulli suurte arvude seadus. [20]. Sõltuvad ja sõltumatud sündmused. Sündmuste summa ja korrutis. [21]. Täistõenäosuse valem. Bayesi reegel. [22]. Bernoulli valem (k katse õnnestumine katsete üldarvu n korral). [23]. Kord- ja algarvud. Algarvude jaotus, algarvulisuse kontroll, Eratosthenese sõel. [24]. Naturaalarvude kanooniline kuju. Suurim ühistegur ja vähim ühiskordne. [25]. Fermat teoreem. Pseudoalgarvud ja Carmichaeli arvud. [26]. Eukleidese algoritm. [27]. Lineaarsed diofantilised võrrandid. [28]. Täisarvude kongruentsid. Kongruentsi omadusi. [29]. Moodularitmeetika. [30]. Algarvulisuse Fermat` test. Miller-Rabini test. [31]. Graafid ja graafide omadused. Ahelad ja tsüklid graafis. [32]. Euleri graafid. Hamiltoni tsüklid. [33]. Puud. Puude omadused. [34]. Graafi vähima kaaluga aluspuud. [35]. Märgendatud puud. Puude esitamine arvuti mälus. [36]. Prüferi kood. Märgendatud puude loendamine. Cayley teoreem. [37]
JOptionPane.showInputDialog( null, "Sisesta midagi", "Andmete sisestamine", JOptionPane.QUESTION_MESSAGE); 7. Loeng Graafiline kasutajaliides JavaFX Struktuur Lava (Stage) Stseen (Scene) · konteiner, kuhu pannakse kõik erinevad elemendid (nähtavad ja nähtamatud) Stseenigraaf · stseeni loogilise struktuuri määramiseks Lava public void start(Stage primaryStage) { primaryStage.setTitle("Tiitel"); primaryStage.show(); Group juur = new Group(); Scene stseen1 = new Scene(juur); primaryStage.setScene(stseen1); } Graaf. Puu 1. tipp (node) 2. ülemus (parent) 3. alluv (child) 4. lehttipp e. leht (leaf node) - pole alluvaid 5. vahetipp (branch node) - on alluvaid 6. juurtipp e. juur (root node) - vahetipp, millel pole ülemust JavaFX 1. tipp (node) - abstraktse klassi Node mingi alamklassi isend 2. lehttipp e. leht (leaf node) - pole alluvaid 3
normaalkuju liikmetele. d. TDNK leidumine. Teoreem. Kui valem ei ole samaselt väär, siis tal leidub täielik disjunktiivne normaalkuju. e. Valemi TDNK jaoks on üheselt määratud seal esinevate täielike elementaarkonjunktsioonide hulk, see peab vastama esialgse valemi tõeväärtuse veerule. Seega on TDNK määratud ühesel kuni elementaarkonjunktsioonide järjestuse täpsuseni. f. TDNK-le teisendamise algoritm https://moodle.ut.ee/mod/url/view.php? id=78717 lk 29 30. 7) a. Boole'i funktsioonide esitamine lausearvutuse valemitega. https://moodle.ut.ee/mod/resource/view.php?id=125416 lk 14 16. 8) a. Lausearvutuse tehted on kasutusel tingimuste kirjapanemisel: a.i. Programmeerimiskeelte tingimuslausetes ja tsüklitingimuste a.ii. Päringukeeltes a.iii. Semantilises veebis (ontoloogiad) jne. 9) a. Tõestamise strateegiad. https://moodle.ut
......................................................................36 SUUNAMISLAUSE..............................................................................................................38 VALIKULAUSE...................................................................................................................39 ÜLESANDED....................................................................................................................... 39 STRUKTUURSED ANDMETÜÜBID: JADA, MASSIIV, KIRJE, FAIL. .............................39 ............................................................................................................................................... 39 Sissejuhatus ...........................................................................................................................39 Jada. Massiiv. Massiivi mõõtmed .........................................................................................40 Massiivi deklareerimine ..........
Puu on rekursiivne, seega ka enamik algoritme, mis temaga rakendada, on rekursiivsed. Kuid iga rekursiivset algoritmi saab esitada ka iteratiiselt, nagu enne juttugi oli. Kui juur välja jätta, siis kõigil teistel tipul on olemas ematipp ja ematippudel(parent) on omakorda tütartipud(child). Sama emaga tipud on õed(siblings). Kui meil on mitu puud, võime rääkida metsast(forest). Luline on rääkida veel puu kõrgusest. Puu jaguneb nivoodeks. Nivoode hulk on puu kõrgus. Mõnes õpikus võib näha ka teistsugust definitsiooni puu kõrguse kohta. Järjestatud puu, järjestamata puu. Kui on oluline, mis järjekorras mööda nivood vasakult paremale
2) kaotame kõik A → ε. Kui T → Aa ja A → ε, siis kustutame A → ε ja lisame T → a (sama mis T → εa) 3) kaotame kõik A → B. Kui T → A ja A → a, siis asendame T → A kohe produktsiooniga T → a. 4) sobitame muud reeglid, kasutades abi-mitteterminaale. Nt S→aTb muudame S→AC, lisame A→a, C→TB, B→b. 10 KV-keelte süntaksanalüüsi ülesanne. CKY-algoritm. Cocke-Kasami-Younge’i algoritmi abil saame teada, kas sõne kuulub KV keelde L. antud: KV grammatika Chomsky normaalkujul ja sõne w=w1…wn tulemus: accept, kui w selle grammatikaga keelde. Else, reject. tehakse püramiidikujuline tabel, mille alumisse ritta pannakse etteantud sõne kõik osad ja igasse tabeli lahtrisse kuidas neid kombinatsioone saada. Produktsiooni X → a korral pannakse “a saamise lahtrisse” X. Esimeses reas vaadatakse, kuidas saada 1 täht, teises reas, kuidas saada 2 tähte jne
KNK on elementaardisjunktsioon või elementaardisjunktsioonide konjunktsioon. 34. Esitada näitena avaldisi, mis on samaaegselt nii DNK kui ka KNK? , , ∨ 35. Mis on täielik disjunktiivne normaalkuju (TDNK)? TDNK on DNK, kus iga elementaarkonjunktsioon sisaldab kõiki funktsiooni muutujad. 36. Mis on täielik konjunktiivne normaalkuju (TKNK)? TKNK on KNK, kus iga elementaardisjunktsioon sisaldab kõiki funktsiooni muutujaid. 37. Mis on loogikaavaldise keerukus? Loogikaavaldise keerukus on temas sisalduvate algtermide arv. 38. Mis on minimaalne DNK (MDNK)? Mis on minimaalne KNK (MKNK)? MDNK (MKNK) on vähima keerukusega DNK (KNK) ehk sisaldab kõige vähem algterme. 39. Millisest loogikafunktsiooni piirkonnast tuleneb DNK? Millisest piirkonnas tuleneb KNK? DNK tuleneb 1depiirkonnast. KNK tuleneb 0depiirkonnast. 40. Kuidas kirjutatakse funktsiooni tõeväärtustabelist välja funktsiooni TDNK või TKNK? TDNK
ka järjendiks, kahemõõtmelist massiivi maatriksiks või tabeliks. Massiivi iseloomustavad seega: 1. massiivi nimi (täpsemalt massiivi identifitseeriv L-väärtus) 2. massiivi elemendi tüüp 3. massiivi indeksite arv ja indeksite tüübid 4. massiivi elementide arv (täpsemalt iga indeksi võimalike väärtuste hulk) 5. massiivi elementide väärtused Javas käsitletakse massiive ühemõõtmelistena, kahemõõtmeline massiiv on ühemõõtmeliste massiivide massiiv jne. Javas on massiivi indeksiks täisarv vahemikus 0 kuni massiivi pikkus miinus üks. Massiiv on massiivitüüpi muutuja (L-väärtus). Javas saab massiivi kirjeldada ilma massiivi elementide arvu fikseerimata. Elementide arv määratakse mälu reserveerimise käigus (see operatsioon on Javas massiivi kirjeldusest lahutatud). Javas kasutatakse massiivi elemendile viitamiseks indeksit, mis kirjutatakse massiivi nime järele kantsulgudesse
stiil ja programmide koostamise metoodika. On kokkulepped, millega vabatahtlikult kitsendatakse süntaktiliselt lubatud programmide hulka, et saavutada paremat loetavust inimese poolt (näit. "treppimine" programmi struktuuri väljatoomiseks, nimekokkulepped jne.). Algoritmidest ca 825 m.a.j. , Abu Ja'far Mohammed ibn Mûsâ al-Khowârizmî - reeglid aritmeetiliste operatsioonide sooritamiseks Algoritm on täpne (üheselt mõistetav) juhis antud ülesande lahendamiseks. Algoritm koosneb lõplikust arvust sammudest, millest igaüks on täidetav lõpliku aja jooksul lõplikke ressursse kasutades. Algoritmi rakendatakse teatavale lähteandmete komplektile (sisend) ning ta annab teatava resultaadi (väljund). Kui algoritm lõpetab töö (peatub) mistahes sisendi korral, siis nim. seda kõikjal määratud algoritmiks, vastasel juhul osaliseks algoritmiks. Kui algoritmi mistahes sammu täitmise järel on üheselt määratud, milline on järgmine samm, siis nim
Loogikafunktsioonid Algterm: avaldise koosseisu kuuluv loogikamuutuja, selle inversioon või konstant 1 või konstant 0 Argumentvektor: loogikamuutujate komplekt, mis esitab funktsiooni igale üksikule muutujale omistatavat väärtust 1 või 0. Muutujate väärtustamisel omandab ka loogikafunktsioon väärtuse Elementaardisjunktsioon: üksik algterm või algtermide disjunktsioon Elementaarkonjunktsioon: üksik algterm või algtermide konjunktsioon Loogikavalemi keerukus: loogikavalemi koosseisus olevate algtermide arv Loogikavalemi sügavus: kõige pikem tehete ahel, mis tuleb läbida, et saada loogikafunktsiooni väärtus, pmst aeg, mis funktsiooni lahendmiseks kulub Mitteoluline muutuja: muutuja, millele omistatud loogikaväärtus ei muuda kuidagi funktsiooni väärtust Tõeväärtustabel: loogikafunktsiooni esitusviis, mis loetleb esitatava funktsiooni väärtused tabelisse korrastatuna kõikide argumentvektorite puhul
elementi vastavusse seadnud. Nendeks on 0 ja 10. Nüüd hakkan juhindudes tabelist(alustan paremalt) lisama puule uusi tippe(ülemine rida) ja ühendama neid vastava alumisest reast ehk koodist pärit tipuga. Ehk esimesena lisan puule tipu 1 ning ühendan selle tipuga 0. Seejärel lisan tipu 9 ja ühendan selle tipuga 1. Ülejäänud tippudega käitun analoogiliselt. Tulemuseks saan järgmise puu: Vastus: ÜLESANNE 3. Võrdlen alguses mõlema graafi kõigi tippude astmeid. Märgin ära iga tipu astme. Diskreetne matemaatika II Kodused ülesanded 5 Olga Dalton 104493 IAPB21 Nii parem- kui vasakpoolsel graafil on olemas 2 tippu, mille aste on 3, ja 4 tippu, mille aste on 2.
ühisosa, täiend. Minimaalne Cantori normaalkuju on lihtsaim CNK. Täielik CNK on normaalkuju, mille iga avaldise osa sisaldab kõiki hulki. MCNKst saab TCNK kleepimisseaduse abil. Ristkorrutis on kahe hulga elemendite paaride koostamine. Järjestatud paare esitatakse loogsulgude vahel. Otseruut on hulga ristkorrutis iseendaga. Korteežid on järjestatud paarid, kolmikud, nelikud jne. Graafid: Graaf on objektide vaheliste seoste mudel. Graaf koosneb tippudest ja kaartest. Orienteeritud graafis saab ühest tipust teise minna ainult noolega suunatud kaare mööda. Orienteerimata graafil saab liikuda mistahes suunas kaarel. Tühi graaf on graaf, kus ühegi tipu vahel ei ole ühtegi kaart. Täielik graaf on graaf, kus iga tipp on seotud iga teise tipuga. Väljundaste on tipust väljuvad kaared.
Kõike, mis nende sümbolite vahele ei jää, loetakse HTML koodiks ja faili täitmisel väljastatakse selliselt nagu on. Kaks esimest varianti on kõige rohkem levinud stiil ja peamiselt kasutatakse selliseid märgendeid (selle kursuse jooksul kasutame ainult esimest varianti). Kommentaarid Näide esimesel real asub kommentaar Kirjuta valjundisse "Hello, World!". Kommentaare kasutatakse selleks, et teised inimesed saaksid koodist aru (eriti vajavad kommenteerimist teie poolt välja mõeldud algoritmid ja keeruline loogika). Mõnikord juhtub ka nii, et 2-3 kuu pärast ei oska ka koodi autor seletada kuidas tema programm töötab ja temal läheb suhteliselt palju aega selleks, et seda meelde tuletada. Aga kui kommentaarid on olemas piisab selleks ~5 minutist. Kommentaarid peavad kirjeldama loodava koodi eesmärke, kasutatud muutujaid, funktsioone ja algoritme. PHP parser ei loe teksti, mis asub kommentaaride vahele. Ta lihtsalt ignoreerib seda
1 0 0 1 0 1 1 1 0 0 1 0 G= 0 1 1 0 0 1 H= 1 1 0 0 0 1 1 1 0 0 0 1 1 0 1 0 0 1 0 0 1 1 1 0 0 1 0 1 1 0 Lahendus. Joonistades välja graafide täiendid, leiame, et graafi G täiend on tsükkel tippudega 1, 4, 5, 3, 2, 6 ning graafi H täiend on tsükkel tippudega 1, 2, 5, 4, 3, 6. Et kaks sama tippude arvuga tsüklit on isomorfsed, siis on ka graafid G ja H isomorfsed. Üks isomorfism on näiteks bijektsioon , mis teisendab graafi G tipud graafi H tippudeks järgmisel viisil: (1) = 1, (2) = 3, (3) = 4, (4) = 2, (5) = 5, (6) = 6. Materjal õpikus. Lk 5759 (graafide isomorfism). Lk 62, ülesanded 3741. Ülesanne 4
[Halbwachs]. Alati tuleb valida see keel, mis antud süsteemi module p1: kahealuseline graaf, kus on kahte tüüpi sõlmi: Sünkroonsed keeled kirjeldavad samaaegselt jaoks ............ Koha sõlmed (places): Hoiavad hajutatud
//keerab ringi
n=strlen(jutt); //n on stringi pikkus
m=n>>1;
for(i=0; i
Siit järeldub, et kas 11É või 11É( - 2), sest vastasel juhul ei saaks jäägiks 0-i. Seega on võrrandil kaks lahendit: # 0 (J 11) ja $ 2 (J 11), sest jäägi null annab - 2, seega peab $ ise andma jäägiks 2-e. Vastus: # 0 (J 11); $ 2 (J 11) ÜLESANNE 2. 25 + 41 = 1 Täisarvuliste kordajatega võrrandil I + I = I leiduvad täisarvulised lahendid parajasti siis, kui gcd(I, I)ÉI. Seega leian alguses kordajad u ja v nii, et 25 + 41 = gcd(25,41) Kasutan selleks Eukleidese algoritmi. gcd(25,41) = gcd(16,25) = gcd(9,16) = gcd(7,9) = gcd(2,7) = gcd(1,2) = 1 Kirjutan välja, kuidas jäägiga jagamine täpselt toimub. 41 = 25 1 + 16 16 = 41 - 25 1 25 = 16 1 + 9 9 = 25 - 16 1 = 25 - (41 - 25 1) = 25 - 41 + 25 1 = 2 25 - 41 16 = 9 1 + 7 7 = 16 - 9 1 = 41 - 25 1 - 2 25 + 41 = 2 41 - 3 25 9 = 7 1 + 2 2 = 9 - 7 1 = 2 25 - 41 - 2 41 + 3 25 = 5 25 - 3 41 7 = 2 3 + 1 1 = 7 - 2 3 = 2 41 - 3 25 - 15 25 + 9 41 = 11 41 - 18 25 Seega = -18 ja = 11
või elementaardisj-de konjunktsioon. Samaaegselt DNK ja KNK 𝑥1 ∨ 𝑥2 ∨ 𝑥3 ̅̅̅𝑥 𝑥1 2 ̅̅̅ 𝑥3 ̅̅̅ 𝑥2 TDNK on DNK, kus iga elementaarkonj. sisaldab F-ni kõiki muutujaid 𝑥𝑖 . TKNK on KNK, kus iga elementaardisj. sisaldab F-ni kõiki muutujaid 𝑥𝑖 . MDNK/MKNK on konkreetse F-ni väikseima keerukusega DNK/KNK. Keerukus 𝑳(𝒇) on tema koosseisus olevate algtermide arv. Loogikaalgebra põhiseosed Seosed konstantidega 0̅ = 1 1̅ = 0 0 ∗ 1 = 0 0 ∨ 1 = 1 𝑥 ∗ 0 = 0 𝑥 ∗ 1 = 𝑥 𝑥 ∗ 𝑥̅ = 0 𝑥 ∨ 0 = 𝑥 𝑥 ∨ 1 = 1 𝑥 ∨ 𝑥̅ = 1 Idempotentsus 𝑥∗𝑥 =𝑥 𝑥∨𝑥 =𝑥 ̅̅̅̅̅̅̅ DeMorgani seadused 𝑥 ∨ 𝑦 = 𝑥̅ ∧ 𝑦̅ 𝑥𝑦̅̅̅ = 𝑥̅ ∨ 𝑦̅
1. Üldine kommunikatsiooni mudel Üldises kommunikatsiooni mudelis on alati kaks poolt – saatja ja vastuvõtja. Terves süsteemis on meil sisuliselt viis osa: 1) allikas, mis genereerib andmeid 2) saatja, mis teisendab andmed transportimiseks sobivale kujule 3) edastussüsteem, mis transpordib signaalid ühest kohast teise 4) vastuvõtja, mis võtab signaali ja teisendab selle jälle adressaadi jaoks sobivale kujule 5) adressaat, kellele need allika poolt saadetud andmed on mõeldud kasutamiseks Allikas – edastaja – edastuskeskkond – vastuvõttev keskkond – sihtkoht Source (see, kes saadab) > transmitter (saatev seade) > transmissioon system (ü lekande sü steem) > receiver (vastuvõttev seade) > destination (see, kes vastu võtab). Nt: tö öjaam, arvuti > modem > telefoni tavavõrk > modem > vastuvõtja, server. 2. Kommunikatsioonisüsteemi ülesanded 1) Edastussüsteemi kasulikkus – seisneb selles, et teha transport saatja ja
1. nädal • Eksamiks: pead teadma suuruse-numbreid ja mida nad tähendavad: bitt, bait, kilobait, megabait jne; oskad selgitada, kuidas tähti kodeeritakse, mis on algoritm ja mis programm. Ajaloost: Kreeka loogikud, induktsioon, deduktsioon, süllogismid, lausearvutus (pead mh oskama tõeväärtustabelit koostada), Pascal, Leibniz, perfokaardid, kangasteljed, Babbage, Hollerith, colossus ja saksa krüptomasinad, Turing, Shannon, Zuse, esimesed programmeeritavad arvutid. Algoritm – täpne samm-sammuline, kuid mitte tingimata formaalne juhend millegi tegemiseks. Nt toiduretsept, juhend ruutvõrrandi lahendamiseks. Programm – formaalses, üheselt mõistetavas keeles kirja pandud algoritm. Arvutid suudavad täita ainult programme. Bitt – info mõõtmise ühik, tuleb mõistest binary digit – nö kahendarv kahe võimaliku väärtusega 0 ja 1. Saab näidata kahte võimalikku olekut. Nibble - 4 bitti.
[x 1, x 2, x3, x 4 ] 1 0 0 0 1 1 1 0 1 0 0 0 1 1 0 0 1 0 1 1 0 0 0 0 1 1 0 1 r1 = x1 + x3 + x 4 r2 = x1 + x2 + x3 r3 = x1 + x2 + x4 Muud kodeerimise algoritmid vastavustabeliga. Lubatud y1 = x1 y3 = x3 y2 = x2 y4 = x4 koodsõnad on kõik tekitava maatriksi read ja nende ridade summad paarikaupa, kolemkaupa, jne 33. Hammingi koodi dekodeerimine sündroomi abil.Konspekt 12. H (X )=1 0 1 1 1 0 0 Hammingi koodi kontrollmaatriks on: 1 1 1 0 0 1 0
BPDU – bridging protocol data unit. Andmeedastusformaat, spetsiaalsed andmekaadrid, et sillad saaksid paremini suhelda. Selle järgi saab aru, millised ühendused on lubatud ja millised mitte. Kui otsustatakse, et on vaja võrk ära konfigureerida, saadetakse vastav pakett kõikidele sildadele (hea on kasutada leviaadressi). Konfigureerimine võtab aega 30-50 sekundit, mille jooksul on võrk maas. Siis hakatakse joonistama graafi (puud). Lepitakse kokku, et üks sõlmedest on juur – kogu liiklus hakkab temast läbi käima. Näiteks valitakse sild, millel on kõige väiksem MAC-aadress ehk 31 kõige vanem MAC-aadress – kõige aeglasem võrk, sest see paneb alumise piiri võrgu kiirusele. Graafist valitakse kõige optimaalsem (lühem, kiirem) tee. Kui kaks teed on täpselt sama head, valitakse juhuslikult üks neist ning teine blokeeritakse ära. Blokeeritud
annaabi.ee 
