My Math Forum  

Go Back   My Math Forum > College Math Forum > Applied Math

Applied Math Applied Math Forum


Reply
 
LinkBack Thread Tools Display Modes
February 6th, 2014, 08:38 AM   #1
Newbie
 
Joined: Feb 2014

Posts: 1
Thanks: 0

Advanced Math: Algorithm to Solve an Optimal Set

I want to develop a program which analyzes sets. I think the best way I can describe the program is using an example. For those of you familiar with toggle coverage that is the purpose of this application.

The goal is to reach 100% coverage. TestA stresses X% of the chip, but % doesn't matter, what matters is which set of pins/portions of the chip is stressed. So let us say TestA stresses setA and TestB stresses setB, so on and so forth for Y number of tests until we reach 100% coverage.

Here is the problem, we want to reduce Y to Y' such that Y' is the minimum ammount of tests required. How? Lets say TestA can be eliminated because by running TestB, C, D we obtain the set which TestA would have covered.

The question I have is, I want to do research on this area (IEEE articles and so on) but don't know what to search? I am looking for titles, papers, etc. to help me determine an algorithm. If you have 1000 tests, I don't want to say "Can I eliminate testA with B? no? What about B+C? no? What about B+C+D?" In addition to being very slow, it doesn't account for the fact that sure A might be replaced by B+C+D, but A would have significantly helped with removing D+E+F.

I'd appreciate help in going in the right direction.

Thanks!
forkconfig is offline  
 
February 6th, 2014, 03:25 PM   #2
JC
Member
 
Joined: Jun 2008

Posts: 45
Thanks: 0

Re: Advanced Math: Algorithm to Solve an Optimal Set

I think your problem is equivalent to minimum set cover problem. Check it out! Unfortunately efficient algorithm to solve this problem is not known, however if the task is not too big it can be solved by simple bruteforce (and using some tricks like pruning to speed up the search).

Quote:
Originally Posted by forkconfig
The question I have is... ...helped with removing D+E+F.
The last indent is a bit unclear to me, though.
JC is offline  
Reply

  My Math Forum > College Math Forum > Applied Math

Tags
advanced, algorithm, math, optimal, set, solve



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Translating Algorithm into Math? flyjoe Real Analysis 0 February 12th, 2013 06:17 PM
Math algorithm najken Computer Science 3 September 1st, 2012 03:30 PM
Help !.. need advanced math formula put into excell ! TheSwede Advanced Statistics 102 September 19th, 2011 02:48 AM
Advanced Algebra...well advanced for me =p peterle1 Algebra 5 November 23rd, 2009 10:17 AM
Solve for 'x' algebraically, extremely difficult (advanced)? IsenseHelp Algebra 2 January 11th, 2009 05:10 PM





Copyright © 2018 My Math Forum. All rights reserved.