Pakowanie online prostokątów i d-wymiarowych kostek
| dc.contributor.advisor | Januszewski, Janusz. Promotor | |
| dc.contributor.author | Zielonka, Łukasz | |
| dc.date.accessioned | 2020-07-13T08:14:06Z | |
| dc.date.available | 2020-07-13T08:14:06Z | |
| dc.date.issued | 2020 | |
| dc.description | Wydział Matematyki i Informatyki | pl |
| dc.description.abstract | Przedmiotem tej rozprawy jest pakowanie online d-wymiarowych boxów oraz d-wymiarowych kostek. Oznaczmy przez b(d) [przez c(d), odpowiednio] największą liczbę taką, że dowolny ciąg d-wymiarowych boxów [kostek, odpowiednio] o krawędziach długości co najwyżej 1 i całkowitej objętości nie większej niż b(d) [niż c(d), odpowiednio] można upakować w d-wymiarowej kostce jednostkowej (tzn. kostce o krawędziach długości 1). W rozdziale 2 prezentuję algorytm pakowania online prostokątów. Stosując ten algorytm pokazuję, że b(2) jest większe lub równe 0,2837. Ponadto w rozdziale 3 dowodzę, że b(d) jest nie mniejsze niż (3-2√2)·3-d dla d większego niż 2. W rozdziale 4 wykazuję, że jeżeli n jest nie mniejsze niż 3 oraz d jest równe 3 lub 4 albo jeżeli n jest liczbą naturalną dodatnią oraz d większe niż 4, to dowolny ciąg d-wymiarowych kostek o krawędziach długości nie większej niż 1 i o całkowitej objętości co najwyżej (n+1) ·2-d można upakować online w n jednostkowych d-wymiarowych kostkach. W rozdziale 5 pokazuję, że powyższy wynik jest słuszny również dla n = 1 i d = 4, to znaczy, że c(4) jest większe lub równe 1/8. Jest to najważniejsza część niniejszej rozprawy. W rozdziale 6 podaję wyniki (bez dowodów) dotyczące zagadnienia pakowania do binów. | pl |
| dc.description.abstract | In this dissertation I examine the online packing of d-dimensional boxes and d-dimensional cubes. Denote by b(d) [by c(d), respectively] the greatest number such that any sequence of d-dimensional boxes [cubes, respectively] of edge length smaller than or equal to 1 and of total volume not greater than b(d) [than c(d), respectively] can be packed online into the d-dimensional unit cube (i.e., a cube of edges of length 1). In Chapter 2, I describe an algorithm for online packing of rectangles. By using this algorithm I show that b(2) is greater than or equal to 0.2837. Moreover, in Chapter 3 I prove that b(d) is not smaller than (3-2√2)·3-d for d greater than 2. In Chapter 4 I show that if n is integer not smaller than 3 and d equals 3 or 4, or if n is positive integer and d is greater than 4, then any sequence of d-dimensional cubes of edge lengths not greater than 1 whose total volume does not exceed (n+1) ·2-d can be online packed into n unit d-dimensional cubes. In Chapter 5 I show that this result holds true also for n = 1 and d = 4, i.e., c(4) is greater than or equal to 1/8. This is the crucial result in the dissertation. In chapter 6 I give results (without proofs) regarding the bin packing problem. | pl |
| dc.identifier.uri | http://hdl.handle.net/10593/25697 | |
| dc.language.iso | pol | pl |
| dc.rights | info:eu-repo/semantics/restrictedAccess | pl |
| dc.subject | pakowanie online | pl |
| dc.subject | online packing | pl |
| dc.subject | prostokąty | pl |
| dc.subject | rectangles | pl |
| dc.subject | boxy | pl |
| dc.subject | boxes | pl |
| dc.subject | kostki | pl |
| dc.subject | cubes | pl |
| dc.title | Pakowanie online prostokątów i d-wymiarowych kostek | pl |
| dc.title.alternative | Online packing of rectangles and d-dimensional cubes | pl |
| dc.type | Dysertacja | pl |