Other answers have shown algorithms to sink the aircraft carrier in at most
shots. Here is a proof that no algorithm can achieve a lower maximum number of shots.
Initially, consider a $5 \times 5$ grid. There are 10 possible placements of the ship onto the grid: 5 horizontally, filling each row, and 5 vertically, filling each column. Each grid square touches exactly 2 possible ship placements, one horizontal and one vertical. In order to find the ship, up to 5 shots are required, as each miss can eliminate only two possibilities, with each shot in a unique row and column in order to touch every possible ship location. Once the ship is hit, the orientation of the ship is still unknown (since there are no other shots in the row or column of the "hit"), so in order to sink it, up to 5 additional shots are required: 4 to sink it, plus an additional possible miss if we guess the wrong direction initially.
Now consider a $10 \times 10$ grid. We can restrict the placement of the ship so that it lies entirely in a single quadrant, and doesn't cross one of the center lines of the grid—in other words, we repeat the $5 \times 5$ case once in each dimension, so that there are 40 possible ship locations, and each square still touches exactly 2 possible ship locations. Even with the restricted ship placement, an optimal algorithm must spend up to 20 shots to guarantee that it hits the ship once, and once it does, as with the $5 \times 5$ grid, it must spend up to 5 shots to sink it. Because 24 shots is insufficient to guarantee sinking the ship when we restrict the ship placement in this way, it's also insufficient if the ship could be placed anywhere else on the grid, meaning that algorithms that guarantee that the ship is sunk in 25 moves or less are optimal.