noc19-mg15 - Lecture 52: GERT

[Music] [Music] a very warm and a good morning good afternoon good evening to all of you wherever you are in this part of this globe and once again welcome to all my dear friends and students in this da dm2 course which is data innocent decision-making to course on Nunda and patel mooc series and as you know this course duration is for 12 weeks which is 30 hours of contact in the video mode and this total number of lectures is 60 because each lecture is for half not and each week we have five classes of lectures each being for a half an hour and after each five that means after the first week then second week so on and so forth we have assignments so if you can notice on the slide we are in the 11th week which is the and we are doing the 52 lecture and you have already completed these 10 weeks which is 50 lectures and you have solved 10 such assignments so if you remember in the 51st lecture which was the first lecture in the 11th week we are discussing Wengert and launching of the spacecraft with concerning the booster rockets and we are considering two different scenarios in one obviously in both the cases booster rocket 1 & 2 can be success or unsuccessful that is for combinations but in the first case we will consider the success success leads to the actual success of the project and in the second case and obviously it will mean there are on three unsuccessful ones that means once access to failure and the third key is being first unsuccessful second been a success and in the fourth case both being failures in case two we'll consider that any one of them being successful is a success for the whole project which means if one is successful two is successful it's a success and in another case one success to failure third case one failure to success and the last case both being failures would all lead all these three things would lead to the failure of the project so we are considering the the concept of preparatory reactions which are to be taken for the launch so they can be different type of preparatory actions some probabilistic SAR deterministic and based on that we we return to the overall known where they return to the start of the test will be performed in such a way so that means we if you if you remember and let me copy it again again as I said it'd be easier for us to consider I will take it from yes so if you consider this concept here this is an inclusive order a deterministic one depending on how the nodes have been formed and in this case also is inclusive or in this case it is an or one it says it's a or is not there it means it will be the first case would be in exclusive on and the second case with the inclusive or so it is exclusive odd and this is an inclusive or based on that you preceded finish the concept of how the diagram is made now for this all the six nodes that means which have been drawn behave in the same manner if and only if the branches received at an input side and one branch is emitted from the output side so six are coming based on the output this one thus if two branches are in the series and they are being considered then the node type have no effect on the equivalent one band because series means what any one of them working would lead to the output being positive if it is parallel in a series one sorry in the series one my mistake in the series one if we have two consecutive concepts which are working and if any one of them fail so obviously that concept would launching of that this spacecraft is not possible in the parallel one if we consider in the simplistic sense any one of the in success would basically lead it he does to the suspect success of the the project now we will basically have to convert them into the query networks when an equivalent network would be defined as a reduction of the multi branch network which we already have into the basic and odd exclusive or inclusive on nodes and network says that the complexity of the diagram is reduced yet it basically has the same logical sequence of the output and the input combined together in the same way as it was earlier early means before you reduced so let me continue reading it and equivalent network is defined as a reduction of a multi branch network into one branch network where the parameters of the one branch network are derived from the multiple network which you have so if you remember we consider that time which was determining or probabilistic and for trying trying to find out the time we consider the moment generating function and the front the probabilistic feedback the probability of the of that branch being taken was also considered so we'll combine both moment generating function to find out the time as well as the probabilities to find out the probabilities of which path will be taken so you'll combine them from the overall complicated Network in the equivalent simplest form on the network second case would be the concept of a feed is only appropriate for the exclusive-or input output of the node so exclusive or if you remember you have the exclusive r is DS so it was basically did be if you are interested so this is the exclusive R so it means the realization of an any branch leading with the node causes the node to be realized is yes activated however one and only one of the branch leading into this node can be realized at a given point of time so that means only one is being realized it will be realized but if only one would be realized so it means the concept of feedback is only appropriate for the exclusive or input type of node this results from the fact that the feedback requests that the node being returned to be realized prior to the feedback based on which we will proceed but then mode cannot be realized if it is an ant type node unless all inputs have been realized so the exclusive or anyone would realize but in an network all of them has to be realized in order then the output is true so if you consider the very simple concept of of series and parallel in this case when it is an an one all the CDs is all the elements which are there in the series they should be activated such that current will flow from the point A to point B and in the concept of the parallel one you will basically have that any one of them working would mean that current will flow from node a to node B so you need not be basically all of them have to work at at least more than one combination have to work so we basically considered this in the very simplistic sense as I mentioned in the very simple we have a series in and parallel for the inclusive or input type only the branch representing the first activity completed is significant all other branches are ignored in computing the time the inclusive or is in a node is realized so in the extras inclusive or you will consider the first branch being realized would give you all the results as it requires which is unlike the exclusive water now since the feedback branch will always be completed after an on feedback branch so consider with a non feedback branch you will basically a feedback which will give you the output of of the second stage going as the as a feedback or an input at the first stage so they can be different type of loops as Isaac's explained so hence as this is possible the exclusive-or representation which exclusive or we have already considered is this one exclusive odd we see how so the exclusive odd representation can replace the inclusive arnoud if a feedback branch is incident to that node hence the overall logic circuit would be maintained third case if all the nodes have the exclusive or input characteristics then either all node outputs are of the provost ik type so probability means touristic output being there or the paths that is the collection of the branches so there are different paths you can follow so you can be path i1 to i2 i2 to i3 i3 to J so all the combinations can be there so I can be I 1 to I 5 i5 to i3 i3 to J so they can be different ways how you can do so if I draw the network it can be this is one of the ways this is one of the ways you can have one path like this this is the source and this is the sync I'm using being the starting and the ending one so consider is the starting s ending so there can be different ways how you LS that one so third if all the nodes are the exclusive or input characteristics then either all known outputs out of the probabilistic type so in this case the probability concept would come or the paths there's the collection of the branches which you have any one of the the path you take you combine all the branches with there in that path follow a deterministic output and they are independent with each other in the sense they are disjoint so the independent structure would not be there if this was not the case then at some input side of a node there would be possibility of two branches being realized simultaneously so if they are not axilla exclusive and exhausting every say in statistics so if that was the case so it was it was that case then they would be a possible of two branches being realized simultaneously and then hence how you basically take that path which will be taken up would basically be difficult to find ant in unless you have a probability of spillage splitters means their path one and path to being taken which are true fourth case can be for some network and on inclusive or input types can be converted in the exclusive-or relationship so to illustrate this each of the relationship is discussed in a quantitative fashion for the exclusive-or relationship we can basically have the following diagram so consider this so from PAH from the realization which is probabilistic one we go to three from two to go to three so let us again go back to the logic so I am going from the logical circuit to the diagrams so logical circuit to the diagrams and like this so this is the inclusive are so that would be on the right hand side and if I consider these are the probabilistic one the diamond shaped with the pointed on to the right the triangle one so these are the deterministic probabilistic one the probability is given P a and T is the time similarly probability P B and T B is given and we basically realize with the time T 3 bar mean the average time so in this case P 3 would basically be the corresponding probability P 1 into small PA which is the probability and this paths P 1 being taken P 2 into the probability P B and the average time would be calculated depending on the total average time which is taken in combined by the probabilities so it will be so if there are three paths so technically it would be P 3 would be P 1 into P a plus P 2 into P B plus P 3 into B for I consider so P 4 would basically be P 1 into P a plus P 2 into P B plus P 3 into PC considering there are three paths which are coming 1 2 3 and the corresponding time period average which is T 4 but would be P 1 into P a so I'm only repeating the first out terms which are outside the brackets in the numerator so it will be P 1 into P a the second term outside the backyard will be P 2 into P B and the third term would basically be P 3 into PC PC because there's a third part also I said and the corresponding time period would be based on the fact that you all tried to find on the average T 1 T 2 T 3 so T 1 T 2 T 3 T would be coming from the previous stage so we will consider that so it will be T 1 bar it would be calculated in the previous stage T 2 bar would be calculated in the previous stage and the corresponding and obviously they would be T 3 bar also because you are trying to find out the T 4 bar and the multiplicative factor inside the bracket in the numerator would be T 1 bar plus ta plus T 2 bar into T V plus T 3 bar into TC and the denominator will basically have have P 1 capital P 1 into PA plus capital P 2 into P V plus capital P 3 into P see it can be extended depending on number of such connections you have now obviously what are capital P is so where capital P I is the probability that the node I has been realized beforehand so if I consider as I said so obviously 1 2 & 3 am considering so in this case I consider 1 2 3 so obviously there would be much more no more nodes and more connection coming from the from the left so we'll consider the corresponding probabilities P 1 capital P 1 capital P 2 capital P 3 Sweden's fourth for the corresponding probability then the average time would be corresponding to those probabilities that is T 1 bar T 2 bar T 3 bar so once we find out T 4 it will be utilized in the next stage wherein to calculate T 5 will utilize this concept of T 4 bar and the corresponding of P 4 capital P 4 which is the probability so let us let me continue where P I is the probability that node I is realized and T bar I is the expected time that node I is DLS based on the probabilities in the time which are already given in the previous stage and obviously they should be realized for this introductory discussion only the expected time for a node to be realized given it is realized will be recalculated so given it realize you will only find the average expected time and the average time so no note that even though ta TB may have come a B constants depending on the time period the time to realize Note 3 in our case Note 4 and corresponding time period T 4 and T 4 bar or T 3 T 3 bar depending on how many such nodes based on which you are proceeding that would be through the utilization and these these T 3 T 4 not the bar values are random variables the derivations of P 3 and T 3 bar is is an human enumeration or the possible different of events that result in the realization on Note 3 so similarly once we want to realize Note 4 you will basically find out the different combinations based on which will proceed so they can be realized if either branch a or branch B is realized so if you have three parts either A or B or C is there as based on which we will proceed the probability that branch a will be realized is the probability that the branch one is the one is realized which is basically P 1 times the probability that the branch is real as given node is realized which is so you basically have the branches on the nodes the nodes realization is given by the small piece and the branch realization is given by the capital P so you will basically multiply them accordingly a similar discussion holds for the branch B an equivalent results which you found out so known by the definition of the exclusive or relationship branch a and B cannot occur both at the same time so that means if you have three bunches ABC they cannot occur at the same time if this was a possibility then node 3 would have to be an inclusive or where we will consider that more than one branch occurring is possible the expected time to realize node 3 given it is realized is the weighted sum of the possible times two realized in the node 3 so node 4 would depend on one two three similarly note three would depend on for this diagram which you have would depend on one and two you basically proceed it is it iteratively later on so consider this if node one was worth the same as note 2 that means P 1 is equal to P 2 and T 1 bar is equal to T 2 bar then the corresponding result equations would be P 3 can be counted so let me put this value so let me bring it here so P 3 is P 1 P a P 2 P B P 1 P 2 P and P B so consider if they are equal you take it outside this PA plus PB as already mentioned now coming to the time so the time factors are given by this equation this is the time factor so you consider that P 1 capital P 1 and P 2 are equal based on that if you want to just recalculate and and make that equation look nice without much complications so you can find out T 3 bar would be T 1 plus a so called factors so it will change and the network would be done drawn as we are going from 1 to 3 comes corresponding in the fact that mm node 1 and node 2 are the same if node 2 and node and node 1 are not the same the calculation remains as it is before so you basically have the equivalent probabilities as PA plus PB and the equivalent time would be given as already calculated out we know that you have just given the formula so only remember the general concept of how you find out the capital piece depending on how many such nodes you have before and the time average time also depending on how many nodes you have before so now let us consider the the and logic relationship and and it will be depicted as below so basically you'd be take and these are the probabilities in the time so you can basically go from the so the source or the start to one and two so the corresponding probabilities of paths being followed will be taken similarly there are two outputs happening from one and two depending on the logic relationship one would basically with the probability P a so the counterpart path because there are two paths would be 1 minus P a and the time taken in these two paths would be different obviously in the first case when probabilities P a it will be we are considering as T a and in the second case when the probability 1 minus P a it is considered at small T C similarly for node 2 you have the output given as the probability and the time given as P B and T B and probabilities values given we can find out the corresponding probability and the time period for the subsequent parts later so node 3 will be will only be realized if both a and B are realized the probability that that is realized is capital as I already said so considering the simplest case of P 1 and P 2 being equal we are that's the simple one so the probability that a is Els it is given by P 1 into P a and the probability that B is realized is given by P 2 into P B which you have already seen the properties does that both the both of them are realized is basically the intersection set or the intersection numbers in this case the intersection of the events associated with node 1 and 2 would be depicted by probability 1 intersection B which is common and that should be equal to P 1 and assuming P a B is P a into B B which is means you are trying to basically multiply the probabilities so we can find out that the branches must be realized if we have the corresponding time period being being the maximum which is being realized at two different points accordingly so kirtan must be taken here in the competition of the expected value since the expected value of a maximum is not usually in the maximum the expected value that should be remembered so this will be discussed in the later parts for this course not with what you will just mentioning that for this case were obviously in the time period t 1 into 2 and the time period from the source from where we start is given and we'll consider T 3 is basically the TS plus the max values and we proceed accordingly an equivalent probability and that the equivalent time would be equivalent would be found out and and utilize that for that network so we have from the source 1 2 3 outputs the probabilities are one for the second one the cumulative rope the equivalent probabilities PE equivalent time is T and the corresponding probabilities and time periods for the so called paths emanating from 1 & 3 are corresponding to 1 minus PA and 1 minus PE because you have that one part is realized another part is not realized would be given by 1 minus P a and similarly for the third party it would be 1 minus P B so once this is logical structure is done so the exclusive-or relationship can replace the end relationship at node 3 since only one branch is received is received at non 3 so if there are more than two branches obviously caution has to be taken into consideration where you can basically replace any one of the exclusive network concept in the other one so depending on the node structure which is there for the inclusive our relationship the analysis procedure as proceeds as in this case the branches of the network given below would basically give you the Nydia so the left part of the concept is basically equal to the right part and we will basically have the the equivalent part being considered in such a way we will consider the probabilities and the : probabilities of PA PB and PE and the time periods as given so thus the direction process would now involve the enumeration of all the mutually exclusive and alternative nodes in and will basically come my clearly show them each step such that you can find out what is the equivalent Network so description being branch a but not branch B is being his is being realized so it will be probability of PA minus intersection of the probabilities in a B and the equivalent time is given by TA similarly B is the branch and not a is the branch in that case is just swap the numbers it will be PB minus P suffix a intersection B and the tank will runtime is PB and in case branch a and branch B both are realized it will take the the probability of a intersection B which is the overall common so called area if you consider the concept of vein diagram and the equivalent time would basically the minimum time based on which you to see so in this section the the equivalent network will be derived from the following three basic networks which is the series one parallel on one and the self loop one depending on on whether the loops are allowed for the parallel and and the series concept the derivation will be accomplished by enumerating all the possible outcomes in order to show which is that which are the equivalent network possibility that the or the network to the terminal node so it means the derivation will be accomplished by enumerating all the possible paths from the starting node of the network to the terminal node of the network so will basically start till then a generalization on the derivation procedure based on the flow graph diagram will then be utilized in order to reduce it to the maximum possible extent to simplify the terminology a node will be described by the input-output relationship where no ambiguity would be there for this diagram so in this figure it will illustrate the equivalent one branch network for a series a parallel a self loop Anna some this series concept so there are three series parallel and and self-loop depending on the loops you have all of whose branches must have constant time parameters but those nodes are of the exclusive-or type so with this I will end the 50 second lecture and continue more discussion about the Gert in a very simplistic sense and then start off a new topic as to quite have a nice day and thank you very much [Music] [Music] [Music]