ingångAlternativ för uppgifter om disciplinverkstad på dator. Workshop för att lösa uppgifterna för datorer: pedagogisk och metodisk manual
(Dokumentera)
n1.doc.
Utbildningsdepartementet av Ryska federationen
Novosibirsk State Technical University
Workshop på eum.
Algoritmer
Godkänd av universitetets redaktionella förlag
som ett undervisningsstöd
för studenter i FPPMI-kursen
(Direction 510200 - Tillämpad matematik
och informatik, special 351500 -
Matematisk avsättning och administration
informationssystem) Dagens utbildning
Novosibirsk
2004
T. A. Shaposhnikova, st. lärare
Granskare: S. . Pianocand. tehn vetenskap, röv.,
L.v. Tunincand. tehn Vetenskap, doc.
Arbete förberedd vid avdelningen för tillämpad matematik
Workshop på dator. Algoritmer
P 691 TUTORIAL / V.P. HITSENKO, TA Shaposhnikova. - Novosibirsk: Publishing House Nstu, 2004. - 112 s.
De viktigaste algoritmerna som studerades i kursen "Workshop på datorn" beaktas: algoritmer på grafer, kombinatoriska algoritmer, full av släckningsalgoritmer. Många exempel som illustrerar det teoretiska materialet demonteras.
UDC 004.421 + 519.1] (075.8)
Novosibirskstat
tekniska universitetet, 2004
innehållsförteckning
Kursen "Workshop på en dator" är den första grundläggande disciplinen bland programmerare discipliner. Det är omöjligt att behöva programmering utan kunskap om de viktigaste och mest kända algoritmerna. I denna handledning demonteras algoritmer i detalj, används i stor utsträckning för att lösa olika klasser av uppgifter: grundläggande algoritmer på grafer, algoritmen för fullständig släckning och metoder för dess förbättring (dynamiska programmeringsalgoritmer, "girig" algoritm, en metod för grenar och gränser), algoritmer för bildning av grundläggande kombinatoriska föremål.
Textboken är inte bara avsedd för studenter som studerar de inledande delarna av programmering, men också för dem som vill berika sina färdigheter för att designa algoritmer (i stället för "nästa cykel"). Ofta är skillnaden mellan dåliga och bra algoritmer större än mellan snabba och långsamma datorer. Till exempel vill vi sortera en rad en miljon nummer. Vad snabbare är att sortera det inlägg på en superdator (100 miljoner operationer per sekund) eller slå samman på hemdatorn (1 miljon operationer)? Samtidigt, om sorteringsinsatserna är skrivna på monteraren extremt ekonomiskt, för sortering n. siffror behöver ungefär 2 n. 2 operationer. Samtidigt skrivs fusionsalgoritmen utan särskild vård för effektivitet och kräver 50 · n.· Logga. n. operationer. I det första fallet, för att sortera 1 miljon nummer får vi:
för en superdator:
för en hemdator:
Detta visar att utvecklingen av effektiva algoritmer inte är mindre viktig än utvecklingen av snabb elektronik.
Utbildningshandboken kompletterar det föreläsnings- och praktiska materialet i disciplinen "Workshop på en dator" och är främst inriktad på att stödja självständigt arbete studenter när du utför rgr och siktpapper. Därför demonteras varje algoritm i handledningen på praktiskt exempelFör vissa implementeras programmeringsspråket (SI). Även för algoritmer ges för att bedöma deras komplexitet.
Algoritmer spelas in i form av "pseudokode" kommenterade i texten, tydligt presenterad i bilderna och i tabellerna.
1. Grundläggande algoritmer på grafer
Matematiska modeller av ett stort antal uppgifter kan beskrivas med avseende på teorin om grafer, därför är algoritmerna för studien av strukturen (bearbetning) av graferna, liksom sätten att deras presentation mycket viktiga.
1,1. Några grundläggande definitioner
Räkna (ne-orienterad graf) G.(V., E.) kallas en kombination av två uppsättningar, var V. - Finit, icke-tom uppsättning av element som heter Vertices, och E. - många oorderade par av olika delar av uppsättningen V. (Dessa par kallas kanter). Räkna som består av ett vertex kallas trivial.
Säg det kanten e. = (u., v.) Anslut toppar u. och v.. Kant e. och topp u. (såväl som e. och v.) Kallas incidentoch vertikaler u. och v. – intilliggande. Ribbor, incidenter av samma topp, kallas också intilliggande.
Graden av vertikaler - Detta är antalet kanter som inte handlar om det. Toppen av grafen, som har en grad av 0, kallas isoleratoch ha en examen 1, - hängande.
Om en E. är inte en uppsättning, men en uppsättning som innehåller flera identiska element, då kallas dessa element flera revbenoch graf - multigrill.
Om elementet i uppsättningen E. Kanske ett par identiska (inte olika) element V.Då ett sådant element E. kallad slinga. Pseudograf- Detta är ett diagram, som tillsammans med flera revben, tillåtna och loopar, och till och med några loopar vid ett vertex.
Räkningen kallas enkelOm något par hörn är anslutna med högst en kant och grafen inte har en slinga.
Rutt (sätt) - Detta är en alternerande sekvens
a \u003d V. 0 , e. 1 , V. 1 , E. 2 , ..., v n - 1 , e n,v n \u003db.
Vertikaler och kanter graf så att e. jag = (v. jag- 1 , v. jag), 1 ? jag ? n.. Det sägs att rutten förbinder vertikalerna a. och b. - ändarna av rutten. I en enkel kolumn kan rutten läggas till av noteringen bara dess hörn a. = v. 0 , v. 1 , …, v. n. = b. eller hans revben e. 1 , e. 2 , …, e. n. .
Ruten kallas kedjaOm alla hans revben är olika. Ruten kallas stängd, Om en v. 0 = v. n. .
Sluten kedja kallad cykel. Kedjan heter enkelOm det inte innehåller samma hörn. Enkel sluten kedja som heter enkel cykel.
Hamiltonisk kedja Det kallas en enkel kedja som innehåller alla grafiska hörn. Hamiltonisk cykel Det kallas en enkel cykel som innehåller alla grafiska hörn.
Vertex u. Ändåfrån vertexen v.Om det finns ett sätt från v. i u..
Stiglängd v. 0 , v. 1 , …, v. n. lika med antalet hans revben, d.v.s. n..
Distans Mellan de två hörn är längden på den kortaste vägen som ansluter dessa hörn.
Del av grafen G.(V., E.) - Det här är ett sådant graf G."(V.", E."), Vad V." V. och E." E..
Subgraf Räkna G. kallas samma del G." som tillsammans med något par hörn du,v. Innehåller och kant (u., v.) Om det är i G..
Tillägg Räkna G. kallad graf G." med samma uppsättning vertikaler som G., och två olika hörn är intill G." Då och bara när de är instabila i G.. Ribgrafer G. och G." tillsammans formulär full Graf. Räkningen kallas fullOm några två av sina hörn är intill.
Två grafer G.1 I. G.2 isomorfOm det finns en ömsesidigt entydig kartläggning av uppsättningen av grafen G.1 på uppsättningen av grafen G.2, bevarande av anknytning.
Räkningen kallas ansluten Om det för något par vertikor finns en fogbana. Den maximala anslutna subgrafen av ett obundet graf kallas komponent ansluten Detta diagram.
Om funktionen är angiven F.: V.?M., sedan uppsättningen M. kallas flera märken, och grafen - märkt. Om funktionen är angiven F.: E.?M.. kanterna av grafen tillskrivna vikt, då kallas grafen vägd.
Kanten på grafen kallas orienteradOm ordern av dess ändar är väsentlig. Räkna, alla revben är orienterade, kallas orienterad Räkna (eller orgraff). I det här fallet elementen i uppsättningen V. kallad knutpunkteroch uppsättningar av uppsättning E. – bågar. Båge (u., v.) leder från vertexen u. Till toppen v., Topp v. hänvisa till efterföljaren av vertikalerna u., men du -tidigare vertikaler v.. Koncept delar av orgraf, vägar, avstånd, enkel och sluten väg, cykel Definierad för orgrafen såväl som för grafen, men med hänsyn till arkens orientering.
Källa till orgraf. - Det här är ett vertex från vilket alla andra hörn kan uppnås. Stoke Orgraf. - Detta är ett vertex, som uppnår från alla andra hörn.
Träd Ett anslutet diagram utan cykler kallas.
Rotträd - Detta är en ansluten Orgraf utan cykler tillfredsställande villkor:
Det finns ett enda vertex som kallas roten där ingen båg inte ingår;
En båg leder till varje icke-SMEED-vertex.
1,2. Representation av grafer i dator
Presentationen i programmet för den matematiska modellen är en viktig del av programmeringen. Valet av bästa presentation bestäms av kraven. specifik uppgift. Känd olika metoder Representationer av grafer i datorns minne. De skiljer sig åt i mängden minne och hastighet av operationer över grafer. Det bör noteras att i många utmaningar på graferna är valet av presentation avgörande för effektiviteten av algoritmer. I fig. 1.1 för icke-orienterade ( a B C D) och orienterade ( d, e, w, s) Stocks visar olika visningar: b, E. - adjacency matris; b, J. - Matris av incident; g. - En lista över intilliggande icke-orienterad graf med den intilliggande placeringen av listelementen; z. - Lista över anknytningsorienterad graf med tillhörande plats för listobjektet.
1.2.1. Räkna intilliggande matris
Angränsningsmatrisen av den markerade grafen med n. Vertikerna kallas matrisen A \u003d [ a. i J. ], jag, j. = 1, 2, ..., n., vart i
Anslutningsmatrisen bestämmer unikt grafen (bild 1.1, a-b., d-e.). För ett oorienterat graf är matris A symmetrisk i förhållande till den huvudsakliga diagonalen. Antalet enheter i linjen är lika med graden av relevant vertex. Slingan i matrismatrisen kan representeras av ett motsvarande enhetsdiagonalt element. Kanterna kan representeras genom att matriselementet kan vara större än 1.
Fördelen med en sådan presentation är "direkt åtkomst" till kanterna av grafen, d.v.s. Det finns ett tillfälle i ett steg för att få ett svar på frågan "Finns kanten i kolumnen (x., y.) ? " För små grafer, när det finns tillräckligt med utrymme i minnet, är det ofta lättare att arbeta med arrangemanget. Nackdelen är att oavsett antal revben är mängden minne som är upptagen n. n. eller n. n./2 – n.Om du använder symmetri och lagrar endast den triangulära vyn av anknytningsmatrisen. Dessutom är varje element i matrisen tillräcklig för att presentera med en binär urladdning.
1.2.2. Country Incident Matrix
Incidensmatrisen kallas matrisen B \u003d [ b. i J. ], jag = 1, 2, ..., n., j. = 1, 2, ..., m. (Var n. - Antal vertikaler, och m. - Antalet kanter på grafen), vars rader motsvarar vertikalerna och kolumnerna - revbenen. Matriselementet i en icke-orienterad kolonn är:
Vid ett orienterat graf med n. vertikaler I. m. Arcs Elementet i incidensmatrisen är lika med:
Matrislinjerna motsvarar också vertikalerna, och kolumnerna är bågar.
Incidensmatrisen bestämmer unikt grafens struktur (bild 1.1, men–i, Dr.). I varje kolumn i matrisen B exakt två enheter. Det finns inga lika kolumner.
Nackdelen med denna presentation är det n. m. Minnesenheter, varav de flesta kommer att ockuperas av nollor. Inte alltid bekväm tillgång till information. Till exempel, för att svara på frågor "finns det en båge i kolumnen (x., y.) ? " Eller "till vilka toppar är revbenen från toppen x.? " Du kan behöva byta alla kolumner i matrisen.
1.2.3. Matrix vågar graf
Ett enkelt viktat diagram kan representeras av sina skalor W \u003d [ w. i J. ], var w. i J. - Vikt av ribben som ansluter vertikalerna jag, j. = 1,2, ..., m.. Vikten av obefintliga revben är lika med lika? eller 0 beroende på uppgiften. Matris av skalor är en enkel generalisering av anknytningsmatrisen.
1.2.4. Lista över kanter graf
När du beskriver diagrammet med listan över hans revben (eller för Arg-armlistan) representeras varje kant av ett par toppar. Denna uppfattning kan implementeras av två arrays (eller en tvådimensionell):
x \u003d.(x. 0 , X. 1 , ..., x m)och y \u003d (y 0 , y. 1 , ..., y m)
Var m. - Antal revben i diagrammet. Varje element i arrayen är ett vertexmärke, och jag-E. kanten på kanten kommer ut ur toppen x. jag och går in i toppen y. jag . Mängden minne är i det här fallet 2 m. minnesenheter. Inkomsten är ett stort antal steg som behövs för att få ett flertal vertikaler till vilka revbenen utförs från detta vertex.
1.2.5. Listor över intilliggande vertikaler i grafen
Diagrammet kan definitivt representeras av strukturen i anknytningen av dess hörn. Anslutningsstrukturen består av ADJ-listor [ x.] Toppen av grafen intill toppen x.. ADJ Lists [ x.] Sammanställd för varje vertexdiagram. Anslutningsstrukturen implementeras bekvämt av en uppsättning av n. (antal vertikor i kolumnen)
linjärt relaterade listor (1.1, a-g.). Varje lista innehåller 
men d.
| 1 | 2 | 3 | 4 | 5 | 1 | 2 | 3 | 4 | 5 |
|||
| 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 0 |
|
| 2 | 1 | 0 | 1 | 0 | 0 | 2 | 0 | 0 | 0 | 0 | 0 |
|
| 3 | 1 | 1 | 0 | 1 | 1 | 3 | 0 | 0 | 0 | 0 | 0 |
|
| 4 | 0 | 0 | 1 | 0 | 1 | 4 | 1 | 1 | 0 | 0 | 0 |
|
| 5 | 1 | 0 | 1 | 1 | 0 | 5 | 0 | 0 | 0 | 1 | 0 |
b. e.
| Ѕ | 1/3 | 1/5 | 2/3 | 3/4 | 3/5 | 4/5 | Ѕ | 1/3 | 4/1 | 4/2 | 5/4 |
|||
| 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | -1 | 0 | 0 |
|
| 2 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 2 | -1 | 0 | 0 | -1 | 0 |
|
| 3 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 3 | 0 | -1 | 0 | 0 | 0 |
|
| 4 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 4 | 0 | 0 | 1 | 1 | -1 |
|
| 5 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 5 | 0 | 0 | 0 | 0 | 1 |
i j.
g. z.
Fikon. 1.1
Vertikerna ligger intill det vertex som listan är sammanställd. Listan över angränsande vertikaler i diagrammet ger en kompakt representation för rarefied grafer - de där många revben har mycket mindre än uppsättningen av hörn. Nackdelen med denna presentation är: Om vi \u200b\u200bvill veta om det finns en revben i kolumnen ( x., y.), måste bläddra i det hela lista över adj [ x.] I Sök y.. Mängden minne som krävs är för orienterat n.+ m. och n.+2 m. för icke-orienterade grafer av minnesenheter, var n. - antalet vertikaler i grafen, och m. - Antalet kanter (bågar) i diagrammet. Om problemlösningsalgoritmen är baserad på att lägga till och ta bort vertikor från listor, implementeras lagring av intilliggande listor lämpligen med hjälp av den tillhörande angivna representationen (1,1, dn).
1,3. Land bypass
Att kringgå ett diagram är en viss systematisk passage av sina vertikaler (och / eller revben). Kommer med grafen, flyttar vi längs revbenen (bågarna) och vi passerar alla vertikaler. I det här fallet kan du få mycket information som är nödvändig för vidare bearbetning av grafen, därför kringgå grafen - grunden för många algoritmer för att studera strukturen i grafen. Om, när du besöker vertikalerna, ändras inte strukturen i grafen, de två huvudsakliga sätten att bypass är mest användbara: förbikoppling och runt bredden.
1.3.1. Bypass (eller sök) i djupet
Låt grafen uppsättas och fixa den ursprungliga vertexen s. (Källgrafen kan vara orienterad eller orienterad). Sökstrategin i djupet är att, från början av det ursprungliga vertexet, går djupt in i djupet, medan det är möjligt (det finns inga utgående revben) och återvända och leta efter ett annat sätt när det inte finns några sådana kanter. Detta görs tills alla hörn upptäcks kan uppnås från källan. Om de oupptäckta vertikorna kvarstår efter det, väljs en av dem (som den ursprungliga) och processen upprepas. Så gör vi tills vi hittar alla grafiska hörn.
När när vi söker upptäcker vi först toppen v.intill toppen u., Det är nödvändigt att markera denna händelse. Djupsökningsalgoritmen använder för denna färg (taggar) vertikaler. Var och en av topparna är första vita (inte reste). Detekteras blir det grått. När vertex är fullt bearbetat (dvs när listan över intilliggande toppar kommer att ses) blir den svart. Således, i färd med att söka från grafen, tilldelas en del till "Djupsökningsträdet" eller flera träd (djup sökskog), om sökningen upprepas från flera vertikaler. Varje topp faller på exakt ett sökträd i djup, så dessa träd skär inte. Dessutom kan du lägga extra etiketter på toppen av trädet: etiketten när toppen upptäcktes (blev grå) och etiketten när behandlingen av den intilliggande listan var klar u. verkhin (I. u. blev svart).
Algoritmen nedan använder grafvyn av de intilliggande hörn av adj [ u.]. För varje vertex u.
räkna lagrade dessutom sitt färgmärke [ u.] och dess föregångare pr [ u.]. Om det inte finns någon föregångare (till exempel om u. =
s. eller u.
Ännu inte upptäckt), sedan pr [ u.] = noll.. Dessutom, i D [ u.] I.
f [ u.] Ytterligare för u. Taggar: tidtaggar. I d [ u.] Tiden är inspelad när vertexen u. upptäcktes (och blev grå), och i f [ u.] Tiden skrivs när behandlingen av den intilliggande listan har slutförts u. Verkhin (I. u. blev svart). I tidsalgoritmen av tidstid d [ u.] I.
f [ u.] Dessa är heltal från 1 till 2 | V.|; För varje vertex u. Ojämlikhet: D [ u.] U]. Vertex u. Det kommer att vara vitt tills d [ u.], grå mellan d [ u.] och f [ u.] och svart efter f [ u.]. Algoritmen använder rekursion för att se alla intilliggande
u. Verkhin.
Söka_v_glubina ( G.)
2 för (varje vertex u. V.[G.])
4 PR [ u.] ?noll.;
7 för (varje vertex s. V.[G.])
Sök ( u.)
3 d [ u.]? Tid? Tid + 1;
4 för (var och en v. adj [ u.])
5 (om (Markera [ v.] \u003d Vit)
6 (PR [ v.] ?u.; Sök ( v.); }
9 f [ u.]? Tid? Tid + 1;
10 }
Algoritmen börjar med det faktum att först (linjer 2-5) alla hörn är målade i vitt (markerade som inte passerat); I PR-fältet placerat noll. (Medan vertikalerna inte har föregångare). Sedan är (sträng 6) inställd på den ursprungliga (noll) tiden (tidsvariabel - global variabel). För alla vertikaler (strängar 7-8), som fortfarande inte passeras (vit), kallas sökproceduren. Dessa vertikaler blir rötter av sökträdets djup.
Vid samtalssökning ( u.) Topp u. - Vit. I sökproceduren blir det omedelbart grå (linje 2). Dess detekteringstid (linje 3) är inmatad i d [ u.] (Tidräknaren innan detta ökade med en). Ses sedan (rader 4-7) intill u. vertikaler; Sökningsproceduren kallas för de som visar sig vara vita vid samtalets tid. Efter visning av alla relaterade u. Topptoppar u. Vi gör svart och skriver i f [ u.] Tiden för denna händelse.
Utbildningsdepartementet av Ryska federationen
Bashkir State University
Workshop på eum.
Uppgifter för C ++
Del 1
Kompilator:
Rykov V.I. Workshop på dator. Uppgifter för C ++ .. Del1. / Utgåva av Bashkir University. - Ufa 2006. - Nos. C.
Arbetet är avsett för programmeringsmetoden i C ++.
Innehåller initialt kodningsinformation, lanserings- och felsökningsprogram. Innehåller texter av uppgifter och i nödvändiga fall anvisningar om teknik för att lösa dem.
Metoder för programmering och kodning av program för varje uppgiftstyp presenteras i form av kompletta exempel.
Arbetet används när han utför laboratorium och praktiskt arbete Under disciplinen "Workshop på en dator".
1 Introduktion 5.
1.1 Första programmet 5
2 Certifikat av C ++ 5
2.1 Grundläggande datatyper 5
3 enkla datatyper 6
3.1 Modell Uppgiftsinmatningsoperatörer, Cykel. Bedömning av strukturer 6.
3.2 Struktur av pseudokod 7
3.3 Genomförande av kontrollstrukturerna 7
3.4 Modelluppgift heltal. Operatörer för, medan, om 8
4 Arrays 10.
4.1 Modelluppgift Sats av arrays. Maskin noll 10.
4.2 Modelluppgift inklusive hantering av strukturer 18
5 förfaranden och funktioner 20
5.1 Modell Uppgift Exempel Funktion 20
5.2 Överbelastningsfunktion 21
5.3 Överföring av parametrar för att fungera 21
5.4 Överföring av en arrayadress till funktion 22
6 vektorer och matris 24
6.1 Modelluppgift Multidimensional Arrays, inmatning från filen 24
7 Bearbetningssymbolisk information 29
7.1 Beslut Hitta det längsta symmetriska ordet i den angivna meningen 31
8 recursion 33.
8.1 Lösningsberäkning av faktorn för ett positivt nummer 33
8.2 Lösning Rekursiva funktioner. Arbeta med rader. 36.
8.3 Lösning för att bygga en syntaktisk analysator för begreppet konsol. 38.
9 Form av en rapport om laboratoriearbete 41
10 alternativ för laboratoriearbete 42
1. Introduktion
Programmering Initialinformation anges i Microsoft Visual C ++ - miljö- och felsökningsprogram.
1.1 Presentationsprogram
Programmet "2 + 3". I programmet efter inbjudan introduceras två siffror. För att ange varje nummer måste du ringa den på tangentbordet och tryck på ENTER-tangenten.
#Include "iostream.h"
char * rus (const char * text);
int Main (Int Argc, Char * Argv)
// costreturn 0;
char * rus (const char * text)
Workshop på dator, beslutsmetoder linjära system Och hitta dina egna värderingar, del 1, Bogachev K.YU., 1998
Den nuvarande ersättningen innehåller beskrivningar av algoritmer som erbjuds genomförandet av Mekanik och matematiska fakulteten för Moskva State University på datorn, men en workshop på datorn. " För alla algoritmer ges den nödvändiga teoretiska motiveringen, motsvarande beräknade relationer och rekommendationer, men deras praktiska genomförande på datorn (organisationen av beräkningsprocessen. Lagring av data och resulterar i datorns minne etc.).
Metoder för att lösa linjära system baserade på enhetliga transformationer av matriser.
Var och en av ovanstående metoder för att lösa linjära system kan representeras som en sekvens. elementära omvandlingar Matriser (se till exempel en sådan representation i §4 för Gauss-metoden). Var och en av transformationerna ges av någon matris P, så att användningen av denna beredning är ekvivalent med multiplicering (vänster) av den ursprungliga matrisen A på matrisen R. Således är varje steg av ovanstående algoritmer övergången från matrisen A till matrisen a \u003d ra. På antalet tillstånd av denna nya matris A \u003d RA är det möjligt att argumentera för att K (RA)< к(Р)к(А). Поэтому может случиться так. что в процессе проведения преобразований число обусловленности матрицы возрастает и на каждом шаге метод будет вносить все большую вычислительную погрешность. В результате может оказаться, что исходная матрица имела приемлемое число обусловленности, однако после нескольких шагов алгоритма она уже имеет слишком большое число обусловленности, так что последующие шаги алгоритма приведут к появлению очень большой вычислительной погрешности.
En idé uppstår för att välja matriserna i transformationsnumret. Så att antalet villkorlighet i matrisen i omvandlingsprocessen inte har ökat. LEMMA 1.5 indikerar oss ett exempel på sådana matriser: om matrisen av transformationen av Renheten (ortogonal i det reala fallet), i förhållande till spektralnormen till (RA) \u003d K (a).
Metoden för rotationer och reflektionsmetoden är algoritmerna för valet av enhetliga matriser av transformationer P, såsom som ett resultat av alla dessa transformationer, den ursprungliga matrisen A drivs av en triangulär form. Systemet med en triangulär matris löses sedan, t ex genom referensen av Gauss-metoden. Trots. Vad komplexiteten hos dessa metoder är större än gauss-metoden (respektive 3 och 2 gånger) var dessa metoder utbredd i beräkningspraxis på grund av deras hållbarhet av ackumulering av beräkningsfel.
Gratis nedladdning elektronisk bok I ett bekvämt format, titta och läs:
Ladda ner bokverkstaden på datorn, metoder för att lösa linjära system och hitta våra egna värderingar, del 1, Bogachev K.YU., 1998 - Fileskachat.com, snabb och gratis nedladdning.
- Workshop på dator, metoder för att lösa linjära system och hitta våra egna värderingar, del 2, BOGACHEV K.YU., 1998
- Matematik och design, klass 1, träningsmanual för allmänna utbildningsorganisationer, Volkova S.i., 2016
- Matematik, muntliga övningar, betyg 1, handledning för allmänna utbildningsorganisationer, Volkova S.i., 2016
Följande läroböcker och böcker.
Federal byrå för utbildning
Statlig utbildningsinstitution
Tomsk Polytechnic University
__________________________________________________________________
"Godkänna"
Direktör IDO
"____" ____________ 2007
Workshop på eum.
Arbetsprogram, Metodiska instruktioner och kontrolluppgifter För studenter av specialiteter 521600 (080100) "ekonomi", 060500 (080109) "Redovisning, analys och revision", 060700 (080103) "National Economics", 060800 (080502) "Ekonomi och ledning på företaget", 061100 (080507) "Management Management» Institutet för fjärrutbildning
Termin | |
Oberoende arbete, veckor | |
Uppgifter, veckor | |
Skriva rapport, klocka | |
Kontrollformer | |
UDC 681.3: 658.8
Workshop på dator: Arbetsprogram, metodiska instruktioner för studenter av specialiteter 521600 (080100) "ekonomi", 060500 (080109) "Redovisning, analys och revision", 060700 (080103) "National Economics", 060800 (080502) "Ekonomi och ledning På företaget, "061100 (080507)" Management Management ". Id / sost. . - Tomsk: ed. TPU, 2007. - 23 s.
Arbetsprogrammet, riktlinjer och kontrolluppgifter beaktas och rekommenderas för offentliggörandet av det metodiska seminariet från institutionen för ekonomi 12 april 2007, protokoll
Huvud Avdelning, professor, d. E. N .____________
anteckning
Arbetsprogram, metodiska instruktioner och kontrolluppgifter för produktionspraxis "Workshop på dator" är avsedda för studenter av specialiteter 521600 (080100) "ekonomi", 060500 (080109) "Redovisning, analys och revision", 060700 (080103) "National Economics" , 060800 (080502) "Ekonomi och ledning på företaget", 061100 (080507) "Förvaltning av organisationen". Utbildningspraxis hålls i den fjärde terminen på datorn i datorklassen för att tillhandahålla avdelningen eller filialens IDO, varaktigheten av övningen är 4 veckor.
Listan över de viktigaste frågorna som ska studeras i praktiken ges. Alternativen ges kontrolluppgifter. Metodiska instruktioner om deras genomförande ges.
1. Mål och mål för produktionspraxis
Produktionspraxismål
Utbildningspraxis "Workshop On Eum" är avsedd att konsolidera färdigheter om användningen av informationsteknik. Under sin passage känner studenterna bekanta med strukturen i det ekonomiska informationssystemet, med informationsresurser, Övergripande egenskap och klassificeringen av informationsteknik med Microsoft Office i sitt arbete. Öva är viktigt för att förbereda ekonombidrar till det framgångsrika genomförandet av det kontinuerliga användningsprogrammet dator i träning bearbeta. Särskild uppmärksamhet ägnas åt självständigt arbete och insamling av praktiska färdigheter med en bred användning av dator. För att säkra och verifiera arbetslivserfarenheten, innehåller verkstaden ytterligare uppgifter som studenterna måste uppfylla och lämna in resultaten i rapporten.
Uppgifter som utförs under träningspraxis
Under praxis utför studenterna uppgifter för att bearbeta ekonomisk information och ekonomiska beräkningar i Excel, skapa databaser och arbeta med dem i Access DBMS-miljön.
Passage av träningspraxis "Workshop på en dator" innehåller:
a) Oberoende arbete med undervisningsförmåner, riktlinjer;
b) utföra oberoende uppgifter och referensuppgifter
d) skydd av praxis.
Ämne 1. Informationsteknik
1. Information, teknik.
2. Ekonomiskt informationssystem.
3. Konceptuell modell av informationsteknik.
4. Informationsresurser och egenskaperna hos informationsteknik.
5. Klassificering av informationsteknik.
Ämne 2. Bearbetning av ekonomisk information i Excel
1. Förberedelse och redigering av ekonomisk information.
2. Enklaste beräkningar i Excel-tabeller.
3. Förberedelse av rapporter för affärsanalys.
Ämne 3. Finansiella beräkningar i Excel
1. Accrual räntor.
2. Analys av investeringar.
3. Prognoser värdena för tidsserierna.
Ämne 4. Åtkomstdatabashanteringssystem
1. Grundläggande begrepp av DBMS-åtkomst.
2. Åtkomstdatabas Arbetsmiljö.
3. Skapa tabeller tillgång.
4. Skapa de enklaste formerna och deras användning.
5. Sök efter information och skapa önskemål.
6. Skapa rapporter.
Under passage av övning utförs uppgifter på följande ämnen. Varje elev måste utföra en uppgift från de angivna uppgifterna för självständigt arbete. Uppgiftsnumret anger handboken. Träningspraxis hålls på personliga dator Och ligger i praktisk användning Datorstudenter programvaruprodukter (Microsoft Office.).
Ämne2 . Bearbetning av ekonomisk information i Excel
Förberedelse och redigering av ekonomisk information
1. Skapa ett bord där du behöver inkludera följande data på fordonsägare: efternamn, förnamn, patronymic, födelsedatum, adress, bilmärke, nummer statsregistrering, Datum för utsläpp, körsträcka (km). Tabellen måste innehålla data för minst tio ägare.
2. Skapa ett tabell som åtgärdar resultaten av sessionen och innehåller följande data: efternamn, förnamn, patronymic, datum för att överföra tentamen, namnet på ämnet, resultatet av leveransen (nummer). Sessionen var 4 examen.
3. Skapa en tabell som innehåller följande information om leverans av varor i livsmedelsgruppen: varornas namn, kostnaden per enhet (s.), Numret (st., Kg), namnet på företaget - Köparen, namnet, förnamn, återförsäljare, leveransdatum. Bordet måste innehålla minst tio typer av varor.
4. Skapa en tabell som innehåller information om tillgängligheten av varor från industrikoncernen (ljud- och videoutrustning) i företagets lager: Produktnamn, kostnaden för enheten (s.), Kvantitet (st), namnet på Tillverkaren, datumet för mottagandet. Bordet måste innehålla minst tio typer av varor.
Uppgifter för självständigt arbete
Ämne 3.Finansiella beräkningar i Excel
Under förutsättningarna för motsvarande oberoende uppgifter för avsnittet "Förberedelse och redigering av ekonomisk information", hitta:
1. Ålder av fordonsägare (TC), den totala kostnaden för alla fordon, fordonets genomsnittliga körsträcka, datumet för frågan om det nyaste och äldsta TS.
2. Mellanvärdet som erhållits på tentor, datumet för den första tentamen, är den sista tentamen.
3. Kostnaden för varor som genomförs av varje återförsäljare, datumet för den senaste leveransen, priset på de dyraste varorna, det totala värdet av de varor som tillhandahålls av bolaget.
4. Kostnaden för alla varor i lager, datum för mottagande av varorna, längre än alla lagrade i lageret, det totala antalet varor, priset på de dyraste varorna.
Ämne 4.DatabashanteringssystemTillgång
Uppgifter för självständigt arbete
Med åtkomst dbms skapa:
1. Databas med produktimplementering av en kommersiell organisation för den angivna perioden.
Fältnamn: Återförsäljare, leveransbelopp, mängd leveranser, leveransdatum, fakturanummer, klient.
Tabeller: Återförsäljare, klient.
2. Databasen för lagerräkning i en kommersiell organisation till det angivna datumet.
Fältnamn: Produktnamn, kvantitet, pris per enhet., Leverantör, Leveransdatum.
Tabeller: Varor, leverantörer.
Som en prototyp för uppgifter 1 och 2, ta någon känd kommersiell organisation av regionen, distriktet, staden. Data kan vara villkorliga.
I form av -handlare(Uppgift 1) och produktnamn (uppgift 2) Skapa knappar: Framåt på posterna, Tillbaka med inspelningar, Sök, Produktion.
4. Examination
4.1. Generella riktlinjer
För att slutföra studien av ekonomiska uppgifter i miljön porslinsprocessor Excel i slutet av produktionspraxis, måste du utföra kontrolluppgifter här för det utgivna alternativet.
Kontrolluppgifter och resultat av lösningen måste tas i en produktionsrapport.
Rapportdesignen görs i enlighet med de allmänna kraven i rapporteringen (se punkt 6.)
4,2. Metodiska instruktioner och alternativ för testuppgifter
Uppgiftsnummer 1.
Handelsföretaget i den aktuella månaden levererade produkter N. Kunder för ett totalt belopp S. R. med tillhandahållande av ett handelslån under en period av en månad under procentsatsen PI. Bestämma:
· Profitbolaget från detta lån;
· Ren vinst, förutsatt att inkomstskatten är 20%
· Resultat med en ökning av inflationen 1% per månad.
· Ändra utlåningsvillkor för inflationsnivån så att bolaget gör en vinst på 10%.
Värderingar S.1 , S.2 ,…, Sn. Satt godtyckligt så det.
Värderingar PI Ta från intervallet: 
Källdata för uppgiftsalternativen visas i tabell 1. Tabell 1
Alternativnummer | Belopp leverans | Antal klienter N. |
Exempel på utförande
Låt uppgifterna om den perfekta försäljningen specificeras i tabell 2
Tabell 2
Klient | Försäljningsbelopp, r. | Procent |
För att utföra uppgiften är det nödvändigt att utföra följande beräkningar:
Vinst \u003d 13350 p.
Vinstskatt \u003d 2670 p.
Nettoresultat \u003d 10680 p.
Nettoresultat med inflation 1% https://pandia.ru/text/78/464/images/image009_63.gif "Bredd \u003d" 351 "Höjd \u003d" 41 "\u003e \u003d 7,92%
Fikon. 4.1. Utför uppgiftsnummer 1 i Excel
Uppgiftsnummer 2.
Varu reserver köps av Enterprise 4 gånger under operationscykeln ( N.1, N.2, N.3, N.fyra). Aktier i början (början av resten) smink N.0 enheter. Lagerrörelse (kvantitet, pris, kostnad) på perioderna ges tabell. 3.
Bestämma:
· Commodity Stocks N. Under kvittoperioden och deras värde vid intäkter S.;
· Balans av varor R. I slutet av perioden
· Kostnaden för varans balans är tre metoder-vägda genomsnittliga, LIFO, FIFO, om 500 enheter av varor genomfördes.
· Kostnaden för varans balans är tre metoder-vägda, LIFO, FIFO, om 100 enheter av varor genomfördes.
Tabell 3.
Indikatorer | siffra | Pris per enhet., R. | Kostnad till priser ankomster, r. |
Återstoden (initial) | |||
Försäljning | |||
Återstoden (slutet) |
Källdata för uppgiftsalternativen visas i tabell 4.
Tabell 4.
Alternativnummer | N.0 | N.4 |
|||
annonser
Tävling 1: Python (i anytask)
Numpy bibliotek. Vektorisering av beräkningar.
Viktig artikel Dokumentation numpy:
Contest 2: numpy (i anytask)
Kodorganisation i Python.
Funktioner, moduler, klasser.
Tävling 3: Klasser (i anytask)
Metriska klassificeringsmetoder.
Diskussion om den första praktiska uppgiften.
Introduktion till bildbehandling.
Visualisering i python.
Förberedelse av textrapporter. TEX-system.
Undantagshantering. Menengers kontext. Testning.
Förberedelse av korta taler.
Iteratorer och generatorer.
Krav på rapporten om praktiska uppgifter
Rapporten måste vara ett självförsörjande dokument i pDF-formatförberedd i latexsystemet. Studenter som har slutfört rapporter om tidigare uppgifter kan passera rapporter i HTML eller PDF-format, förberedd med Jupyter Notebook.
Rapporten ska ge verifierande svar på följande frågor:
- Vilken kurs är uppgiften?
- Vilken uppgift är klar?
- Vem är uppgiften?
- Vad var uppdraget?
- Vad gjordes? Vad var inte gjort?
- Är de rätta svaren på alla teoretiska frågor av uppgiften?
- Har alla nödvändiga experiment utförts? Har du fått meningsfulla slutsatser?
- Är den kreativa delen av uppgiften?
- Har den student som andra använder? Om så är fallet, i vilken volym?
- Vilken litteratur använde studenten?
Några delar av en bra rapport:
- Rapportera volym: 5-20 sidor;
- Rapporten från rapporten upprepar inte den fullständiga uppgiftsformuleringen.
- Rapportstrukturen motsvarar uppgiftsposter.
- Vektor teckensnitt används;
- Grafer är ordentligt inredda;
- Skala för grafer är korrekt vald;
- På olika grafer visas resultaten för samma metoder i samma färg;
- Mellan platsen för graferna och de platser som nämns i texten om litet avstånd (på samma eller på nästa sida);
- Sidorna ska inte ha mycket tomt utrymme;
- I de flesta fall bör grafik / tabeller / pseudokoder av algoritmer inte ockupera större delen av en sida i rapporten.
- Alla nummer i texten / tabellerna är angivna med det önskade antalet meningsfulla siffror;
- I de flesta fall bör det inte finnas någon kod i rapporten.
- För alla experiment beskrivs den valda utformningen av experiment, såväl som slutsatser från de erhållna resultaten;