\documentclass[a4paper]{article}
\pagestyle{empty}
\usepackage[T1]{fontenc}
\usepackage[latin2]{inputenc}
\usepackage{amsmath}
\usepackage[magyar]{babel}
\usepackage{graphics}
\usepackage{epic}
\usepackage{eepic}
\usepackage{color}
\usepackage{amssymb}

%\setlength{\hoffset}{-2 cm}
%\setlength{\voffset}{-1 cm}
%\addtolength{\textwidth}{5 cm}
%\addtolength{\textheight}{8 cm}

\newcommand{\Tr}{\mathop{Tr}}

\begin{document}

\begin{center}
{\Large \bf Számítástudomány alapjai 2003/2004 tavasz\\
Gráfok mátrixai, algoritmuselmélet bevezetés}
\end{center}

\begin{enumerate}

\item Írjuk fel a tetraéder élháló-gráfjának a szomszédossági, illeszkedési, 
kör- és vágásmátrixát! Irányítsuk a tetraéder éleit úgy, hogy egyik csúcs 
be-foka $3$ legyen, a többié egy. Írjuk fel a kapott gráf körmátrixát!

\item Legyen $A$ egy egyszerű irányítatlan gráf szomszédossági mátrixa.
Bizonyítsuk be hogy az alábbi két kijelentés ekvivalens!
\begin{enumerate}
\item A gráf nem tartalmaz 4 hosszúságú kört.
\item Az $A$ bármely két sorának skalárszorzata legfeljebb egy.
\end{enumerate} 

\item Lássuk be, hogy egy egyszerű irányítatlan gráf akkor és csak akkor 
páros, ha szomszédossági mátrixának minden páratlan kitevőjű hatványában 
minden diagonális elem 0.

\item Mi lehet a jelentése $\Tr (A^3)$-nek, ahol $A$ egy egyszerű irányítatlan 
gráf szomszédossági mátrixa?

\item Mutassuk meg, hogy az $n$ pontú irányítatlan fa illeszkedési mátrixának 
rangja $n-1$ !

\item Tegyük fel, hogy egy számítógép egymillió műveletet tud elvégezni egy 
másodperc alatt. Ha $1$ perc gépidő áll rendelkezésünkre, akkor a lineáris 
keresés nevű kereső algoritmus $6\cdot 10^7$ érték esetén alkalmazhatjuk 
legfeljebb. Mennyi ideig tartana ugyanennek a feladatnak az elvégzése  a 
bináris keresés segítségével, és egy perc alatt legfeljebb hány elem közül 
tudunk keresni az utóbbi algoritmussal?

\item Gondoltam egy számot $0$ és $31$ között. Ezt nyilván ki lehet 
barchobázni öt kérdéssel. Ki lehet-e viszont úgy találni, hogy előre eldöntjük 
az öt kérdést (tehát nem az első kérdésre adott válasz után adjuk meg a 
második kérdést)? Bizonyítsuk be, hogy 4 kérdés nem elég.

\item 16 látszólag egyforma pénzdarab közül egyik hamis, könnyebb a többinél.
Határozzuk meg egy kétkarú mérleg segítségével, hogy melyik az, minimális 
számú mérés segítségével! (Tehát igazolni is kell, hogy kevesebb méréssel nem 
lehetséges megállapítani.)

\item Pontosan hány összehasonlítás szükséges ahhoz, hogy egy $n$ elemű 
tömbből egy olyan tagot keressünk, amely a tömb legkisebb 10 eleme közé 
tartozik?

\item Rendezzük sorba az alábbi listát a buborék- és a beszúrásos rendezés 
segítségével: 4, 11, 9, 10, 5, 6, 8, 1, 2, 16.

\item Tegyük fel, hogy $a_1$, $a_2$, \dots, $a_n$ sorozat és $b_1$, $b_2$, 
\dots, $b_n$ sorozat is nagyság szerint növekvő sorrendben van rendezve. 
Adjunk algoritmust, amely ezt a $2n$ darab számot egyetlen növekvő 
sorozattá rendezi. 

\item Egy csupa különböző egész számokból álló sorozatot bitonikusnak 
nevezünk, ha először nő, aztán csökken, vagy pedig fordítva: először csökken, 
aztán nő. (Például az (1, 3, 7, 21, 12, 9, 5), (9, 7, 5, 4, 6, 8) és 
(1, 2, 3, 4, 5) sorozatok bitonikusak). Adjunk $O(n)$ összehasonlítást 
használó rendező algoritmust $n$ elemű bitonikus sorozatok rendezésére!

\end{enumerate}

\end{document}
