Home

Software Modelling and Architecture: Exercises

1. CHAPTER 2 UML EXERCISES 11 EXERCISES Software Modelling and Architecture L Liberti 2 2 Sequence diagrams In this section we shall present some easy examples of sequence diagrams These are similar to two dimensional Euclidean planes the horizontal axis marking labels for a finite set of actors and system components and the downward vertical axis representing time Actors and components are usually derived from a use case diagram Actions are split into messages going back and forth between actors and components Messages are represented by horizontal arrows There are two types of messages synchronous the initiator of the message is blocked until a return value is sent back from the message recipient and asynchronous the initiator is not blocked and any return value must be carried by a later message where the initiator is the recipient of the asynchronous message 2 2 1 The norm of a vector Consider the following algorithm for computing the norm of a vector Class Array pubis return the size of the array int size void return the index th component of the array double get int index double norm const Array amp myArray double theNorm 0 double c 0 for int index 0 index lt myArray size 1 index Y c myArray get index theNorm theNorm c c theNorm sqrt theNorm return theNorm Write down a sequence diagram illustrating the behaviour of the
2. Configuration File ReadConfiguration Project tables XML Site lap XML Tribe Map I 1 4 l PublishIncidence Statistics I U Li XSL Stylesheet HTML Output i 1 mov Get Time Graph Statistics Publish Time Graph Statistics Sn L L Figure 5 2 The transition state diagram for the user interface s FTP API to retrieve log file tails e ErrorStatus ReadConfiguration in String FileName out DBConnectionData theDB out int LogFileFormat out String LogURI out String UpdateInfoFileName Opens a text configuration file named FileName reads the following information name of the project DB server name DB user name DB password DB database name log file format uni CHAPTER 5 LOG ANALYSIS ARCHITECTURE 97 EXERCISES Software Modelling and Architecture L Liberti DBConnection tribes list Stringi connection Connection zones List String connection URL String lt onfiguration Config statement Statement selectedTribes String 3 configuration Configuration selectedZones int statisticsTypeirt open int time Span int closeQint accessTypeint execute Query result Result Set int incidence Statistics Hashtable Pair Tribe Zone double timegraph Statistics Hashtable DateTime double gt xml Statistics ML Document db Connection DB Connection dbServer String getTribes ListO int db Password String getZones List int file Name int get
3. private void initAttributes F3 endif COMPLEX_H DRE OOOO OR ok kk ook OO AGO a a kkk kkk Complex h cpp Copyright liberti Here you can write a license for your code some comments or any other information you want to have in your generated code To to this simply configure the headings directory in uml to point to a directory where you have your heading files or you can just replace the contents of this file with your own If you want to do this this file is located at usr share apps umbrello headings heading cpp gt Code Generators searches for heading files based on the file extension i e it will look for a file name ending in h to include in C header files and for a file name ending in java to include in all generated java code If you name the file heading lt extension gt Code Generator will always choose this file even if there are other files with the same extension in the directory If you name the file something else it must be the only one with that extension in the directory to guarantee that Code Generator will choose it you can use variables in your heading files which are replaced at generation time possible variables are author date time filename and filepath just write variable name This file was generated on date at time FROG GK ke kk ok ok AGA kk kk A a II I A a 212k 21 21 2 2 2 24 24 2 3 21 o ak 2k 2k a 2k 2k 2K 2k 2 ak k include Complex h Construct
4. P Potena V Cortellessa F Marinelli Automated selection of software components based on cost reliability tradeoff In V Gruhn and F Oquendo editors EWSA 2006 volume 4344 of LNCS pages 66 81 Springer Verlag 2006 85
5. subject to diffcolours fu in V v in V k in K 1 in K u vand k 1 w u k v 1 lt gamma u v linearization constraints subject to lini u in V v in V h in K kin K u v in E or v u in E w u h v k lt x u h subject to lin2 fu in V v in V b in K k in K u v in E or v u in E w u h v k lt x v k subject to lin3 fu in V v in V h in K k in K u v in E or v u in EJ w u h v k gt x u h x v k 1 The AMPL data file is as follows activity2 dat AMPL dat file from UML activity diagram 2 param n 16 param E c I mu i 15 3 1 2 15 111 2 9 111 Z 4 od 3 3 5 111 4 6 111 b 6 111 b 16 T12 6 O0 L11 T 3B iat T 46 12 89 10 111 8 16 112 11 16 3 2 1216 112 13 16 112 14 16 112 param lambda i 1 2 2 3 3 4 3 5 2 6 2 T 2 8 2 9 1 10 1 11 4 124 13 4 14 4 15 1 164 The AMPL run file is as follows file flexcolour clustering run model flexcolour_clustering mod data activity1 dat let kmax 4 maximum number of clusters option solver cplexstudent solve display y display x We solve the problem by issuing the command cat flexcolour_clustering run ampl We ask for at most 4 clusters let kmax 4 We obtain two clusters Cy 1 2 3 4 5 6 9 15 and C2 7 8 10 11 12 13 14 161 The diagram is now as in Fig 6 6 CHAPTER 6 A SEARCH ENGINE FOR PROJECTS 76 EXERCISES Software Modelling and Architecture
6. CHAPTER 2 UML EXERCISES 22 EXERCISES Software Modelling and Architecture L Liberti double Complex getImaginary 4 Oreturn double double Complex absoluteValue Oparam theComplexNumber void Complex add Complex theComplexNumber Oparam theComplexNumber void Complex subtract Complex theComplexNumber Oparam theComplexNumber void Complex multiplyBy Complex theComplexNumber F Oparam theComplexNumber void Complex divideBy Complex theComplexNumber void Complex initAttributes 4 m_realPart 0 m_imaginaryPart 0 y 2 4 2 Singly linked list Draw a class diagram representing a singly linked list 2 4 2 1 Solution The class diagram is given in Fig 2 12 It consists of a class with a single unidirectional association next with multiplicity 1 because a node of a singly linked list only has one neighbouring node the next node 2 4 3 Doubly linked list Draw a class diagram representing a doubly linked list CHAPTER 2 UML EXERCISES 23 EXERCISES Software Modelling and Architecture L Liberti l next sIList Figure 2 12 The class diagram of a singly linked list 2 4 3 1 Solution The class diagram is given in Fig 2 13 It consists of a class with a single bidirectional association with reference names previous and next both with multiplicity 1 because a doubly linked list has a previous
7. belongs in practice the function sqrt is found in a system library called 1ibm on UNIX systems but this is hardly part of the system at hand so it has no representation In such cases we depict the sqrt call as a self action of the norm actor onto itself This is shown in Fig 2 4 1 size Figure 2 4 The sequence diagram describing the computation of the norm of a vector 2 2 2 Displaying graphical objects Write a sequence diagram for a program that displays Fig 2 5 on the screen in the order left right CHAPTER 2 UML EXERCISES 13 EXERCISES Software Modelling and Architecture L Liberti Figure 2 5 2 2 2 1 Solution The sequence diagram in Fig 2 6 describes the required behaviour rectangle1 Composite ellipsel Ellipse Triangle rectangle2 Composite circlel Ellipse polygon1 Figure 2 6 The sequence diagram describing the printing of the drawing in Fig 2 5 2 2 3 Vending machine Draw a sequence diagram for the vending machine of Sect 2 1 2 2 2 3 1 Solution The sequence diagram in Fig 2 7 describes the required behaviour Notice the box shaped elements in the diagram these are used to endow the diagram with a modicum of logical representation alt signals an alternative an if else block opt signals an option an if block and loop a loop a for or while block CHAPTER 2 UML EXERCIS
8. kmax variables var x V binary var y u v in E gt 0 lt min max 0 mu u v k 1 max 0 k mu u v 1 model maximize densesubgraph sum u v in E I u v c u v ylu v sum v in V x v linearization constraints subject to lini u v in E ylu v lt x ul subject to lin2 u v in E ylu v lt x v subject to lin3 u v in E y u v gt x u x v 1 The AMPL data file is as follows activityl dat AMPL dat file from UML activity diagram 1 param n 15 param E 15 15 B E Li NN NNN NONANO PUNNNE BR w N PRRRRRRRRARRARARARARARARO a PRPRNONNNRERENNNNRRRRAR RR CHAPTER 6 A SEARCH ENGINE FOR PROJECTS 72 EXERCISES Software Modelling and Architecture L Liberti Ss 10 1 141 8 14 112 14 142 112 11113 1132 12 13 112 param lambda ONOOFRWNEF PAP PRP RPNNNNWWNH The AMPL run file is as follows file interface run model interface mod data activity1 dat let k 2 choose the colour option solver cplexstudent solve display y display x We solve the problem by issuing the command cat interface run ampl We find the interface subgraph H U F where U 5 7 11 12 13 14 and F all blue arcs We add a new vertex 16 representing the interface remove the arcs F and add the bidirected arcs F u 16 u U Since 16 is a database interface we assign it the database vertex colour blue The diagram evolves into
9. 0 leftChild TreeNodePtr rightChild TreeNodePtr getNumberOfChildren int getChildType childIndex int 0 theChildLevel int 0 int Pi leftChild rightChild datatype TreeNodePtr Figure 3 3 The UML class diagram for the TreeNode class case 6 sqrt nc 1 break case 10 number nc 0 break default break CHAPTER 3 MODELLING 29 EXERCISES Software Modelling and Architecture L Liberti return nc int TreeNode getChildType int childIndex int theChildLevel int ret 1 increase the level by one unit theChildLevel if childIndex 0 Y left child ret m leftChild getOperatorLabelO else if childIndex 1 xight child ret m_rightChild gt getOperatorLabel return ret Now consider the following main function in the file TreeNode_main cxx TreeNode_main cxx include lt iostream gt include TreeNode h int main int argc char argv int ret 0 expression tree t number number 2 TreeNode t Set peratorLabel 0 setLevel 0 setLeftChild new TreeNode setRightChild new TreeNode getLeftChild gt setOperatorLabel 10 getLeftChild gt setLevel 1 getRightChild gt setOperatorLabel 4 getRightChild gt setLevel 1 getRightChild gt setLeftChild new TreeNode getRightChild gt getLeftChild gt setOperatorLabel 10 g
10. 1 15 7 identify the foreground and background processes respectively If we consider two separate starting points for the two processes we can eliminate vertex 15 and all its adjacent arcs including 15 7 We then introduce a starting vertex labelled 15 since the old vertex 15 was reformulated out of the graph for the background process see Fig 6 7 The data flow arc 5 16 is crucial to the process interplay and cannot be eliminated It actually gives CHAPTER 6 A SEARCH ENGINE FOR PROJECTS TT EXERCISES Software Modelling and Architecture L Liberti Figure 6 7 Final diagram separating the processes the extent and the type of interconnection between the processes It also suggests where the two teams developing the different process will need to interact namely in the design of the database interface DBI vertex 16 more precisely the background process team will need to explain to the other team what data is made available by the interface and the foreground process team will need to require the appropriate data exchange formats and protocols The precise breakdown of each component into classes and methods is part of the technical architec ture 6 3 4 Technical architecture Propose a technical architecture detailing the inner working of each system component as well as the system as a whole This should include a class diagram and component APIs application programming interfaces 6 3 4 1 Solution In or
11. Fig 6 5 6 3 3 1 2 Synthesis Modules in a software architecture need to be clustered for at least two good reasons a to give an idea of the different independent or nearly independent streams in the archi tecture b to be able to assign separate sets of modules to separate teams One of the most common ways to bootstrap a software architecture design process is to construct the initial graph Go by means of a brainstorming session this will almost always give rise to a very tangled architecture Modules will roughly correspond to the requirements list and will be heavily interconnected Clustering these modules in an arbitrary way according to their perceived semantics may give rise to clusters whose degree of inter dependency is not minimal which will greatly complicate team interactions and possibly impair the whole development process In its most basic form the clustering procedure acts on a weighted undirected graph G V E c where w E R and outputs an assignment of vertices in V to a set of clusters such that the weights of inter cluster edges is minimized Such a problem is known in the combinatorial optimization literature as the GRAPH PARTITIONING PROBLEM GPP 1 9 4 2 Its formulation in terms of mathematical programming is as as follows given the weighted undirected graph G and an integer K lt V the problem consists of finding a partition of k subsets clusters of V minimizing the total weigh
12. java code If you name the file heading lt extension gt Code Generator will always choose this file even if there are other files with the same extension in the directory If you name the file something else it must be the only one with that extension in the directory to guarantee that Code Generator will choose it you can use variables in your heading files which are replaced at generation CHAPTER 2 UML EXERCISES 18 EXERCISES Software Modelling and Architecture L Liberti time possible variables are author date time filename and filepath just write variable_name This file was generated on date at time FRA A RI I RAI I A a a I IR a a ak 1 ooo 21 21 21 2 24 24 2 1 2k 2k 2 2 2k 2k 2k 2 2k 2k 2K ok 2 kak ifndef COMPLEX_H define COMPLEX_H include lt string gt class Complex class Complex public Constructors Destructors Empty Constructor Complex Empty Destructor virtual Complex Static public attributes public attributes public attribute accessor methods public attribute accessor methods Oparam theRealPart void setReal double theRealPart Oparam thelmaginaryPart void setImaginary double theImaginaryPart Oreturn double double getReal return double double getImaginary return double double absoluteValue C
13. loop for a very long time 2 talk p M get lost creep 3 flirt gt smooch 4 threaten_father_call but love you par 5 boy call par 5 daddy call 6 bash to pulp 6 get up from couch 6 bash_to_pulp 8 notice_vulnerable_pulp 7 ask judgment nah you did well he s a creep 9 feel mothering instinct 10 express love pee had enough fuck you 11 ask comfort all men are bastards Figure 2 8 The sequence diagram for the boy girl interactions state A to state B is represented by an arrow from A to B Two types of states start and end are such that there are no incoming arrows into start and no outgoing arrows from end states Arrows are labelled by the name of the activity that caused the state change Another type of state diagram called activity diagram emphasizes activities rather than states ac tivity names label the round cornered boxes and the state names label the arrows Apart from start and end nodes activity diagrams also have special test nodes represented by small rhombi 2 3 1 Vending machine Draw state and activity diagrams for the vending machine described in Sections 2 1 2 and 2 2 3 CHAPTER 2 UML EXERCISES 16 EXERCISES Software Modelling and Architecture 2 3 1
14. performs the query organizes the data in the specified output map e ErrorStatus GetByZoneStatistics in String 3 SelectedZones in TimeSpan theTimeSpan in AccessType in DBConnectionData theDB out Map Tribe Zone double Statistics Forms the SQL query to count how many accesses occurred during the specified timespan from each tribe to the selected zones performs the query organizes the data in the specified output map e ErrorStatus GetGlobalStatistics in TimeSpan theTimeSpan in AccessType in DBConnectionData theDB out Map Tribe Zone double Statistics Forms the SQL query to count how many accesses occurred during the specified timespan from each tribe to each zone performs the query organizes the data in the specified output map e ErrorStatus Get TimeGraphStatistics in String Tribe inString Zone in TimeSpan theTimeSpan in AccessType in DBConnectionData theDB out Map DateTime double Statistics Forms the SQL query to track the access of Tribe towards Zone versus time performs the query organizes the data in the specified output map e ErrorStatus PublishIncidenceStatistics in Map Tribe Zone double Statistics inString XSLVisualSpecFileName out TextBuffer XMLStatistics Transforms the incidence Statistics map into XML format uses the PHP PNG vector graphics API subset to produce a JPEG image of the desired graph in full colours reads the specified XSL visual specification file to produce an HTML output which also
15. they can be linearized exactly by replacing them by either 0 or VE according to their indices What this really means is that the reformulation Q obtained through a series of automatic reformulation steps is a semantically different formulation defined in terms of the following decision variables Vi lt n j H zij lif j I is assigned to and 0 otherwise and Vi lt n j Jik N Vi if j Jj is assigned to and there are k tests to be performed and 0 otherwise The AMPL implementation of the reformulation and consequent CPLEX solution is left as an exercise CHAPTER 4 MATHEMATICAL PROGRAMMING EXERCISES 50 Chapter 5 Log analysis architecture Some firms currently handle project management in an innovative way letting teams interact freely with each other whilst trying to induce different teams and people to converge towards the ultimate project goal In this liberal framework a continual assessment of team activity is paramount This can be obtained by performing an analysis of the amount of read and write access of each team to the various project documents Read and write document access is stored in the log files of the web server managing the project database Such firms therefore require a software package which reads the webserver log files and displays the relevant statistical analyses in visual form on a web interface Propose a detailed software architecture consistent with the definitions goals and
16. 1 L Liberti Solution The state diagram is given in Fig 2 9 and the activity diagram in Fig 2 10 e f ne operator switches on A yong for selection _ user selects good 3 e d displaying cost money cost P4 va x money cost L delivering good T M pu 3 money gt cost E l ERE operator switches off a ery y Figure 2 9 T he state diagram for the vending machine P change lt money x E p Br d deli h E ee eliver change self diagnostic tests machine ready lt o ees A s yes verify off control yes 0 d Ino Al wait for selection user selects product 2 Ro gt wait for money user inputs money aly ML change money cost check change 1 change 0 amp change gt 0 check for abort lt gt deliver good Figure 2 10 The activity diagram for the vending machine CHAPTER 2 UML EXERCISES 17 EXERCISES Software Modelling and Architecture L Liberti 2 4 Class diagrams In this section we present some elementary exercises on class diagrams 2 4 1 Complex number class Draw a class diagram for the single class Complex A Complex object has a private real and an imaginary part of type double and can perform addition subtraction multiplication and division by another complex number 2 4 1 1 Solution The class diagram for the Complex cla
17. 53 b 42 Details sia a a a e eee mo oe Rn ae ha Ros a eon Ros 55 6 A search engine for projects 61 6 1 Thesetting 42 hec ke Bee wd RR Reb A e Yo Oe P xu 61 02 hu aloHer 224222922 9992 42 v 26494999 dex d PRESS 62 6 2 L Kick O meeting srs ced an oar me RN REB Iq e um wee Re dna 62 6 2 2 Brainstorming meetings o koe or PR ege x vox 74 ox Poo RO mex OD 63 CONTENTS 4 EXERCISES Software Modelling and Architecture L Liberti 6 2 8 Formalization of a commercial offer 2222s 65 6 3 System planning 2442s 444 bb be bebe dee RUE E EY HER dedero ee hd P PES 67 6 3 1 Understanding T Sale s database structure oo a 67 6 3 2 Brainstorming Ideas proposal o e 69 6 3 3 Functional architecture les 70 6 3 4 Technical architecture co e moe e Ro o desa a 78 CONTENTS 5 EXERCISES Software Modelling and Architecture L Liberti CONTENTS 6 Chapter 1 Introduction This exercise book is meant to go with the course on Software Modelling given at cole Polytechnique by Prof D Krob the current course edition is 1st semester 2008 2009 code INF556 This book contains a set of exercises in software modelling and architecture 1 1 Structure of this book Software modelling and software architecture are concepts needed when planning complex software sys tems The book will focus on exercises to be carried out by means of the UML language some notions of optimization and a good deal o
18. E DB specific attributes vector lt Project gt P contains double getValue Project p 7 N vector lt Indicator gt I void scale void contains pointer of A vector lt Cluster gt C l y vector lt Clustering gt CL vector lt double gt D Cluster map lt pair lt pair lt int double gt pair lt int double gt gt bool gt M double vL vU vector lt Project gt map lt Cluster vector lt Cluster gt gt Gamma map lt double Clustering gt gamma int ID vector lt Indicator gt Early A int ClusteringID vector Indicator Late Ze z Bes A uses contains_pointer_of Pd contains pointer of see uses 1 A E Clustering ForegroundProcess M Be vector lt Cluster gt void Classify void pd A A int ID BackgroundProcess int IndicatorID Project pi i is Indicator vE ee em intiDistaneelD double Delta Clustering Clustering double d Nave s 3 A TELE vector lt Project gt intersection Cluster Cluster vector lt triplet lt int int int gt gt O d A i vector lt Project gt symmetricDifference Cluster Cluster double Delta Cluster Cluster void Cluster void void Match void Figure 6 9 The class diagram of the fore and background processes CHAPTER 6 A SEARCH ENGINE FOR PROJECTS EXERCISES Software Modelling and Architecture L Liberti CHAPTER 6 A SEARCH ENGINE FOR PROJECTS 84 Bibliography 1 2 R Battiti and A Ber
19. FileName reads the following information name of the project DB server name DB user name DB password DB database name XSL visual specification file name finally it closes the configuration file e ErrorStatus GetTribesList out List TribesList Queries the DB engine to obtain the zones list e ErrorStatus GetZonesList out List ZonesList Queries the DB engine to obtain the zones list CHAPTER 5 LOG ANALYSIS ARCHITECTURE 55 EXERCISES Software Modelling and Architecture L Liberti e ErrorStatus GetUserSpecifications outint StatisticsType outString 3 SelectedTribes out String 3 SelectedZones out TimeSpan theTimeSpan out int AccessType Gets the user specifications for the desired statistics from a web form The StatisticsType will denote per tribe per zone global or time graph If per tribe is selected SelectedTribes contains up to three names of meaningful tribes If per zone is selected SelectedZones contains up to three names of meaningful zones If time graph is selected SelectedTribes 0 and SelectedZones 0 will contain the relevant tribe zone pair In all cases AccessType will denote read access write access or both e ErrorStatus GetByTribeStatistics in String 3 SelectedTribes in TimeSpan theTimeSpan in AccessType in DBConnectionData theDB out Map Tribe Zone double Statistics Forms the SQL query to count how many accesses occurred during the specified timespan from the selected tribes to each zone
20. a per zone visual map BE 7 3 given a timespan 7 display a global visual map BE 7 4 given a timespan 7 and an edge e t z in B4 7 display a time graph of w e The per tribe and per zone visual maps can be extended to the per tribe pair per tribe triplet per zone pair per zone triplet cases 5 3 Requirements The technical requirements of the software can be subdivided into three main groups a user interaction b log file reading c computation and statistics 5 3 1 User interaction All user interaction input and output occurs via a web interface This will 1 configure the desired visual map or time graph according to user specification input action 2 delegate the necessary computation to an external agent a log database server and obtain the results process action 3 present the visual map or time graph in a suitable graphical format output action 5 3 2 Log file reading Log file data will be gathered at pre definite time intervals by a daemon parsed according to the log file format and stored in a database The daemon will 1 find the latest entries added the log files since last access input action 2 parse them according to the log file format process action 3 write them to suitable database tables output action 5 3 3 Computation and statistics Actually counting the relevant numbers and types of accesses will be carried out by a database engine This will receive a query
21. amount of team interaction needed 6 3 3 1 Solution The only available point of departure for this analysis is the sketched architecture design contained in our commercial offer which at this point should be used and expanded into a detailed and fully implementable software architecture The following components are apparent 1 Input web form IWF user inputs early indicator values concerning a new project 2 Output web form OWF user sees similar projects with relevant indicator values 3 Clustering engine CE given a set of objects and their pairwise distances perform a clustering minimizing the inter cluster distances 4 Clustering significance evaluator CSE Given a clustering does it match well to another given clustering 5 Classification CLS given an indicator for a given type of clustering find the cluster it belongs to in the given and all similar clusterings 6 Customers DB split in Commercial CDB Human resources HRDB Technical TDB data repositories 7 Clustering DB CLDB repository for existing clusterings Fig 6 4 shows a mixture of state architecture and deployment diagram based on this modularization Vertices are either logic anchors black actions yellow important data green and databases blue Arcs denote logic flow black or data flow blue CHAPTER 6 A SEARCH ENGINE FOR PROJECTS 70 EXERCISES Software Modelling and Architecture L Liberti Figure 6 4 Initial dia
22. and a next node previous i diList next 4 Figure 2 13 The class diagram of a doubly linked list 2 4 4 Binary tree Draw a class diagram representing a binary tree 2 4 4 1 Solution The class diagram is given in Fig 2 14 It consists of a class with a single bidirectional association with reference names child with multiplicity 2 and parent with multiplicity 1 because a binary tree has two children and one parent node parent 1 node 2 child Figure 2 14 The class diagram of a binary tree 2 4 5 n ary tree Draw a class diagram representing an n ary tree a tree with a variable number of children nodes CHAPTER 2 UML EXERCISES 24 EXERCISES Software Modelling and Architecture L Liberti 2 4 5 1 Solution The class diagram is given in Fig 2 15 It consists of a class with a single bidirectional association with reference names child with multiplicity and parent with multiplicity 1 because a binary tree has a variable number of children and one parent node T parent node ie Figure 2 15 The class diagram of an n ary tree 2 4 6 Vending machine Draw a class diagram for the vending machine described in Sect 2 1 2 and 2 2 3 2 4 6 1 Solution The class diagram is given in Fig 2 16 Client chooseGood theGood inputCoin theMoney confirm cancel retrieveGood th
23. ask the user the desired type of statistic per tribe per zone global time graph 4 ask the user the necessary input data timespan tribe s zone s tribe zone pair presenting lists of tribes zones and pairs to choose from CHAPTER 5 LOG ANALYSIS ARCHITECTURE 53 EXERCISES Software Modelling and Architecture L Liberti 5 form the database query according according to user specification 6 perform the database query 7 gather output statistics 8 form an XML representation of the statistics visualization 9 produce an output HTML other publishing formats Should any action fail in the events sequence the correct error recovering procedure is simply to abort the sequence display an error and return to Step 2 5 4 1 2 Log reading daemon The log reading daemon simply waits in the background and every so often reads the tail of the log files parses it and records the data in the log database server It needs to perform the following actions in the given order 1 configure its runtime parameters project name DB server information access log file format specification uniform resource identifiers URIs of log files update information file name 2 read log file sizes when last accessed from the update information file then for each log file listed 3 get tail of log file 4 parse records according to log file format to extract i requesting IP address ii requested document URL iii access
24. can be inferred by the directory name of the document URL contained in the zones table and the tribe name can be inferred by the IP address according to the tribes table 5 4 1 4 Project Interface This module is optional in the sense that a prototype may well work without it Its main function is to load incidence information of document URLs with zones and IP addresses with tribes on the database server This can be carried out either as a web interface drawing input from the user or as an executable program configured through a text file In both cases this interface should hook into the project specific database to build the document to zone and IP to tribe tables 5 4 2 Details The user interface and log reading daemon expose a C like API API entries are listed in the following format ReturnType FunctionName in InputArgument out OutputArgument In this document all functions return an integer error status this can be changed to using exceptions where applicable The TimeSpan type is simply a pair of date time records starting and ending times 5 4 2 1 User interface The user interface is going to be coded in PHP It is going to make use of several primitive PHP API subsets text file handling abstract DB connection and query XML XSL vector image creation e ErrorStatus ReadConfiguration in String FileName ouf DBConnectionData theDB out String XSLVisualSpecFileName It opens a text configuration file named
25. clusters with a small number of interconnections Such clusters may help break down the architecture in logically disconnected parts as system wide faults usually emerge from inter team lack of communication assigning such parts to different teams will minimize the chances of ending up with system wide faults The AMPL model is as follows flexcolour_clustering mod flexible coloured clustering colours on vertices AMPL model graph param n gt 1 integer set Y 1 n set E within V V edge weights param c E edge inclusions param I E vertex colours param lambda V param gamma u in V v in V u v if lambda u lambda v then 0 else 1 arc colours param mu E max number of clusters param kmax default n set K 1 kmax original problem variables var x V K binary linearization variables var w V K V K gt 0 lt 1 cluster existence variables var z K binary model minimize intercluster sum k in K 1 in K u v in E k 1 I u v clu v w u k v 1 sum k in K z k subject to assignment v in V sum k in K x v k 1 tt use ceil card V kmax 1 as RHS for balanced multi cluster cardinality subject to cardinality k in K sum v in V x v k lt ceil card V 2 CHAPTER 6 A SEARCH ENGINE FOR PROJECTS 75 EXERCISES Software Modelling and Architecture L Liberti subject to existence k in K sum v in V x v k gt z k
26. commercial offer became the true service that was eventually sold to the customer The management hope that the preliminary customer requirements contained in the public tender may be successfully matched with the stored initial requirements to draw some meaningful inference on how the project actually turned out in the past T Sale wants to enter into a contract with a smaller firm called VirtualClass to provide the following service which was expressed in very vague terms from one senior vice president of T Sale to VirtualClass sales department We want a sort of Google for starting projects We want to find all past projects which were similar at the initial stage and we want to know how they developed this should give us some idea of future development of the current project VirtualClass must estimate the cost and time required to complete this task and make T Sale a compet itive offer Should T Sale accept the offer VirtualClass will then have to actually plan and implement the system Note 1 The commercial offer needs to be drawn quickly The associated risks should be assessed It should be as close as possible to the delivered product 61 EXERCISES Software Modelling and Architecture L Liberti 2 In general the software engineering team should follow the V development process left branch for planning the system as shown in Fig 6 1 We shall limit the discussion to the leftmost branch of the V proc
27. displays the GIF JPEG image directly on the screen e ErrorStatus Publish TimeGraphStatistics in Map DateTime double Statistics in String XSLVisualSpecFileName out TextBuffer XMLStatistics Transforms the time graph Statistics map into XML format uses the PHP PNG vector graphics API subset to produce a PNG image of the desired graph in full colours transforms this to GIF or JPEG format reads the specified XSL visual specification file to produce an HTML output which also displays the GIF JPEG image directly on the screen Note to implementors some of the above functions are extensive pieces of coding They should be implemented by breaking them up into smaller protected functions The transition state diagram for the user interface is given in Fig 5 2 The class diagram is given in Fig 5 3 Note to implementors this class diagram is intended to give a semantic grouping of the required data and methods PHP is not necessarily best used in object oriented mode Should the choice fall on a procedural PHP development the class diagram should just be used for clarification and as general guidance 5 4 2 2 Log reading daemon The log file daemon is going to be coded in Java and will use the following primitive JAVA API subsets process timer handling text file handling abstract DB connection and query and possibly an advanced CHAPTER 5 LOG ANALYSIS ARCHITECTURE 56 EXERCISES Software Modelling and Architecture L Liberti
28. evaluate 66KB printresult 64KB evaluate evaluate 3KB e parse gettoken 0 1KB readexpr 1KB readprimitive gettoken 0 1KB variable 0 5KB number 0 2KB logarithm 1KB exponential 1KB sine 1KB cosine 1KB tangent 1KB minus 1KB readexpr 2KB e readpower power 2KB readprimitive 1KB e readterm readpower 2KB product 2KB fraction 2KB e readexpr readterm 2KB sum 2KB difference 2KB e gettoken ungettoken 0 1KB Each function call requires a bidirectional data exchange between the calling and the called function In order to guarantee data integrity during the function call we require that a checksum operation be performed on the data exchanged between the pair calling function called function Such pairs are called checksum pairs Since the checksum operation is costly in terms of CPU time we limit these operations so that no function may be involved in more than one checksum pair Naturally though we would like to maximize the total quantity of data undergoing a checksum 1 Formulate a mathematical program to solve the problem and solve the given instance with AMPL 2 Modify the model to ensure that readprimitive and readexpr are a checksum pair How does the solution change 4 3 1 Solution We represent each subroutine with a vertex in an undirected graph G V E For each u v V u v E if subroutine u calls subroutine v or vice versa Each edge i j E
29. h Mid 55 1A vn Tri 058 IWF input m v gt V j 6 h O output projects in Vor The required data structures are e project p class contains project attributes as defined in the T Sale DB e cluster list of projects e clustering 7 list of clusters e indicator v class contains methods to retrieve the indicator value given a project list of clustering distances D floating point numbers extremal values v v floating point numbers list of clusterings Wwa for this indicator relative to all distances d D methods to scale the indicator values and distances in D to the interval 0 1 e foreground process class contains list of early indicators v7 i lt m list of late indicators v j lt n matching information M array of booleans indexed on i lt m d DF j lt n D matching cluster information T maps clusters Yiak for varying k lt Kia to list of matching clusters 755 for varying h 1 Kj CHAPTER 6 A SEARCH ENGINE FOR PROJECTS 81 EXERCISES Software Modelling and Architecture L Liberti 6 3 4 1 5 The background process The data transformation model of the background process is as follows given an early indicator v i m a distance d Df a late indicator v j n and a distance 6 DF e if 4E is present in the CLDB database retrieve it else compute it and store it e if Yis is present
30. norm function 2 2 1 1 Solution In order to draw a sequence diagram we must first draw a use case diagram to help us identify system actors and actions In this case drawing a use case diagram is not all that simple we have a static piece of code Where is the system Who are the actors It turns out that the code has a class and a function outside the class In this setting the class is passive If no entity calls the class methods the class will not carry out any action of its own accord The class is therefore to be considered as a system rather than an actor The norm function on the other hand calls methods within the class and can thus be likened to an actor The actions are precisely those methods that are called by norm This arrangement is shown in Fig 2 3 Having identified actors actions and system we can now build the sequence diagram The norm function calls two Array methods size O and get O both of which block norm until a return value CHAPTER 2 UML EXERCISES 12 EXERCISES Software Modelling and Architecture L Liberti class Array Figure 2 3 The use case diagram of the norm Array system is received and can therefore be represented by asynchronous messages One other notable non local action carried out by norm is the call to the sqrt O method This is external to norm so it should be represented on the sequence diagram on the other hand we have no system component where sqrt
31. perform it and output the desired results 5 4 The software architecture According to the above requirements the overall software architecture is based on three main modules 1 user interface 2 log reading daemon CHAPTER 5 LOG ANALYSIS ARCHITECTURE 52 EXERCISES Software Modelling and Architecture L Liberti 3 log database server plus an optional added project interface module to configure project specific data into the log analysis database The overall software architecture is depicted in Fig 5 1 User Figure 5 1 The overall software architecture Project specific data are a a set of tribes possibly with hierarchical functional relationships ex pressed via a set of edges in the graph induced by the tribes b a set of zones possibly with semantic relationships expressed via a set of edges in the graph induced by the zones c a document to zone map here we refer to the documents listed in the project webserver log files d an IP to tribe map where IP is the IP address requesting documents from the project webserver log files 5 4 1 Summary 5 4 1 1 User interface This is the most complex module It needs to perform the following actions in the given order 1 configure its runtime parameters project name DB server information access XSL specification for statistics visualization output 2 get project specific list of tribes list of zones information from the log database server 3
32. picture Do not eschew backtracking correcting and re thinking current diagrams for this is one of the main system design values added by UML The student s approach should absolutely not be it took me three hours to put together the use case diagram and several days to compose sequence and state diagrams and now I m certainly NOT going to change it just because of one small inconsistency in the class diagram which is likely to require me to change the whole thing Usually one small inconsistency in the class diagram is all it takes for the whole system organization to fall apart The point is that without UML the error would have gone unnoticed and likely crept in the system implementation with catastrophic consequences 2 1 Use case diagrams In this section we give some examples of use case diagrams for various situations In general use case diagrams consists of a system represented by a large box actors represented by small stylized men out EXERCISES Software Modelling and Architecture L Liberti of the box actions represented by ellipses within the box and relations edges or arcs linking actors with actions actors with actors actions with actions 2 1 1 Simplified ATM machine Propose a use case diagram for an ATM machine for withdrawing cash Make the use case simple yet informative only include the major features 2 1 1 1 Solution The use case diagram is given in Fig 2 1 taken from 7 Fig 16 5 subsys
33. requirements listed in Sections 5 1 5 2 5 3 5 1 Definitions An actor is a person taking part in a project A tribe is a group of actors A document is an electronic document uploaded to a central database via a web interface Documents are grouped according to their semantical value according to a pre defined map which varies from project to project There are therefore various semantical zones or simply zones in each project a zone can be seen as a semantically related group of documents A visual map of document accesses concerning a set of tribes T and a set of zones Z is a bipartite graph BZ T Z E with edges weighted by a function w E N where an edge e t z exists if the tribe t has accessed documents in the zone z and w e is the number of accesses There may be different visual maps for read or write accesses and a union of the two is also envisaged A timespan is a time interval 7 s e where s is the starting time and e is the ending time Visual maps clearly depend on a given timespan and may therefore be denoted as BT T For each edge e E we can draw the coordinate time graph of w e changing in function of time denoted as we 7 in this case 5 2 Software goals The log scanning software overall user goals are 1 given a tribe t and a timespan 7 display a per tribe visual map Bey 7 51 EXERCISES Software Modelling and Architecture L Liberti 2 given a zone z and a timespan 7 display
34. that can be carried out by any client plus some more relative to his her added properties A dashed action action relation 4 B carrying a label include means that action B necessarily takes place within action A For example confirming that we want to buy a good necessarily includes retrieving that good although one might imagine a case of somebody using the machine in a train station and abandoning the good already paid for because the train is about to leave the train element is evi dently completely removed from the vending machine system and so need not be modelled A dashed action action relation A B carrying the label extends means that action A may take place within action B notice that this relation is reversed with respect to the include relation For example once we confirm we want to buy some good we necessarily retrieve the good but there may be no change to collect Vending machine E ose ___ choose beverage choose Z E gachide choose snack include N bh ae aa _ t xor eo Ee t zi i Ex N ancel A d assistance operator secondary DA client 1 E S A AN include EEES include MB b gt GE etrieve coins hw E m d p P d ES xor 75 021 _ 0 1 angry client Gro A Er fix machine cs Casi ce d extend we extend kick 2 e O Figure 2 2 The use case diagram of a vending machine
35. v aiyi i e Constraints 1 demand for each i x lt dj TOS gi 2 production 55 lt P 3 activation for each i xi Pqiyi 4 minimum batch for each i z gt liyi 4 2 1 2 AMPL model data run mixedproduction mod set PRODUCTS param days gt 0 param demand PRODUCTS gt 0 param price 4 PRODUCTS gt 0 param cost PRODUCTS gt 0 param quota PRODUCTS gt 0 param activ_cost i PRODUCTS gt 0 4 activation costs param min batch PRODUCTS gt 0 4 minimum batches var x PRODUCTS gt 0 quantity of product var y PRODUCTS gt 0 binary activation of production lines maximize revenue sum i in PRODUCTS price i cost i x i activ_cost i y i subject to requirement i in PRODUCTS x i lt demand i subject to production sum i in PRODUCTS x i quota i lt days subject to activation i in PRODUCTS x i lt days quota i ylil subject to batches i in PRODUCTS x i gt min batch i y il mixedproduction dat set PRODUCTS A1 A2 A3 param days 22 param demand price cost quota activ cost min batch A1 5300 124 73 30 500 170000 20 A2 4500 109 52 90 450 150000 20 A3 5400 115 65 40 550 100000 16 mixedproduction run CHAPTER 4 MATHEMATICAL PROGRAMMING EXERCISES 37 EXERCISES Software Modelling and Architecture L Liberti model mixedproduction mod data mixedproduction dat option solver cplexstu
36. 5 The class diagram for the log reading daemon CHAPTER 5 LOG ANALYSIS ARCHITECTURE 60 Chapter 6 A search engine for projects This large scale example comes from an actual industrial need An industry manager once mentioned to me how nice it would be to have a search engine for projects and how easy their work would be if they were able to come up with relevant past data at a glance whenever a decision on a new project has to be taken Although this example does not use UML although it does use some diagrams inspired to UML it employs some novel partially automatic graph reformulation techniques for manipulating the software architecture graph This example also shows how optimization techniques and mathematical programming are useful tools in software architecture 6 1 The setting T Sale is a large multinational firm which is often employed by national governments and other large in stitutions to provide very large scale services They will secure contracts by responding to the prospective customers public tenders with commercial offers that have to be competitive The upper management of T Sale noticed some inefficiencies in the way these commercial offers are put together in that very often the risk analysis are incorrect They decided that they could improve the situation by trying to use stored information about past projects More precisely T Sale keeps a detailed project database which allows one to see how an initial
37. 64 EXERCISES Software Modelling and Architecture L Liberti The Proogle system will require the following functionalities input output web user interface a computational engine for clustering according to a quantitative or qualitative indicator e a computational engine for evaluating clustering significance a database module for storing clusterings a computational engine for evaluating clustering compatibility e a database module for querying the stored clusterings Computational engines will require expertise in clustering techniques database modules should be sufficiently straightforward presenting output in a meaningful way will likely pose problems 6 2 3 Formalization of a commercial offer Aims of the meeting l write a document for internal use which gives a rough overview of the system functionalities and of the system breakdown into sub systems and interdependencies 2 write a document for internal use with projected sub system costs complexity and a rough risk assessment 3 write a commercial offer to be sent to T Sale with functionalities and the total cost CHAPTER 6 A SEARCH ENGINE FOR PROJECTS 65 EXERCISES Software Modelling and Architecture L Liberti 6 2 3 1 Meeting output Rough system breakdown System overview use case Input output Input web form Output web form Database modules Bill Project data Input early indicator values See releva
38. E la E i UT e PA o s 1 z T e i S y gt T d 2T I o as 3 Pid I N A x a p ec B N ae a 09 new project RENS d p s P Tes 7 a Ssa s 09 we 10 11 12 13 14 15 16 17 18 19 20 CHAPTER 6 A SEARCH ENGINE FOR PROJECTS Figure 6 2 Main idea for the Proogle project Functionality cluster projects according to a given quantitative qualitative indicator computa tional engine Functionality access the customer database database module How do we assess the quality of a clustering How clear cut is a clustering Functionality clustering significance evaluator computational engine How are the early late clusterings used later on Functionality record a clustering database module New projects must be classified according to early indicators how do we use the information given by the clusterings obtained with late indicators More in general how do we pick a set of significant late clustering which give the useful risk assessment information given an early clustering Functionality clustering compatibility evaluator computational engine Literature review on clustering How do we classify a new project according to the stored clusterings Functionality query clusterings for How do we present the output to the user Functionality output form user interface Name how about proogle the project google
39. ES 14 EXERCISES Software Modelling and Architecture L Liberti Customer VendingMachine Operator selectProduct code alt available loop 1 00 dorfect 1 return correct confirmOrCancel PE Tetum em 77777 isltemCorrect opt nat ipltemCorrect else return money else askRefill return Figure 2 7 The sequence diagram for the vending machine of Sect 2 1 2 2 2 4 Boy girl interaction A boy takes a fancy to a girl and wants her to become his girlfriend Draw a sequence diagram for their interactions to avoid any accusation of genderwise discrimination you can also reverse the roles of boy and girl 2 2 4 1 Solution The sequence diagram in Fig 2 8 illustrates the interactions between boy and girl Some other actors and system components have been added mostly for fun 2 3 State diagrams In this section we present some elementary exercises on state diagrams State diagrams are similar to state automata and are used to describe the logic behind any state change within a system or a system component States are represented by rounded corner boxes with a label the state name a change from CHAPTER 2 UML EXERCISES 15 Software Modelling and Architecture L Liberti e Q e girl s agony aunt friend on i other boy FN boy girl girl s father 1 see
40. G EXERCISES 42 EXERCISES Software Modelling and Architecture L Liberti The picture below is the solution represented on the graph 0 1 0 1 gettoken 66 p l Vis readexpr Jeee 64 SUO ET 1 4 4 Network Design Orange is the unique owner and handler of the telecom network in the figure below The costs on the links are proportional to the distances d i j between the nodes expressed in units of 10km Because of anti trust regulations Orange must delegate to SFR and Bouygtel two subnetworks each having at least two nodes with Orange handling the third part Orange therefore needs to design a backbone network to connect the three subnetworks Transforming an existing link into a backbone link costs c 25 euros km Formulate a mathematical program to minimize the cost of implementing a backbone connecting the three subnetworks and solve it with AMPL How does the solution change if Orange decides to partition its network in 4 subnetworks instead of 3 CHAPTER 4 MATHEMATICAL PROGRAMMING EXERCISES 43 EXERCISES Software Modelling and Architecture L Liberti 4 4 1 Solution Let G V E be the graph of the network The problem can be formalized as looking for the partition of V in three disjoint subsets Vi Va Va such that the sum of the backbone update cost are minimum on the edges having one adjacent vertex in a set of the partition and the other adjacent vertex in another set of t
41. HAPTER 2 UML EXERCISES 19 EXERCISES Software Modelling and Architecture L Liberti param theComplexNumber void add Complex theComplexNumber param theComplexNumber void subtract Complex theComplexNumber Oparam theComplexNumber void multiplyBy Complex theComplexNumber param theComplexNumber void divideBy Complex theComplexNumber protected Static protected attributes protected attributes public protected attribute accessor methods protected public protected attribute accessor methods protected private Static private attributes private attributes double m_realPart double m_imaginaryPart public private attribute accessor methods private public private attribute accessor methods ft Set the value of m realPart Oparam new var the new value of m realPart void setRealPart double new_var Get the value of m_realPart return the value of m_realPart CHAPTER 2 UML EXERCISES 20 EXERCISES Software Modelling and Architecture L Liberti double getRealPart Set the value of m imaginaryPart Oparam new var the new value of m imaginaryPart void setImaginaryPart double new var Get the value of m imaginaryPart Oreturn the value of m imaginaryPart double getImaginaryPart
42. L Liberti HRDB CLDB Figure 6 6 Diagram after clustering The architecture is composed of two main subsystems C1 C5 corresponding to two activity processes IWF CLS OWF performed by the user and CEGCSE DBI performed by the program that we may call respectively the foreground and background processes The foreground subsystem consists of three main components input classifier and output the background subsystem consists of a database sub subsystem with an interface and four databases and two main components clustering engine and clustering significance evaluator Very high level specifications may now be given as follows 1 IWF input indicator s and clustering distance s from the user 2 CLS classify new project according to given indicator s and distance s using a database of existing clusterings with cluster matching information 3 OWF output set of existing projects close to the new project w r t given indicator s 4 CE given a set of indicator values and an associated distance metric cluster the values pass the clustering to the DB interface for storage 5 CSE given two clusterings match them and verify their compatibility pass the matching informa tion to the DB interface for storage 6 DBI interface to customer and clustering DBs The two processes corresponding to C1 C5 are linked by arcs 15 7 a logical flow arc and 5 16 a data flow arc The logical path choices 1 15 2 and
43. LIX COLE POLYTECHNIQUE COLE POLYTECHNIQUE Software Modelling and Architecture Exercises Leo Liberti liberti lix polytechnique fr Last update October 22 2008 EXERCISES Software Modelling and Architecture L Liberti Contents 1 Introduction TI Structure of this book aor i gea awena cera aa a aaa 2 UML exercises 2 1 Use case dlagrams e os a a E a E OX wap EO e SS S 2 1 1 Simplified ATM machine so sacd adane 22s 2 12 Vending machine s koe x kc ede o he Ry ek he e dee Ro s 2 2 Sequence diagrams s e io 42H o HA RUE dO 3 ROY som ee a bee ole 2 2 1 The norm of a NECIO seu xo xe po mx EUR RUE RR A EUR EE Ux n 2 2 2 Displaying graphical objects sa 22e 2 2 2 Vending machine i 2 a ia RON veu Pee bee a mee v We 2 24 Boy gitl interaction e eoe d ROM e a Ee we Rd 2 3 State diagrams 2 3 1 Vending machine 6 s 44 xoa echo e o a Rho d 2 4 Class diagrams 24 1 Complex number Class s s ooo A RO X mang s BOR Rm uds 24 2 Sinely linked list casona e a Ru Eg gems 2 4 3 Doubly linked list 244 V y ek be RR UN ROC e E RS eR me VU x 2 14 Binary tre w eose g a ktm ouo MORIR OOo A a 3 PUE P 2 4 0 a Week 4m ae we bE SE RN 2 4 6 Vending machine amp 4444 44 kon eR RR Pea a a Ro a 3 Modelling 3 1 The vending machine revisited eee Sebel DOMO 2 wc a x OO RE ata Gb Reg 7E BES has 10 10 12 12 13 14 15 15 16 18 18 23 23 24 24 25 27 EXERCISES
44. Software Modelling and Architecture L Liberti 3 2 Mistakes in modelling a tree e 27 M To ipo ts 2 2 42 e a ds RS BG 31 4 Mathematical programming exercises 33 41 Museum guards i d e aora aaee e c Roe e a de RR TR AUR a 33 Al Solution 2220 kk eere mk m ee ee e e hoe Ro GR A A nS eo S ded s 34 42 Mixed production s 6o beo RU ox do 34666 AA 36 Au SOMON 22 3 ID ee ee GA OG SR deg RE Ren 36 4 3 Checksum ugs b m bGekSmILe xS a a a 38 4 3 1 O k ae 44 ah OS Se ee ae we ae Go M vun e eee ey E a ao Ghee 40 44 Network Design e e xov E A a ae UE DR al el de ea 43 ZI SOLULION es e a A E IA A AE 44 4 5 Error correcting c d s 0 ts dekh bho a a d det RA d on a AT 4 5 l Solution a 2 2 e a REED m RU EUROS Remo pen dee at Sod P ul 47 4 6 Selection of software components 2l a rs 48 Z6 l jSOIUbIOD 2 escri a dup dU ev now xk Rhe xem eK d 48 5 Log analysis architecture 51 Hal Definitions i d soe eek m peXom b em ow Arda iaa 3 o5 51 5 2 DOLLWATO Coals 2 ose 454 5K eo Ba eee A e dre a c ERU he d e mu 51 0 9 Requirements s e mo Rx ed BRE a eed d Y AD Wi ge Dg 52 D 9 l User interaction s saf mangs g Gon eho eb ee a ee V RU er EE ROSA e He ed 52 Dia Logfile reading ow RUE PW ex RR a FOEDE oues 52 5 3 3 Computation and statistics cesare irna i kiea nadia da a 52 5 4 The software architecture ps sas sdi aeaa K EE Loe k bte i PUn a AA So 52 5 4 1 Summary es ist ar sorak dayi AA aa due
45. UserSpecificatior int xsIFile Name String 2 get By Tribes Statistics int db Database String get By Zones Statistics int file Handle FilelO get Global Statistics int dbUser String get Time Graph Statistica Jint db Brand int publish Incidence Statistica Yint read Configuration Filet tint publish Time Graph StatisticsQ int Figure 5 3 The class diagram for the user interface form resource identifiers URIs of log files update information file name finally it closes the configuration file e ErrorStatus ReadUpdatelInfo in String UpdateInfoFileName inString LogURI outlong LogSize Opens the update information file reads a file read up to size for each given log file URI closes the file e ErrorStatus SaveUpdateInfo in String UpdateInfoFileName inString LogURI in long LogSize Writes a new update information file with the current log sizes closes the file e ErrorStatus ReadLogFileTail in String LogURI in long LogSize out TextBuffer theTail Uses a network or filesystem transfer method to retrieve the last filesize LogURI LogSize bytes of the log file LogURI e ErrorStatus ParseLogData in TextBuffer theTail in int LogSize in int LogFileFormat out DBTable UpdatedLogData out UpdatedLogSize Calls a lower level parsing driver according to LogFileFormat this driver must parse theTail iden tify the relevant fields and organize them into a memory representation of a DB table U
46. al relations among system components class diagrams are used to represent the system organization into blocks each of which includes data and actions relative to those data Of these diagrams the former two use case and sequence diagrams are not considered as formal languages but rather as an aid tool to thought and system organization The latter state and class can be considered as formal languages although really compilers exist mostly just for class diagrams taking a graphical description and outputting corresponding C or Java header files Students should therefore aim at clarity for what concerns use case and sequence diagram and at formal rigourousness for state and especially class diagrams UML diagrams can be used as a tool in system design One usually starts with the simplest type of diagram i e use case diagrams to make sure the understanding of actors and actions of the system is clear One then proceeds to sequence diagrams adding a temporal scale to the system events Next come state diagrams and finally the closest software representation of the system the class diagram there are more than four types of UML diagrams but in this book we shall limit ourselves to these four types Each step is likely to underline system design errors in previous steps so that the whole process is a continuous backtrack through use case sequence state and class diagrams so that in the end the whole diagram set presents a consistent system
47. atch each early indicator clustering to at least one late indicator clustering Given two matching clusterings Yud Yvs we must now find indices h Kua and k K s such that Yudh and wsk are as close as possible We extend the dissimilarity definition A to clusters as follows Altuan sr 4 8 GP 9 yuan var PEYudhNYv k where AAB AU B x AN B is the symmetric difference of two sets A B This definition is justified by the fact that the difference in normalized indicator value for a project p in yuan Ayvsx is simply the diameter of the corresponding normalized interval 0 1 namely 1 and that 1 1 With this extended definition we can compute A Yudn Yor for each possible pair h k and determine a pair of closest clusters We denote the set of clusters 5 in Yws closest to a given cluster Yuan by Dl yuan Yui 6 3 4 1 4 The foreground process The data transformation model of the foreground process is as follows we are given a new project 7 we select an early indicator v7 compute w vP r select a meaningful distance d DF find the corresponding clustering y and the cluster y such that w Tax We then find a late indicator clustering Yi where j n and Di such that M vi 55 1 and the corresponding closest clusters Ven l 4E vis The formal data flow description of the foreground process is CLDB CLS Pd a dus vi n Liar gt A OWF gt O G 5
48. back in the mathematical expression string buffer e readexprO reads the operators with precedence 4 lowest e readtermO reads the operators with precedence 3 e readpower reads the operators with precedence 2 power e readprimitive reads the operators of precedence 1 functions expressions in brackets fa Nb e sum term a term b make a tree e difference term a term b make a tree 4 Z a e product term a term b make a tree A d a e fraction term a term b make a tree EC e power term a term b make a tree 4 i i e minus term a make a tree a e logarithm term a make a tree make a tree log a e exponential term a make a tree make a tree exp gt a e sine term a make a tree make a tree sin a e cosine term a make a tree make a tree cos a e tangent term a make a tree make a tree tan a e variable var x make a leaf node z e number double d make a leaf node d e readdata reads a table of variable values from a file e evaluate computes the value of the binary tree when substituting each variable with the cor responding value e printresult print the results For each function we give the list of called functions and the quantity of data to be passed during the call CHAPTER 4 MATHEMATICAL PROGRAMMING EXERCISES 39 EXERCISES Software Modelling and Architecture L Liberti main readdata 64KB parse 2KB
49. d by 2 add the following constraints to the formulation V i j E BR hAkeK wht gt apyt aje 1 if tin 27 1 wh 1 4 5 V jbe BhAKEK wht tin if in 0 wh 0 4 6 1 J V jje E hzZkeK wh lt ay if oj 0 wi 0 IA Constraints 4 5 4 7 are a way to express the equation wk ZinTjr i e the condition vertex i assigned to subnetwork h and vertex j assigned to subnetwork k without introducing quadratic products in the formulation The resulting formulation is a MILP whose continuous relaxation is a Linear Programming problem hence it is convex which implies that each local optimum is also global so it can be safely used to compute lower bounds in BB algorithms such as that implemented in CPLEX CHAPTER 4 MATHEMATICAL PROGRAMMING EXERCISES 44 EXERCISES Software Modelling and Architecture L Liberti 4 4 1 2 AMPL model data run network design param n gt 0 integer param k gt 1 integer set V 1 n set K 1 k param c gt 0 param m gt 0 integer param d V V gt 0 default 0 var x V K binary var w V V K K gt 0 lt 1 minimize cost sum h in K lin K i in V j inV h 1 and i lt j and dli jl gt 0 c d i j w i j h 1 subject to assignment i in V sumth in K x i h 1 subject to cardinality h in K sum i in V x i h gt m subject to linearization h in K 1 in K i in V j in V h 1 and i lt j and dli j gt O w i j h
50. date time iv success failure v access type read write 5 store those data to the log database server Care must be taken to read a whole number of records in Step 3 as the tail of a file is defined on the amount of bytes last read This depends on the operating system so it cannot be enforced a priori One possible way around is to count the bytes used during data parsing and add those bytes the file size stored in the update information file Should any action fail in the events sequence the correct error recovering procedure is to abort the daemon and notify a system administrator immediately 5 4 1 3 Log database server The log database server is going to perform the necessary computation on the stored relevant informa tion It needs to store the following information 1 project specific information tribes table tribe name associated IP address pool e zones table zone name associated directory name in web site map actors tribes incidence information optional documents zones incidence information optional CHAPTER 5 LOG ANALYSIS ARCHITECTURE 54 EXERCISES Software Modelling and Architecture L Liberti e hierarchical functional tribes actors relationthips optional e semantic zones relationships optional 2 log information table e requesting IP address e tribe name e requested document URL e zone name e access date time e type of access read write Note that the zone name
51. dent solve display x display y 4 2 1 3 CPLEX solution CPLEX 7 1 0 optimal integer solution objective 220690 5 MIP simplex iterations O branch and bound nodes ampl display x x A1 0 A2 4500 A3 5400 ampl display y y A1 0 A2 1 A3 1 4 3 Checksum An expression parser is a program that reads mathematical expressions input by the user as strings and evaluates their values on a set of variable values This is done by representing the mathematical expression as a directed binary tree The leaf nodes represent variables or constants the other nodes represent binary or unary operators such as arithmetic power or transcendental sin cos tan log exp operators The unary operators are represented by a node with only one arc in its outgoing star whereas the binary operators have two arcs The figure below is the binary expression tree for x 2 e ae CHAPTER 4 MATHEMATICAL PROGRAMMING EXERCISES 38 EXERCISES Software Modelling and Architecture L Liberti The expression parser consists of several subroutines e main the program entry point e parse reads the string containing the mathematical expression and transforms it into a binary expression tree e gettoken returns and deletes the next semantic token variable constant operator brackets from the mathematical expression string buffer e ungettoken pushes the current semantic token
52. der to build a class diagram and the APIs we need to know how input data are transformed into the output data and exactly which data is passed from one component to another As the background process is in some way a server to the foreground one we shall model the latter first top down approach CHAPTER 6 A SEARCH ENGINE FOR PROJECTS 78 EXERCISES Software Modelling and Architecture L Liberti Informally the data flow for the foreground process is as follows s IWF CLDB input early indicator indicator value distance value gt CLS corresponding early clustering cluster gt matching late clustering s cluster s SwE output projects in identified cluster s In order for the foreground process data flow to make any sense the CLDB database must contain all the clusterings relative to the given early indicator value and distance and the CLS component must be able to match early and late clusterings and to draw the appropriate close clusters from the matched clusterings The background process must therefore supply the necessary information Recall that the foreground process is ran by each user and so should be as fast as possible It is therefore necessary to delegate most of the computational work to the background process all data transformation should draw from information that was pre computed by the background process In particular finding a matching late clustering sh
53. development time Tij the average time required to perform a test case p is the probability that the instance is faulty and b the testability of the 7 th purpose built component for slot i e Variables 1 Let rj 1 if component j J U J is chosen for slot i lt n and 0 otherwise 2 Let N Z be the non negative number of tests to be performed on the purpose built component j J for i lt n we assume N 0 N e Objective function We minimize the total cost i e the cost of the off the shelf components c and the cost of the purpose built components Tij tij Tij Nij CHAPTER 4 MATHEMATICAL PROGRAMMING EXERCISES 48 EXERCISES Software Modelling and Architecture L Liberti e Constraints 1 assignment constraints each component slot in the architecture must be filled by exactly one software component Vi Xn 1 jELUJi 2 delivery time constraints the delivery time for an off the shelf component is simply dij whereas for purpose built components it is tij Tij Nij Vi lt n p dij Xi ti rij Nij vij lt T jel j Ji 3 reliability constraints the probability of failure on demand of off the shelf components is kij whereas for purpose built components it is given by n pijbi 1 big 070 Ns 9 1 pij pig 1 bij 07t Nis so the probability that no failure occurs during the execution of the i th component is si 22 nimi Y Vig wig Qi e
54. e we shall see how a large complex Mixed Integer Nonlinear Programming MINLP problem taken from 12 can be reformulated to a Mixed Integer Linear Programming MILP problem It can be subsequently modelled and solved in AMPL Large software systems consist of a complex architecture of interdependent modular software compo nents These may either be built or bought off the shelf The decision of whether to build or buy software components influencese the cost delivery time and reliability of the whole system and should therefore be taken in an optimal way Consider a software architecture with n component slots Let I be the set of off the shelf components and J the set of purpose built components that can be plugged in the th component slot and assume I N J Let T be the maximum assembly time and R be the minimum reliability level We want to select a sequence of n off the shelf or purpose built components compatible with the software architecture requirements that minimize the total cost whilst satisfying delivery time and reliability constraints 4 6 1 Solution This problem can be modelled as follows e Parameters l Let N N 2 for alli lt n s is the expected number of invocations 3 for alli lt n j Ii cij is the cost dj is the delivery time and uij the probability of failure on demand of the j th off the shelf component for slot i 4 for all i lt n j Ji Gj is the cost tij is the estimated
55. eGood callAssistance VendingMachine goods Inventory Coins Inventory askSelection theCode askMoney theMoney 1 AngryClient kickMachine clVendingMachine askConfirmation askCallAssistance callAssistance theTrouble int isGoodAvailable theGood isChangeAvailable theMoney 7 wa A vmClient aoVendingMachine _ iet TORRE EE T ser fix ae 1 _ vmAssistanceOp AssistanceOperator fix refill theGood Figure 2 16 The class diagram of a vending machine CHAPTER 2 UML EXERCISES goods seins Inventory previous type 1 1 number next 25 EXERCISES Software Modelling and Architecture L Liberti CHAPTER 2 UML EXERCISES 26 Chapter 3 Modelling This chapter groups some modelling exercises only some of which involve UML 3 1 The vending machine revisited Consider the vending machine described in Sect 2 1 2 2 2 3 and 2 4 6 The proposed use case diagram Fig 2 2 sequence diagram Fig 2 7 and class diagram Fig 2 16 make up for a very poor system modelling indeed The vending machine is always thought of as a monolitic entity this makes the external relationships clear but says nothing about how to plan and build one In particular the monolitic view is incompatible with the fact that a vending machine is com
56. eadprimitive exponential readprimitive sine readprimitive cosine readprimitive tangent readprimitive minus readprimitive readexpr readpower power readpower readprimitive readterm readpower readterm product readterm fraction readexpr readterm CHAPTER 4 MATHEMATICAL PROGRAMMING EXERCISES 41 EXERCISES Software Modelling and Architecture L Liberti readexpr sum param p main readdata main parse main evaluate 64 2 66 main printresult 64 evaluate evaluate 3 parse gettoken parse readexpr readprimitive 0 1 1 gettoken 0 1 readprimitive variable 0 5 readprimitive number 0 2 readprimitive logarithm 1 readprimitive exponential 1 readprimitive sine 1 readprimitive cosine 1 readprimitive tangent 1 readprimitive minus X readprimitive readexpr 2 readpower power 2 readpower readprimitive 1 readterm readpower 2 readterm product 2 readterm fraction 2 readexpr readterm 2 readexpr sum 2 3 checksum run model checksum mod data checksum dat option solver cplexstudent solve display data printf L n for i j in E x i j 19 printf hs 48 n i j printf Hua 4 3 1 3 CPLEX solution CPLEX 8 1 0 optimal integer solution objective 73 1 3 MIP simplex iterations O branch and bound nodes data 73 1 L main evaluate parse gettoken readprimitive cosine readpower power readterm product readexpr sum CHAPTER 4 MATHEMATICAL PROGRAMMIN
57. ems easily This chapter provides an introduction by way of examples to a mathematical programming software system called AMPL A Mathematical Programming Language 6 which is interfaced with continuous mixed integer linear CPLEX 8 and nonlinear solvers See www ampl com for details on downloading and installing the student versions of AMPL and CPLEX 4 1 Museum guards A museum director must decide how many guards should be employed to control a new wing Budget cuts have forced him to station guards at each door guarding two rooms at once Formulate a mathematical program to minimize the number of guards Solve the problem on the map below using AMPL Also solve the problem on the following map 33 EXERCISES Software Modelling and Architecture L Liberti P Belotti Carnegie Mellon University 4 1 1 Solution The problem can be formalized by representing each museum room by a vertex v V of an undirected graph G V E There is an edge between two vertices if there is a door leading from one room to the other this way edges represent the possibility of there being a guard on a door We want to choose the smallest subset F C E of edges covering all vertices i e such that for all v V there is w V with v w F To each i j E we associated a binary variable z is assigned the value 1 if there is a guard on the door represented by edge i j and 0 otherwise 4 1 1 1 Formulation e Paramet
58. ers G V A graph description of the museum topology e Variables xij 1 if edge i j E is to be included in F 0 otherwise e Objective function min x Tij i j eE e Constraints Vertex cover y xi 21 VicV jeV j yeE CHAPTER 4 MATHEMATICAL PROGRAMMING EXERCISES 34 EXERCISES Software Modelling and Architecture L Liberti 4 1 1 2 AMPL model data run museum mod param n gt 0 integer set V 1 n set E within V V var x1E binary minimize cost sum i j in E xl i jl subject to vertexcover i in V sum j in V i j in E x i j sum j in V j i in E x j i gt 1 museum dat param n 10 set E OMAN PF WNHRPRP PB oon FPF ON DWN pa o museum run model museum mod data museum dat option solver cplexstudent solve display cost display x 4 1 1 3 CPLEX solution CPLEX 7 1 0 optimal integer solution objective 6 2 MIP simplex iterations O branch and bound nodes cost 6 X i 12 0 13 1 16 1 17 1 28 1 34 0 45 1 79 0 8 9 0 9 10 1 CHAPTER 4 MATHEMATICAL PROGRAMMING EXERCISES 35 EXERCISES Software Modelling and Architecture L Liberti 4 2 Mixed production A firm is planning the production of 3 products 41 42 43 In a month production can be active for 22 days In the following tables are given maximum demands units 100kg price 100Kg production costs per 100Kg of product and production quotas maximum amount of 100kg units
59. ess Analysis of needs Deployment Functional specs Maintenance m Architecture Validation Technical specs Tests Implementation Integration Figure 6 1 The V development process 6 2 Initial offer 6 2 1 Kick off meeting Aims of the meeting 1 Formalize the customer requirements as much as possible a What is the deliverable i e what is actually sold to the customer b What is the first coarse common sense system breakdown 2 What data is needed from T Sale s databases 6 2 1 1 Meeting output 1 Given some meaningful key words or other well defined indicators in the description of a new project we want to classify it by some quantitative indices and look in a project database for all projects which were sufficiently similar at the initial stage and proceeded to completion with a uniform degree of success we should then display a list of such projects so that the user can immediately glance at all important information concerning risk assessment a The deliverable is a software module that must be plugged in the existing T Sale back office network it should have query access to some of the T Sale databases and should be usable through a web interface b At a first analysis we shall need e I O user interface through a web browser e a way to find meaningful indicators in the given project e a system to query the databases for those indicators and return information about ini
60. etRightChild gt getLeftChild gt setLevel 2 ct oct ct ch oct cb ch ch cb coc get right child type and level int theLevel 0 int theOQperatorLabel 1 theOperatorLabel t getChildType 1 theLevel expect theOperatorLabel 4 theLevel 1 std cout lt lt the peratorLabel lt lt lt lt theLevel lt lt std endl actual output is 4 0 return ret Compile the project by typing c o TreeNode TreeNode main cxx TreeNode cpp CHAPTER 3 MODELLING 30 EXERCISES Software Modelling and Architecture L Liberti and verify whether the output is as expected 4 1 If not why Is this a bug or a modelling error We would now like to code in TreeNode_main cxx a new function that accepts a tree node and returns the number of children of the root node of the expression tree Convince yourself that you cannot do this easily and explain why How can you fix this modelling error Change the UML diagram and the code accordingly 3 2 1 Solution The output is 4 0 The problem is given by the fact that the second argument of getChildType that is theLevel was not declared as an inout read write parameter but as an in read only parameter instead so it cannot be changed by the function itself notice the compiler issues no warning about this occurrence it is perfectly legal syntactically if not semantically The new function cannot be coded in because the model provide no mechanism for going fr
61. f common sense One becomes a good software architect by experience Chapter 2 focuses on simple UML exercises It is split in Sections 2 1 use case diagrams 2 2 sequence diagrams 2 3 state diagrams and 2 4 class diagrams Chapter 3 groups various modelling exercises only some of which involve UML Chapters 5 and 6 are large scale exercises that should give meaningful examples on various modelling techniques used in practical settings these sometimes employ UML like diagrams but are not necessarily based on UML Since some of these exercises use mathematical programming techniques there is a small collection of exercises on mathematical programming in Chapter 4 EXERCISES Software Modelling and Architecture L Liberti CHAPTER 1 INTRODUCTION 8 Chapter 2 UML exercises This chapter proposes small to medium scale exercises on UML Some of them are by the author whilst others have been taken from books credits are made explicit in each exercise where no explicit citation is given the exercise is to be considered the author s work UML is a graphical language consisting of diagrams of many different types each referring to a system be it a software system or otherwise seen from a specific point of view Thus use case diagrams illustrate actors and actions of a system without any reference to logic or the temporal sequence of events sequence diagrams underline the temporal event flow state diagrams encode the logic
62. gram 6 3 3 1 1 Interfacing An interface is a module whose only purpose is that of passing data between other module Interfaces are useful to standardize function calls or message passing protocols Func tional technical architectures may become entangled and modularized after prototype implementations have exhibited previously unsuspected module connection needs resulting in architecture graph diagrams having many arcs edges connections and relatively few nodes modules The interfacing operator is an automatic graph reformulation that adds interface modules in order to reduce the total number of connections Consider a digraph G V A representing the existing architecture We aim to construct a digraph G V A with fewer arcs but same transitive closure i e same connection topology by introducing interface modules In our formalism we represent the inter modular connection relation type as a colour on the corresponding arc Given an arc colouring u A N of G and a connected subgraph H U F of G such that e u f for all e f F G is defined as G with the subgraph H replaced by a subgraph H U F where U UU t u 1 1 v F if and only if u v F The aim of this reformulation is to simplify a set of interconnections of the same type In the extreme case where H is a complete subgraph the reformulation replaces it with a complete star around which reduces the number of i
63. h or not Given two indicators u v and distances d with relative clusterings Yua and ws we first scale the indicator values and distances so that they are comparable This can be easily done by scaling the two clustering intervals gq and I 5 to the interval 0 1 for all p P let u _ up ulp p p u p ces tlp vip 9 v p v p d ulp ds u p u p 5 E v p v p v p We define the dissimilarity between the two clusterings Yud yos AS A Yuas Ys d 8 Y alp peP Notice this definition does not actually consider the clustering itself but just the indicator and the distance this occurs because of the way our clusterings are defined More precisely this occurs because the cluster each p P belongs to is determined by p alone and not by the other elements of P Given an overall tolerance e gt 0 an early indicator clustering y where i lt m and d DP matches a late indicator clustering Yh where j lt n and DF if either one of the two conditions below is satisfied CHAPTER 6 A SEARCH ENGINE FOR PROJECTS 80 EXERCISES Software Modelling and Architecture L Liberti 1 A 95 95 S 6 2 Avia Vs min Aio ono h we denote the matching by M 1k 15 1 and a mismatch by M od Ys 0 If two matching clusterings satisfy the first condition it is a close match The second condition is a catch all condition which ensures that we can m
64. he partition This problem is often called GRAPH PARTITIONING or MIN k CUT problem 4 4 1 1 Formulation and linearization e Indices i j V and h k K 1 2 3 e Parameters for each i j E di is the edge weight distance between i and j c backbone updating cost m minimum cardinality of the subnetworks e Variables for each i V h K let zip 1 if vertex i is in Vp and 0 otherwise e Objective function minj 5 5 Cdi Vin jk hzkeK i je E e Constraints VieV 5 Lip 1 assignment 4 3 keK Vh e K p Zik 2 m subnetwork cardinality 4 4 ev This formulation involves products between binary variables and can therefore be classified as a Binary Quadratic Program BQP Its feasible region is nonconvex due to the integrality constraints and the quadratic terms and the continuous relaxation of its feasible region is also nonconvex due to the quadratic terms This poses additional problems to the calculation of the lower bound within Branch and Bound BB type solution algorithms However the formulation can be linearized exactly which means that there exists a Mixed Integer Linear Programming MILP formulation of the problem whose projection in the z space of the BQP yields exactly the same feasible region The above program can be reformulated as follows hk 1 replace each quadratic product r j by a continuous linearization variable w 0 lt wk lt 1 constraine
65. in the CLDB database retrieve it else compute it and store it Determine M y yi and store it in the CLDB database if M E v5 1 for each k Kiq compute the set T 7 vis and store it in the CLDB database The formal data flow description of the background process is start vE d v 5 i lt mnadeDE Aj lt nade DE 5S gt C 95 55 i amp m d e DE nj lt nas e DE PES CSE store C 5 l M M c ee PG 75 OE 15 C k Kia 25 store M stop l i The required data structures are all those listed in Section 6 3 4 1 4 aside from the foreground process class plus a background process class containing e list of early indicators uf i lt m e list of late indicators up j m e matching information M array of booleans indexed on i lt m d DP j n DF e matching cluster information T maps clusters yg for varying k lt K 4 to list of matching clusters yjsn for varying h 1 Kjs e methods for computing A applied to clusterings e methods for computing intersections of clusters e methods for computing symmetric differences of clusters e methods for computing A applied to clusters 6 3 4 1 6 Class structure The class structure is detailed in Fig 6 9 CHAPTER 6 A SEARCH ENGINE FOR PROJECTS 82 EXERCISES Software Modelling and Architecture L Liberti Project DBInterface Indicator A contains
66. ine Generate the header file and implementation code using Umbrello then add the implementation of the only non obvious functions getNumberOfChildren and getChildType as follows int TreeNode getNumberOfChildren number of children int nc 0 switch m operatorLabel case 0 sum nc 2 break case 1 difference nc 2 break case 2 multiplication nc 2 break case 3 division nc 2 break case 4 square nc 1 break case 5 cube nc 1 break CHAPTER 3 MODELLING 28 EXERCISES Software Modelling and Architecture L Liberti AssistanceOp Customer Controller Robot CoinAcceptor MessagingSystem Door E selectGood theGood H veriiyavalaniithesood boo fnot available A callAssistance problemType bdo assistanceRefill openAndRefill A O O repeat displayOutstanding theMoney insertMoney theMoney newAmount getAmount int until amount price gt if confirmed outProduct theProduct HA dealProduct theProduct e EN outputChange theMoney takeGood theGood Figure 3 2 The revised sequence diagram of a vending machine TreeNode operatorLabel int 0 level int
67. is weighted by the quantity p of data exchanged between the subroutines We want to choose a subset L C E such that for each u V there is v V with u v L i e L covers V such that each vertex v V is adjacent to exactly 1 edge in L and such that the total weight p L gt gyer Pij is maximum G is shown below 0 1 CHAPTER 4 MATHEMATICAL PROGRAMMING EXERCISES 40 EXERCISES Software Modelling and Architecture L Liberti 4 3 1 1 Formulation e Parameters for each i j E pij is the weight on the edge e Variables for each i j E xi 1 if i j L and 0 otherwise e Objective function max gt Pi j Ti j e ij eE e Constraints VieV No sS 4 1 jeV j eE Vj ek Tij 0 1 4 2 4 3 1 2 AMPL model data run checksum mod set V set E within V V param p E var x1E binary maximize data sum i j in E pli jl x i jl subject to assignment i in V sum j in V i j in E x i j sum j in V j i in E x j i lt 1 checksum dat set V main readdata parse evaluate printresult gettoken readexpr readprimitive variable number logarithm exponential sine cosine tangent minus power readpower readterm product fraction sum set E main readdata main parse main evaluate main printresult evaluate evaluate parse gettoken parse readexpr readprimitive gettoken readprimitive variable readprimitive number readprimitive logarithm r
68. jel j J whence the constraint is TI o gt R i lt n notice we have three classes of reliability constraints involving two sets of added variables Y y This problem is a MINLP with no continuous variables We shall now apply several reformulations to this problem call it P 1 We take the logarithm of both sides of the constraint o gt R to obtain 5 Si 5 HijTij 5 jcij gt log R i lt n GEL j Ji 2 We now make use of the fact that Nj is an integer variable for all i n j Jj Fork 0 N we add assignment variables v so that VE 1 if N k and 0 otherwise Now for ij k pig big 1 545 8 DF all k 0 N we compute the constants Y Cops tog b E DR which we add to the problem parameters We remove the constraints defining J in function of N Since the following constraints are valid vi lt n jedi Xov 1 4 8 k lt N Vi n j Ji 5 kvg Ng 4 9 k lt N Vi njcJ DY ovh du 4 10 k lt N CHAPTER 4 MATHEMATICAL PROGRAMMING EXERCISES 49 EXERCISES Software Modelling and Architecture L Liberti the second set of constraints are used to replace Nj and the third to replace 2 The first set is added to the formulation We obtain min y CijTij 5 Gij tij Tij 5 kv aes i lt n jJEL je k lt N j HUJi Vi lt TL p dig Xi So tis Tij 5 kui ae lt T jeli j Ji k lt N desi Y mary Y 2 2 ovg gt log R i lt n je
69. l gt xli h x j 1 1 netdes dat param n 13 param k param c param m 2 param d I w rae 10 11 12 13 ODANOAAUHTBF 4 WWNNNN SE o NPRPONNNRPRPOUNFANWNHN PRP PO netdes run model netdes mod data netdes dat for i in V jinV i lt j4 let d j i d i jl option solver cplexstudent solve CHAPTER 4 MATHEMATICAL PROGRAMMING EXERCISES 45 EXERCISES Software Modelling and Architecture L Liberti display cost for h in K 1 printf subnetwork d h for i in V 1 if x i h 1 then 4 printf Ad i printf n F 4 4 1 3 CPLEX solution For k 3 CPLEX 8 1 0 optimal integer solution objective 232 5 1779 MIP simplex iterations 267 branch and bound nodes cost 232 5 subnetwork 1 6 11 subnetwork 2 3 4 10 subnetwork 3 12578 9 12 13 The solution is in the picture below For k 4 CPLEX 8 1 0 optimal integer solution objective 332 5 18620 MIP simplex iterations 1403 branch and bound nodes cost 332 5 subnetwork 1 125 7 8 12 13 subnetwork 2 4 9 subnetwork 3 3 10 subnetwork 4 6 11 The solution is in the picture below CHAPTER 4 MATHEMATICAL PROGRAMMING EXERCISES 46 EXERCISES Software Modelling and Architecture L Liberti 4 5 Error correcting codes A message sent by A to B is represented by a vector z 2 2 IR An Error Correcting Code ECC is a finite set C with C n of messages with a
70. l j Ji k lt N Vi X n j Ji Su 1 k lt N 3 We distribute products over sums in the formulation to obtain the binary product sets xij VE k NY for all n j Ji We replace each binary product Tijv with indices ranging over all the appropriate ranges by continuous linearizing variables wk defined over 0 1 and add the following constraints wk S tij wr ud VE and wk gt Lig VE 1 these supply a well known exact linearization for products of binary variables 5 By repeatedly applying this reformulation to all binary products of binary variables we get a MILP reformulation Q of P where all the variables are binary We remark that the MILP reformulation Q derived above has a considerably higher cardinality than P More compact reformulations are applicable in step 3 because of the presence of the assignment constraints 11 A semantic interpretation of step 3 is as follows Notice that for i n j Ji if aj 1 then Tij Y vi because only one value k will be selected and if aj 0 then z 5 vi because no value k will be selected This means that Vien jet zg M vf 4 11 k lt N is a valid problem constraint We use it to replace x everywhere in the formulation where it appears with j J obtaining a opt reformulation with r for j I and quadratic terms vivi Now because of 4 8 these are zero when i j l p or k 4 h and are equal to vf when i j l p and k h so
71. leader INTEGER leader2 INTEGER la project_FKindext Y customer ID La project FKindex2 conditionmap D assignment ac Y project ID INTEGER FK amount DOUBLE ispaid BOOL datepaid DATE financial FKIndext Y customer ID financial_FKindex2 Y project ID project customer ID To 3 n t o 4 ID INTEGER project customer ID INTEGER FK project ID INTEGER FK name VARCHAR 45 description VARCHAR 255 created DATE start DATE stop DATE cost DOUBLE documentation VAR CHAR 255 isvalid BOOL invalidated DATE replacedby INTEGER 3g schedule FKindex1 Y project ID Y project customer ID 6 6660000020209 499 Y ID INTEGER conditionmap ind Y team ID INTEGER FK ID INTEGER Y employee ID INTEGER FK Y team phase ID INTEGER FK Y team phase project customer ID INTEGER FK Y team phase project ID INTEGER FK timeshare DOUBLE assignment_FKindext Y team ID W team phase project ID W team phase project customer ID Y team phase ID assignment FKindex2 Y employee ID description VARCHAR 45 pas eam x ID INTEGER Y phase project ID INTEGER FK Y phase project customer ID INTEGER FK o phase ID INTEGER FK description VARCHAR 255 team FKindext Y phase ID Y phase project customer ID Y phase project ID Figu
72. m past projects and cluster data according to different indicators i e tech nological area to which the project belongs type of architecture topology expertise needed total projected cost total actual cost risk to get an idea of what it means for projects to be similar Classify indi cators according to whether they can be known at an early i e technological area or late stage in the project e g total actual cost Compare clusterings if roughly same number of clusters and each cluster has roughly the same cardinality we can infer that the two indicators are probably correlated Assess correlations between all early late indicator pairs Classify new project according to early indicators look at correlated late indicators and output the projects in the corresponding clusters see Fig 6 2 1 User will input project indicators known at early stage 2 Functionality an input web form user interface 3 Which among these early indicators are quantitative which qualitative 4 What sort of clustering of the project space do they lead to 5 According to what other indicators late indicators can project be clustered CHAPTER 6 A SEARCH ENGINE FOR PROJECTS 63 EXERCISES Software Modelling and Architecture L Liberti early indicator late indicator pos EN pens ATT p5 b zu EN 1 B 0 o X j e os 1 e A l 1 1 A SN e 0 I d SNA 1 1 j I i N gt 1 M l e A b dE A 1 5 P l
73. ment CHAPTER 6 A SEARCH ENGINE FOR PROJECTS 69 EXERCISES Software Modelling and Architecture L Liberti 6 3 2 1 Meeting output Here is one possible approach to solving these problems 1 find all project indicators which are known at the initial stage details of first phase customer history personal compatibilities in teams 2 propose a sizable number of quantitative indices that can be associated to a project initial projected cost cost curve required skill levels total human resources cost number of teams number of people total cost 3 cluster all projects with similar degree of success i e look at the condition field and at the number of invalidated phases and produce a partition of the set of projects such that all projects in a partition subset have the same degree of success 4 the most meaningful quantitative indices in the proposed set are those having the least variance in each partition subset 5 finding the variance of the project indicators in the partition subsets will give an idea of the indicator reliability 6 3 3 Functional architecture Propose a functional architecture for the software This should include the main software components and their interconnections as well as a break down of the architecture into sub parts so that development teams can be formed and assigned to each project part Since system wide faults arise from badly interacting teams it is naturally wise to minimize the
74. milarity without implying the triangular inequality CHAPTER 6 A SEARCH ENGINE FOR PROJECTS 79 EXERCISES Software Modelling and Architecture L Liberti a Vp P 3k Kya p Wak covering condition b Vk Kua Vp War v kd v p v k 1 d cluster extent Notice we define clusterings so that yya is unique for each choice of v d and can be computed in O P This is not the only possible such definitions Other definitions allow for non uniqueness and for higher computational complexity orders Each subset yuax of a clustering is called a cluster because of b we can assign to each cluster Yvak an interval Iyak v kd v k 1 d Let y be the clustering of P corresponding to the early indicator v and distance d DP with Kia 4E let YE be the k th cluster of 4E for k lt Kjq and likewise for late indicators Fig 6 8 shows an example of a clustering where P 1 10 v 0 0 3 d 1 vU Ko Lia as oiai iain cini ka p 4 p 4 p E EOS i ril rg g tot AMEN E eee por Dearest bo 0 41 uec dcc o BENE ENMNMNMT BEONON E RA a 123 4 5 67 8 9 10 Figure 6 8 Clustering example We obtain three clusters wai 4 5 6 10 with Iva 0 1 Ywa2 2 3 4 7 with I a2 1 2 and 7vas 1 8 9 with Ivas 2 3 6 3 4 1 3 Clustering comparison Our software relies on our ability to succesfully compare early and late clusterings and say if they matc
75. n associated function p C R such that for each pair of distinct messages x y C the inequality z y gt p x p y holds The correction radius of code C is given by Ro mi c qn p x and represents the maximum error that can be corrected by the code Assume both A and B know the code C and that their communication line is faulty A message x4 C sent by A gets to Bas p C because of the faults Supposing the error in zp is strictly less than Ro B is able to reconstruct the original message x4 looking for the message x C closest to p as in the figure below C x y pla p y z T LA e nearest n transmission Formulate a nonlinear mathematical program to build an ECC C of 10 messages in R 2 where all message components are in 0 1 so that the correction radius is maximized 4 5 1 Solution 1 Indices j lt m i n 2 Variables e x c R position of i th message e p R value of p on x 3 Objective function max min pj i lt n CHAPTER 4 MATHEMATICAL PROGRAMMING EXERCISES 47 EXERCISES Software Modelling and Architecture L Liberti 4 Constraints e coordinates limits lt lt Vi lt n j lt m e distances llz z 2pi p amp Yik lt n The AMPL implementation and solution to be carried out by the MINOS solver because the model is nonlinear is left as an exercise 4 6 Selection of software components In this exampl
76. nt past projects Com put ational engines Clustering engine Clustering significance evaluator Database server T program Classification Cluster data 1 cluster data Find significant indicators Cluster data Cluster according to indicators Program Classify new projects Cluster DB Created with Poseidon for UML Community Edition Not for Commercial Use CHAPTER 6 A SEARCH ENGINE FOR PROJECTS 66 EXERCISES Software Modelling and Architecture L Liberti Risks 1 Failure to obtain necessary data clearance from T Sale catastrophic low probability 2 Not enough specific in house clustering expertise serious high probability 3 Results not as useful as expected low medium probability Address risks 1 Insert clause in contract 2 Plan training 3 Insert clause in contract 6 3 System planning We shall now suppose that T Sale accepted VirtualClass offer and is now engaged in a contract The next step is to actually plan the system The contract clearly states that T Sale is under obligation to provide T Sale with database details which are shown in Fig 6 3 6 3 1 Understanding T Sale s database structure Aims of the meeting analysis and documentation of T Sales database structure Note that the project s condition contains information about whether the project was a success or a failure and other overall properties Make sure every software engineer under
77. nterconnections by a factor U Naturally in order for this reformulation to be worthwhile we require F lt F As F is bounded above by 2 U it is interesting to study the problem of finding a not necessarily induced subgraph H U F of G whose arcs have the same colour and such that F U is maximum Let 1 K be the set of arc colours in G For all v V 4 consider binary variables x lifv U and 0 otherwise For any colour k K the problem of finding the densest proper uniformly coloured CHAPTER 6 A SEARCH ENGINE FOR PROJECTS 71 EXERCISES Software Modelling and Architecture L Liberti subgraph Hj U F of G can be formulated as follows max 5 Ly Ty 5 Ly 6 1 u v Ai 1 vEVi 1 V u v E Aizx1 uty lt min max 0 Huv k 1 max 0 k Huv 1 6 2 zr 0 1 6 3 The interfacing operator is implemented by algorithmically providing a solution to 6 1 6 3 We apply the interfacing operator to this graph on the blue arc color data flow arcs coded by the label 2 in the AMPL data file The AMPL model file is as follows interface mod AMPL model for interface creation graph param n gt 1 integer set V 1 n set E within V V edge weights param c E edge inclusions param I E vertex colours param lambda V arc colours param kmax default 10 param k lt kmax gt 0 integer default 1 param mu E gt 0 integer lt
78. of product that would be produced in a day if all production lines were dedicated to the product Product Ay A As Maximum demand 5300 4500 5400 Selling price 124 109 115 Production cost 73 30 52 90 65 40 Production quota 500 450 550 1 Formulate an AMPL model to determine the production plan to maximize the total income 2 Change the mathematical program and the AMPL model to cater for a fixed activation cost on the production line as follows Product A4 A A3 Activation cost 170000 150000 100000 3 Change the mathematical program and the AMPL model to cater for both the fixed activation cost and for a minimum production batch Product Ay A As Minimum batch 20 20 16 E Amaldi Politecnico di Milano 4 2 1 Solution 4 2 1 1 Formulation e Indicex Let i be an index on the set 1 2 3 e Parameters P number of production days in a month di maximum market demand for product i vj selling price for product i cj production cost for product i qi maximum production quota for product i as activation cost for the plant producing i l minimum batch of product i e Variables a quantity of product i to produce a gt 0 qj activation status of product i 1 if active 0 otherwise CHAPTER 4 MATHEMATICAL PROGRAMMING EXERCISES 36 EXERCISES Software Modelling and Architecture L Liberti e Objective function max Y vi ci
79. om a given node to its parent node much less the root node of the tree The correct UML class diagram is given in Fig 3 4 TreeNode operatorLabel int 0 level int 0 leftChild TreeNodePtr rightChild TreeNodePtr parent TreeNodePtr getNumberOfChildren int getChildType childIndex int 0 theChildLevel int 0 int ES pa rent Pd Ny leftChild AightChild datatype TreeNodePtr Figure 3 4 The corrected UML class diagram for the TreeNode class CHAPTER 3 MODELLING 31 EXERCISES Software Modelling and Architecture L Liberti CHAPTER 3 MODELLING 32 Chapter 4 Mathematical programming exercises The mathematical programming formulation language is a very powerful tool used to formalize opti mization problems by means of parameters decision variables objective functions and constraints Such diverse settings as combinatorial integer continuous linear and nonlinear optimization problems can be defined precisely by their corresponding mathematical programming formulations Its power is not limited to its expressiveness but usually allows hassle free solution of the problem most general purpose solution algorithms solve optimization problems cast in their mathematical programming formulation and the corresponding implementations can usually be hooked into language environments which allow the user to input and solve complex optimization probl
80. ors Destructors Complex Complex 4 initAttributes Complex Complex Methods Accessor methods public static attribute accessor methods public attribute accessor methods CHAPTER 2 UML EXERCISES 21 EXERCISES Software Modelling and Architecture L Liberti protected static attribute accessor methods protected attribute accessor methods private static attribute accessor methods private attribute accessor methods Set the value of m realPart Oparam new var the new value of m realPart void Complex setRealPart double new var m realPart new var Y Get the value of m_realPart return the value of m_realPart double Complex getRealPart 4 return m_realPart Y Set the value of m_imaginaryPart param new_var the new value of m_imaginaryPart void Complex setImaginaryPart double new var m imaginaryPart new var Y Get the value of m_imaginaryPart return the value of m_imaginaryPart double Complex getImaginaryPart 4 return m_imaginaryPart Other methods Oparam theRealPart void Complex setReal double theRealPart param theImaginaryPart void Complex setImaginary double theImaginaryPart return double double Complex getReal 4 return double
81. ould be as simple as looking up a pre computed boolean value in an array in turn this means that the background process must pre compute all possible matching information and store it in the CLDB database Informally the data flow for the background process is as follows start all possible pairs early indicator distance late indicator distance clustering BB store clustering do clustering match list of matching clusters d l 1 store matching info stop To make the data flow descriptions more formal we must make clear what we mean precisely by such concepts as indicator distance cluster clustering clustering comparison 6 3 4 1 1 Indicators An indicator is a non negative real valued function v P R defined on the set of projects P Given an indicator v we let m v m v p d v p Early indicators are indicators whose value can be defined before the project is started late indicators may only be defined after the project ends Consider early indicators v for i lt m and late indicators vj for j lt n For each early indicator i lt m we also consider finite sets of distances DF with and likewise for late indicators 6 3 4 1 2 Clusterings Given an indicator v on P and a distance value d Ry a clustering Wwa of P is a set of Kya Yva subsets Yuax of P where k K 4 and Ui Ui Kya ES gt such that 1By distance we mean here a generic measure of si
82. pdatedLogData furthermore it must return the exact number of bytes used during the parsing add them to the LogSize and put the result into UpdatedLogSize The format of the DB table is as in Section 5 4 1 3 Step 2 the tribe and zone name fields are left blank e ErrorStatus SaveLogData in DBTable UpdatedLogData in DBConnectionData theDB Connects to the log database server finds the tribe corresponding to each IP address in the DB table finds the zone corresponding to each document URL in the DB table completes the table saves the latest log data in the log database server adding them to the relevant table Notes to implementors a Some of the above functions are extensive pieces of coding They should be implemented by breaking them up into smaller protected functions b The main function of this CHAPTER 5 LOG ANALYSIS ARCHITECTURE 58 EXERCISES Software Modelling and Architecture L Liberti program should take a number of seconds s as argument and configure and start a timer calling the log reading procedure every s seconds The transition state diagram for the log reading daemon is given in Fig 5 4 and the class diagram in Fig 5 5 gt ReadConfiguration ReadLogFileTail L Configuration File ReadUpdateInfo Update Info File ParseLogData SaveUpdatelInfo SaveLogData Fork Figure 5 4 The transition state diagram for the log reading daemon 5 4 2 3 Log database
83. posed of different parts Given the following list of parts 1 main controller mechanical robot coin acceptor remote messaging system CU e WCW N door and the fact that 2 3 4 5 can only be interfaced with 1 draw a use case diagram and a sequence diagram to provide an initial blueprint for the inner workings of a vending machine 3 1 1 Solution The use case diagram is found in Fig 3 1 The sequence diagram is found in Fig 3 2 Notice that they do not provide mechanisms for calling assistance operators on failure of providing change and or food How should these diagrams change to cater for these occurrences 3 2 Mistakes in modelling a tree Fig 3 3 describes the class diagram of a tree node which can be used recursively to build an expression tree 27 EXERCISES Software Modelling and Architecture L Liberti ask for mone tos ood saco Na E DE Za erty good avaiblty T rad gt ask confi maton sec good E gm a l l as gt u output goo main controller m o Esc S ls N pero a gt A cal o E system es output NP coa A A mechanical robot deal out good q ul pa BS p Pa gt send message to assistance j hb remote messaging system i a money p coin scena a aet p P tin NS Cra MT Wc door lt y s a assistance operator Figure 3 1 The revised use case diagram of the vending mach
84. re 6 3 T Sales database structure CHAPTER 6 A SEARCH ENGINE FOR PROJECTS 68 EXERCISES Software Modelling and Architecture L Liberti 6 3 1 1 Meeting output 1 10 11 12 13 The table among technical commercial leadership which contains the employee s ID gives its main occupation We consult the expertise table For a description of the expertise we consult expertisemap We simply look at the condition field of the project table whose description is in conditionmap We scan the phase table for a given project and count the times the isvalid field contains true We find the last phase of the project looking at the phase table and we compare the stop field with the datepaid field of the financial table We scan the financial table for a given customer and find whether the completion date stop field of the last phase in the project table phase accessed through project corresponds with the datepaid field of the financial table We sum the costs of all the non invalidated phases in the project and compare it to the total project cost amount field in financial table The function changes every time a phase is invalidated or created The cost is the cumulative cost of all the phases which are valid at any given time Since we only know the costs due to human resources we must find the salaries of all the people involved in the project and scale them by the percentage of their time they devo
85. rnercial T 9 employee ID INTEGER FK selling FLOAT contacts FLOAT publicrelations FLOAT commercial FKindext Y employee ID 0060000000 salary FLOAT leadership x Y employee ID INTEGER FK charisma FLOAT success FLOAT delegation FLOAT leadership FKindext Y employee ID Commercial customer ID INTEGER name VARCHAR 45 name VARCHAR 45 surname VARCHAR 45 telephone VARCHAR 20 email VARCHAR 45 office VARCHAR 20 department VARCHAR 20 rank VARCHAR 20 address VARCHAR 255 birthdate DATE birthplace VARCHAR 45 telephone YARCHAR 20 personal FKindext Y employee ID expertisernap Gni Y ID INTEGER description VARCHAR 45 expertise employee ID INTEGER FK expertisemap ID INTEGER FK level DOUBLE expertise_FKindext Y employee ID expertise FKindex2 expertisemap ID financial Las Y ID INTEGER Y project customer ID INTEGER FK Y customer ID INTEGER FK Q isnew BOOL v Y customer ID INTEGER FK address VARCHAR 255 contactname VARCHAR 255 contacttel VARCHAR 20 2 contactmail VARCHAR 45 detalis_FKindex1 Y customer ID Technical project Y ID INTEGER Y customer ID INTEGER FK le conditionmap ID INTEGER FK name VARCHAR 255 condition INTEGER
86. server The database server of choice is MySQL www mysql com but this can be changed as desired with any other internet enabled DB engine accepting SQL queries and exporting data through the normal standardized APIs CHAPTER 5 LOG ANALYSIS ARCHITECTURE 59 EXERCISES Software Modelling and Architecture L Liberti Updstelnfo configuration Configuration Hog Size long 1 dast Record Date DateTime dogTail Text Reader Appears in tparse Log Cata int saveLog Data int ead Update lnto int saveUpdatelnfa int Specializes fileName int file Handle FilelO db User String db Brand int db Server String db Database String db Password String HogFile Format int xslFile Name String HogURI String t LogDriver parse Log Datat yint Fppears in LogReader configuration Configuration update Info Update info db Connection DB Connection dogTable LogRecord f eadLogFileTail int Configuration tupdate FileName String ead Configuration Filet yirt LogRecord tribe String zone String IP String URL String access Date Time Date Time accessTypeint Popears in Appears in DBConnection connection Connection connection URL String statement Statement lt onfiguration Configuration openQ int 4close int execute Quen result Result Set rint Pppears in Figure 5
87. ss is given in Fig 2 11 Complex realPart double 0 imaginaryPart double 0 setReal theRealPart double setlmaginary thelmaginaryPart double getReal double getlmaginary double absoluteValue double add theComplexNumber Complex subtract theComplexNumber Complex multiplyBy theComplexNumber Complex divideBy theComplexNumber Complex Figure 2 11 The class diagram for a complex number Most UML modellers can be used to automatically generate C or Java code from the class dia gram This results in class skeleton files a header file Complex h and a corresponding implementation file Complex cpp Both are given below DRCOG ok oko oko ok ok ok oko oko ok oko ke oko oko kk GRR A Ra AI A a a ak kk a 2k 2k 2k 2k kkk Complex h h Copyright liberti Here you can write a license for your code some comments or any other information you want to have in your generated code To to this simply configure the headings directory in uml to point to a directory where you have your heading files or you can just replace the contents of this file with your own If you want to do this this file is located at usr share apps umbrello headings heading h gt Code Generators searches for heading files based on the file extension i e it will look for a file name ending in h to include in C header files and for a file name ending in java to include in all generated
88. stands the database structure by answering the following questions 1 2 3 10 11 12 13 How do we find the main occupation of an employee How do we find the expertises of an employee How do we find the condition of a project How do we find how many times a project was changed How do we find whether a project was paid for on time or late How do we find whether a customer usually pays on time or late How do we verify that the cost of all phases in a project sums up to the total project cost How do we evaluate the cost in function of time during the project s lifetime How do we discriminate between the phase cost due to human resources and the cost due to other reasons How do we find the expertises with their levels that were necessary in a given project How do we find out the abilities and skills with their levels that were necessary in a given project How do we find out which teams were most successful How do we find out the most dangerous personal incompatibilities CHAPTER 6 A SEARCH ENGINE FOR PROJECTS 67 EXERCISES Software Modelling and Architecture L Liberti Human Resources employee technical AS Y ID INTEGER Y employee ID INTEGER FK employee ID INTEGER FK assignmentwork FLOAT expertise FLOAT Q availability FLOAT fax VARCHARI20 technical FKindext Y employee ID hq VARCHARI20 com
89. t of edges u v where u v belong to different clusters To each vertex v V and for each cluster k lt K we associate a binary variable r which is 1 if vertex v is in cluster h and 0 CHAPTER 6 A SEARCH ENGINE FOR PROJECTS 73 EXERCISES Software Modelling and Architecture L Liberti em ose j JT wee _ 5 7 Low HRDB CLDB e S 9 100 Figure 6 5 Diagram after interfacing otherwise We formulate the problem as follows min 5 5 5 Cult aktul 6 4 kAISK u v E VveV Mim 1 6 5 k lt K VES Y ma 2 1 6 6 vcV VVEVAk lt K Log 0 1 6 7 This model relies on binary variables and includes many nonconvex quadratic terms Various ways to linearize the formulation have been suggested 3 10 The objective function 6 4 tends to minimize the total weight of edges with adjacent vertices in different clusters Constraints 6 5 make sure that each vertex is assigned to exactly one cluster Constraints 6 6 excludes the trivial solution all the vertices in one cluster and ensures each cluster exists Further conditions such as the clusters not exceeding a balanced cardinality may also be imposed VES NX mad s 6 8 vEV A useful variant of the problem asks for all adjacent vertices with like colours to be clustered together The vertex colours are defined by an integer valued function A V N we denote A u by Au For all u v V wi
90. ted to the project In other words we must sum the scaled salaries over all phases of the project over all teams involved in the phase and over all people associated to the team We find the people involved in the project through phases and teams and we compute their expertise level vector Similar to the above We match the teams involved in a project with indicators such as the project s condition and the number of invalidated phases the fewer the better We find the subsets of people from a team which occur most often in the most unsuccessful projects 6 3 2 Brainstorming Ideas proposal The commercial offer quotes Given some meaningful key words or other well defined indicators in the description of a new project we want to classify it by some quantitative indices Such concepts as meaningful key words or other well defined indicators and quantitative indices are not well defined and therefore pose the most difficult problem to be solved in order to arrive at a software architecture In order to solve the problem a brainstorming meeting is called Aim of the meeting find a set of well defined new project indicators which are suitable for searching similar terms in the T Sale database find a set of quantitative indices to be computed using the T Sale database information which should shed light on the future life cycle of the new project document all ideas spawned during the meeting in a formal docu
91. tem ATMsystem ceu mM a 0 1 Customer Deposit Money A 0 1 0 1 Register ATM 1 y Bank whe e Hye Read gt A eese Figure 2 1 The simplified use case diagram of an ATM 2 1 2 Vending machine Propose a use case diagram for a vending machine that sells beverages and snacks Make use of inclusion and extension associations mark multiplicities and remember that a vending machine may need technical assistance from time to time 2 1 2 1 Solution The use case diagram is given in Fig 2 2 The symbols at each end of relation edges are called multiplici ties and they indicate how many times a given action occurs linked to its actor s and how many times a CHAPTER 2 UML EXERCISES 10 EXERCISES Software Modelling and Architecture L Liberti given actor carries out the corresponding actions a multiplicity n next to an action indicates that the actor can carry it out a minimum of n times and a maximum of oo times Boxes carrying a binary logical operator label and or xor help inserting some logical meaining into a use case diagram A relation A B carrying a triangle shaped arrowhead next to B stands for generalization object actor or action B generalises object A which means that A has all the properties of B and some more thus an angry client is a client with one more property that of being angry an angry client can thus carry out all the actions
92. th u v we introduce binary parameters Yuy 1 if u v have different colours We must then add the following constraints Vuzve V kZzltzkK utu lt Yuv 6 9 CHAPTER 6 A SEARCH ENGINE FOR PROJECTS 74 EXERCISES Software Modelling and Architecture L Liberti Should these constraints be too restrictive and make it too difficult for the solution algorithm to actually find a solution we may want to relax them somewhat We can do this by removing 6 9 and adding the term gt gt 32 urLvt Yuv to the objective function 6 4 uxveV kAI lt K Another useful variant allows the optimization process to determine the number of clusters actually used For all k K we introduce binary variables zz 1 if cluster k is non empty and 0 otherwise We change constraints 6 6 to VARESE Y ra 6 10 vEV to ensure that a cluster that does not exist need not have any vertices assigned to it and then we add the term 7 kc x to the objective function to be minimized thus ensuring that the maximum number of clusters should be empty Once the set of clusters K have been identified the current graph G may be replaced by a graph G V A where V is the set of clusters K and u v A if there are w u z v recall u v are subsets of V such that w u A The synthesis operator performs such a reformulation to the architecture diagram We now apply the synthesis operator to the architecture in order to identify some
93. tial intermediate and final cost time and resources estimates 2 We shall need T Sales data concerning e project descriptions CHAPTER 6 A SEARCH ENGINE FOR PROJECTS 62 EXERCISES Software Modelling and Architecture L Liberti project schedules project costs teams involved people involved other resources involved T Sale s answer as often happens is rather vague Dear VirtualClass Team We are sorry to have to tell you that the structure of our databases is classified information and we will only be able to give it to you at a later stage when and if we choose to employ your services We can however describe the main features of what we think is useful to your job We have an HR database detailing the usual information salary rank abilities and skills We have a technical database with project information nature and cost of project teams people schedule and associated changes We naturally have a commercial database detailing customers and payments Unfortunately the database which details hardware resources and costs may not be accessed as it contains some information classified at national level Best regards A Smith 6 2 2 Brainstorming meeting Aims of the meeting 1 propose ideas for a system plan with sufficient details for a rough cost estimate 2 collect these ideas in a formal document 3 decide on a sexy project name 6 2 2 1 Meeting output Main idea Collect all data fro
94. tossi Greedy prohibition and reactive heuristics for graph partitioning IEEE Transactions on Computers 48 4 361 385 1999 A Billionnet S Elloumi and M C Plateau Quadratic convex reformulation a computational study of the graph bisection problem Technical Report RC1003 Conservatoire National des Arts et M tiers Paris 2006 M Boulle Compact mathematical formulation for graph partitioning Optimization and Engineering 5 315 333 2004 C E Ferreira A Martin C Carvalho de Souza R Weismantel and L A Wolsey Formulations and valid inequalities for the node capacitated graph partitioning problem Mathematical Programming 74 247 266 1996 R Fortet Applications de l alg bre de boole en recherche op rationelle Revue Francaise de Recherche Op rationelle 4 17 26 1960 R Fourer and D Gay The AMPL Book Duxbury Press Pacific Grove 2002 Object Management Group Unified modelling language Superstructure v 2 0 Technical Report formal 05 07 04 OMG 2005 ILOG ILOG CPLEX 8 0 User s Manual ILOG S A Gentilly France 2002 D S Johnson C R Aragon L A McGeoch and C Schevon Optimization by simulated annealing An experimental evaluation part i graph partitioning Operations Research 37 865 892 1989 L Liberti Compact linearization for bilinear mixed integer problems www optimization online org May 2005 L Liberti Compact linearization of binary quadratic problems 4OR 5 3 231 245 2007

Software Modelling and Architecture: Exercises

Contents

Download Pdf Manuals

Related Search

Related Contents