From e8367ef98354d972a8cff041553a74fa7c65dc2f Mon Sep 17 00:00:00 2001 From: Peter Wu Date: Mon, 5 Dec 2016 13:23:39 +0100 Subject: Add assignment text to the template --- part1.tex | 89 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 88 insertions(+), 1 deletion(-) diff --git a/part1.tex b/part1.tex index 45279ff..d5036bf 100644 --- a/part1.tex +++ b/part1.tex @@ -4,6 +4,7 @@ \usepackage{amssymb} \usepackage{epic} \usepackage{graphicx} +\usepackage{gensymb} %\pagestyle{empty} \newcommand{\tr}{\mbox{\sf true}} \newcommand{\fa}{\mbox{\sf false}} @@ -16,8 +17,94 @@ \begin{document} \maketitle -\section*{Problem: Trucks} +\section*{Problem: Packing pallets in trucks} +Eight trucks have to deliver pallets of obscure building blocks to a magic factory. Every +truck has a capacity of 8000 kg and can carry at most eight pallets. In total, the +following has to be delivered: + +\begin{itemize} +\item Four pallets of nuzzles, each of weight 700 kg. +\item A number of pallets of prittles, each of weight 400 kg. +\item Eight pallets of skipples, each of weight 1000 kg. +\item Ten pallets of crottles, each of weight 2500 kg. +\item Twenty pallets of dupples, each of weight 200 kg. +\end{itemize} + +Skipples need to be cooled; only three of the eight trucks have facility for cooling +skipples. + +Nuzzles are very valuable: to distribute the risk of loss no two pallets of nuzzles may +be in the same truck. + +% (a) Investigate what is the maximum number of pallets of prittles that can be delivered, +% and show how for that number all pallets may be divided over the eight trucks. + +% (b) Do the same, with the extra information that prittles and crottles are an explosive +% combination: they are not allowed to be put in the same truck. + +\subsection*{Solution:} + +\section*{Problem: Chip design} +Give a chip design containing two power components and ten regular components satisfying the following constraints: + +\begin{itemize} +\item Both the width and the height of the chip is 30. +\item The power components have width 4 and height 3. +\item The sizes of the ten regular components are $4 \times 5$, $4 \times 6$, + $5 \times 20$, $6 \times 9$, $6 \times 10$, $6 \times 11$, $7 \times 8$, + $7 \times 12$, $10 \times 10$, $10 \times 20$, respectively. +\item All components may be turned $90\degree$, but may not overlap. +\item In order to get power, all regular components should directly be connected + to a power component, that is, an edge of the component should have at least + one point in common with an edge of the power component. +\item Due to limits on heat production the power components should be not too close: +their centres should differ at least 17 in either the x direction or the y direction +(or both). +\end{itemize} + +\subsection*{Solution:} + +\section*{Problem: Job scheduling} +Twelve jobs numbered from 1 to 12 have to be executed satisfying the following requirements: +\begin{itemize} +\item The running time of job $i$ is $i + 5$, for $i = 1, 2, \ldots , 12$. +\item All jobs run without interrupt. +\item Job 3 may only start if jobs 1 and 2 have been finished. +\item Job 5 may only start if jobs 3 and 4 have been finished. +\item Job 7 may only start if jobs 3, 4 and 6 have been finished. +\item Job 8 may not start earlier than job 5. +\item Job 9 may only start if jobs 5 and 8 have been finished. +\item Job 11 may only start if job 10 has been finished. +\item Job 12 may only start if jobs 9 and 11 have been finished. +\item Jobs 5, 7 en 10 require a special equipment of which only one copy is available, so +no two of these jobs may run at the same time. +\end{itemize} + +% (a) Find a solution of this scheduling problem for which the total running time is +% minimal. + +% (b) Do the same with the extra requirement that job 6 and job 12 need a resource of +% limited availability, by which job 6 may only run during the 17 time units in which +% job 12 is running. + +\subsection*{Solution:} + +\section*{Problem: Integer sum from neighbors} +Eight integer variables $a_1$, $a_2$, $a_3$, $a_4$, $a_5$, $a_6$, $a_7$, $a_8$ +are given, for which the initial value of +$a_i$ is $i$ for $i = 1$, \ldots, 8. The following steps are defined: choose $i$ +with $1 < i < 8$ and execute +\[ + a_i := a_{i-1} + a_i+1, +\] +that is, $a_i$ gets the sum of the values of its neighbors and all other values remain +unchanged. + +% (a) Show how it is possible that $a_3 = a_7$ after a number of steps. + +% (b) Show how it is possible that $a_3 = a_5 = a_7$ after a number of steps. +% For this problem both try to use an SMT solver and NuSMV, and discuss how they perform. \subsection*{Solution:} -- cgit v1.2.1